Algorithm - 使用深度优先搜索查找图中的路径

深度优先搜索

 了解深度优先搜索前,需了解下面  基础概念:

• 图
• 顶点
• 边
• 连通
• 相邻

Code

package main

import (
	"fmt"
)

// Graph - 以顶点为 key, 相邻的点为[]value
type Graph map[int][]int

// 搜过的点
var marked = make(map[int]bool, 0)

// 路径
var path = make([]int, 0)

func main() {
	// 初始化图
	g := graph(6)
	// 添加边
	g.addEdge(0, 2)
	g.addEdge(1, 2)
	g.addEdge(3, 2)
	g.addEdge(3, 4)
	g.addEdge(3, 5)
	// 路径查找
	p, exist := g.depthFirstPaths(0, 1)
	fmt.Println(p, exist)
}

// 创建一个含有 V 个顶点但不含有边的图
func graph(n int) Graph {
	vt := make(Graph, 0)
	for index := 0; index < n; index++ {
		vt[index] = make([]int, 0)
	}
	return vt
}

// 和 v 相邻的所有顶点
func (g Graph) adj(v int) []int {
	return g[v]
}

// 向图中添加一条边 v-w
func (g Graph) addEdge(v, w int) {
	g[v] = append(g[v], w)
	g[w] = append(g[w], v)
}

// 顶点数
func (g Graph) v() int {
	return len(g)
}

// 边数
func (g Graph) e() int {
	sum := 0
	for _, v := range g {
		sum += len(v)
	}
	return sum / 2
}

// 使用深度优先搜索查找图中的路径 s -> e
func (g Graph) depthFirstPaths(s, e int) (p []int, exist bool) {
	// 获取起点相邻的所有点
	vs := g.adj(s)
	if len(vs) == 0 {
		// 到头了没找到
		reset()
		return nil, false
	}
	// 添加经过节点
	path = append(path, s)
	marked[s] = true
	// 循环相邻节点
	for _, v := range vs {
		if v == e {
			// 直接找到
			path = append(path, v)
			tmp := make([]int, len(path))
			copy(tmp, path)
			reset()
			return tmp, true
		}
		// 碰到曾经经过的点后退一层
		if marked[v] {
			backPath()
			continue
		}

		path = append(path, v)
		marked[v] = true
		// 当前节点递归
		p, exist := g.depthFirstPaths(v, e)
		if exist {
			// 找到返回
			tmp := make([]int, len(p))
			copy(tmp, p)
			reset()
			return tmp, exist
		}
		// 没找到 后退一层
		backPath()
	}
	return nil, false

}

// 重置 路径
func reset() {
	path = path[:0]
}

// 后退一层路径
func backPath() {
	end := 0
	if len(path)-1 > 0 {
		end = len(path) - 1
	}
	path = path[:end]
}