Day. 16 Graph

Graph(图)顾名思义它是跟图有关的资料结构(废话)。

A~E我们会称为顶点(Vertex)，每一个顶点之间的是线(Edge)，当线是有方向的我们会称这是有向图(Directed graph)，如果没方向就代表两个顶点相通，那就叫无向图(Undirected graph)。
边上的数字代表距离，A到C要6km，A到B要1km...
Graph可以用来储存地图或者关系流程，例如把A~E转成人物，边的值存下他们的关系，A认识B、C，B跟C相互认识....

那我们要怎样去用储存这些资料的关系?
今天会介绍Adjacency list的资料构结，比较常见的还有Adjacency matrix跟Edge list，每一种资料结构都有点不一样。因资料构结的类型，在不同的算法底下，时间复杂度会有差别，这边就不一一介绍了～

Adjacency list

来看一下资料结构

// 顶点
type Vertex struct {
	Name string
}

// 边
type Edge struct {
	Vertex   *Vertex
	Distance int
}

// 图
type Graph struct {
	adjList map[*Vertex][]*Edge
}

Graph里面的adjList是一个map，用来存放图的资料，map里面的Key是每一个顶点，Val是一个slice用来存该顶点的每一条边(slice你也可以用链结来取代哦)。

最後map看起来会长这样

A: [B,C]
B: [C,D]
C: [B,D,E]
D: [E]
E: []

剩下来就把程序的function都补上去

// 新增顶点
func (g *Graph) AddVertex(node *Vertex) {
	g.adjList[node] = []*Edge{}
}

// 新增边
func (g *Graph) AddEage(a *Vertex, b *Vertex, distance int) {
	g.adjList[a] = append(g.adjList[a], &Edge{
		Vertex:   b,
		Distance: distance,
	})
}

// 把顶点跟边都print出来
func (g *Graph) Show() {
	for vertex, edges := range g.adjList {
		str := vertex.Name + " -> "

		for _, edge := range edges {
			str += edge.Vertex.Name + " "
		}

		fmt.Println(str)
	}
}

func newGraph() *Graph {
	return &Graph{
		adjList: map[*Vertex][]*Edge{},
	}
}

来加入顶点跟边

func main() {
	a := &Vertex{
		Name: "A",
	}
	b := &Vertex{
		Name: "B",
	}
	c := &Vertex{
		Name: "C",
	}
	d := &Vertex{
		Name: "D",
	}
	e := &Vertex{
		Name: "E",
	}

	g := newGraph()
	g.AddVertex(a)
	g.AddVertex(b)
	g.AddVertex(c)
	g.AddVertex(d)
	g.AddVertex(e)

	// A的边
	g.AddEage(a, b, 1)
	g.AddEage(a, c, 6)
	// B的边
	g.AddEage(b, c, 2)
	g.AddEage(b, d, 1)
	// C的边
	g.AddEage(c, b, 2)
	g.AddEage(c, d, 2)
	g.AddEage(c, e, 5)
	// D的边
	g.AddEage(d, e, 5)

	g.Show()
}

output:

A -> B C 
B -> C D 
C -> B D E 
D -> E 
E -> 

今天介绍完图的资料结构，明天後天会讲DFS、BFS～