Day.17 Graph-DFS

DFS是简写，全名是Depth-First-Search(深度优先搜寻演算法)
DFS是一种搜寻的算法，在不同的资构结构都会看到，是一种很常见的算法哦！

先来看一下图:

如果我们要找出A点可到达的其他顶点要怎麽做？

我们以A点为起点，每一条边线都一直往下走，直到尽头，再去走其他线边。
红线是第一次寻找，A第一条边是通往B的，直接顺着走到底，到E就没路可走了，回到D点的第二条边走到F，路径为A->B->D->E->F。
当到F没路去，A会走第二条边通往C(绿线)，一样走到底，A->C，当走到E的时候，会发现E之前就来过了，所以停下了，A也没有第三条边可以走，结束搜寻。
直接看图解理解起来应该不难，把它转成程序～

程序:

// 回传全部的顶点
func (g *Graph) getVistedVertex() map[*Vertex]bool {
	visted := map[*Vertex]bool{}
	for v := range g.adjList {
		visted[v] = false
	}

	return visted
}

func (g *Graph) DFS(target *Vertex) {
	visted := g.getVistedVertex() // 用来记录走过的顶点
	visted[target] = true

	g.dfsRecursive(target, visted)
}

// 算法核心用递回的方式来做
func (g *Graph) dfsRecursive(vertex *Vertex, visted map[*Vertex]bool) {
	for _, edge := range g.adjList[vertex] {
		// 判断之前有没有来过
		if !visted[edge.Vertex] {
			// 走过的点要记录下来，不然可能会无限回圈
			visted[edge.Vertex] = true
			fmt.Printf("vist: %v \n", edge.Vertex.Name)
			// 继续递回往下走
			g.dfsRecursive(edge.Vertex, visted)
		}
	}
}

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

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

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

	g.DFS(a)
}

output:

vist: B 
vist: D 
vist: E 
vist: F 
vist: C

明天来讲BFS~