// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

// 图
// Graph 是表示无向图的结构
type Graph struct {
	vertices      int     // 图中的顶点数
	adjacencyList [][]int // 每个顶点的邻接列表
}

// newGraph 基于给定的邻接矩阵创建 Graph 结构的新实例
func newGraph(matrix [][]int) *Graph {
	var graph = &Graph{}
	graph.vertices = len(matrix)
	graph.adjacencyList = make([][]int, graph.vertices)
	for i := 0; i < graph.vertices; i++ {
		graph.adjacencyList = append(graph.adjacencyList, make([]int, 0))
	}
	graph.makeAdjacencyList(matrix)
	return graph
}

// make Adjacency List 将邻接矩阵转换为邻接表
func (graph *Graph) makeAdjacencyList(matrix [][]int) {
	for i := 0; i < graph.vertices; i++ {
		for j := 0; j < graph.vertices; j++ {
			if matrix[i][j] == 1 {
				graph.addEdge(i, j)
			}
		}
	}
}

// addEdge 将顶点 u 和顶点 v 之间的边添加到邻接表中
func (graph *Graph) addEdge(u, v int) {
	if u < 0 || u >= graph.vertices ||
		v < 0 || v >= graph.vertices {
		return
	}

	graph.adjacencyList[u] = append(graph.adjacencyList[u], v)
}

// printGraph 将图的邻接表打印到控制台
func (graph Graph) printGraph() {
	fmt.Print("\n Graph Adjacency List ")
	for i := 0; i < graph.vertices; i++ {
		fmt.Print(" \n [", i, "] :")
		for j := 0; j < len(graph.adjacencyList[i]); j++ {
			if j != 0 {
				fmt.Print(" → ")
			}
			fmt.Print(" ", graph.adjacencyList[i][j])
		}
	}
}
func main() {
	var matrix = [][]int{
		{0, 1, 1, 0, 1},
		{1, 0, 1, 0, 1},
		{1, 1, 0, 1, 0},
		{0, 1, 0, 0, 1},
		{1, 1, 0, 1, 0},
	}
	graph := newGraph(matrix)
	graph.printGraph()
}

//$ go run adjacencyList.go
//
// Graph Adjacency List
// [0] : 1 →  2 →  4
// [1] : 0 →  2 →  4
// [2] : 0 →  1 →  3
// [3] : 1 →  4
// [4] : 0 →  1 →  3s