06 基本数据结构：图

在众多数据结构中，图应该是最复杂的数据结构了，要了解图的全貌需要较深厚的数学基础，这里不可能在一篇文章内讲完，所以只做抛砖引玉。

• 有向图：图G中的每条边都是有方向的，则称G为有向图（Digraph）。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。有向边也被称为弧，将边的始点称为弧尾，将终点称为弧头。

• 无向图：如果图中的每条边都是没有方向的，这种图被称为无向图。无向图中的边都是顶点的无序对，通常用圆括号来表示无序对。

• 顶点：通常将图中的数据元素称为顶点（Vertex），通常用V来表示顶点的集合。

• 完全图：如果无向图中的任意两个顶点之间都存在着一条边，则将此无向图称为无向完全图。如果有向图中的任意两个顶点之间都存在着方向相反的两条弧，则将此有向图称为有向完全图。

• 稠密图与稀疏图：当一个图接近完全图时被称为稠密图，反之将含有较少的边数（即当e«n(n-1)）的图称为稀疏图。

• 权和网：图中的每一条边（弧）都可以有一个相关的数值，将这种与边相关的数值称为权。权能够表示从一个顶点到另一个顶点的距离或花费的代价。边上带有权的图称为带权图，也称作网。

• 子图：假设存在两个图G=(V，E)和G'=(V'，E')，如果V’是V的子集（即V' V），并且E’是E的子集（即E' E），则称G’是G的子图。

• 邻接点：在无向图G=(V，E)中，如果边(vi ，vj )∈E，则称顶点vi 和vj 互为邻接点（Adjacent）；边（vi ，vj ）依附于顶点vi 和vj ，即vi 和vj 相关联。

• 顶点的度：顶点的度是指和顶点相关联的边的数量。在有向图中，以顶点vi 为弧尾的弧的值称为顶点vi 的出度，以顶点vi 为弧头的弧的值称为顶点vi 的入度，顶点vi 的入度与出度的和是顶点vi 的度。

• 路径：如果图中存在一个从顶点vi 到顶点vj 的顶点序列，则这个顶点序列被称为路径。在图中有如下两种路径。 -（1）简单路径：指路径中的顶点不重复出现。 -（2）回路或环：是指如果路径中除第一个顶点和最后一个顶点相同以外，其余顶点不重复。一条路径上经过的边的数目称为路径长度。

除了以上概念还有其他，感兴趣的可继续深入学习，这里点到即止

数据结构的最终目的是存储数据，所以我们在研究图的时候，需要更加深入地研究“图”的存储结构。关于图的存储结构，除了存储图中各个顶点本身的信息之外，还要存储顶点之间的所有关系。在图中的常用存储结构有3种，分别是邻接矩阵、邻接表和十字链表。

邻接矩阵表示顶点直接的相邻关系，推出邻接矩阵的目的是表示一种关系。表示这种关系的方法非常简单，具体表示方法如下所示。

• 用一个一维数组存放顶点信息。
• 用一个二维数组表示n个顶点之间的关系”

虽然邻接矩阵比较简单，只需要使用二维数组即可实现存取操作。但是除了完全图之外，其他图的任意两个顶点并不都是相邻接的，所以邻接矩阵中有很多零元素，特别是当n较大，并且边数和完全图的边（n-1）相比很少时，邻接矩阵会非常稀疏，这样会浪费存储空间。为了解决这个问题，此时邻接表便光荣地登上了历史的舞台。

邻接表是由邻接矩阵改造而来的一种链接结构，因为它只考虑非零元素，所以就节省了零元素所占的存储空间。邻接矩阵的每一行都有一个线性链接表，链接表的表头对应着邻接矩阵该行的顶点，链接表中的每个节点对应着邻接矩阵中该行的一个非零元素。

以下用go代码实现邻接表表示法：

// 顶点数据结构体
type vertext struct {
	key   string
	value interface{}
}

// 图结构体
type Graph struct {
	vers  []vertext           // 存储图所有的顶点
	edges map[string][]string // 存储各个顶点所有邻接的边
}

（1）在邻接表中，每个线性链接表中各个节点的顺序是任意的。 （2）只使用邻接表中的各个线性链接表，不能说明它们顶点之间的邻接关系。 （3）在无向图中，某个顶点的度数等于该顶点对应的线性链接表的节点数；在有向图中，某个顶点的“出度”数等于该顶点对应的线性链表的节点数。

T1 (n)是指在输入边/弧时，输入的顶点信息是顶点的编号；而T2 (n)是指在输入边/弧时，输入的是顶点本身的信息，此时需要查找顶点在图中的位置。

最后还有一种邻接矩阵与邻接表相结合的表示方法：十字链表法，这里不再展开，感兴趣的可继续深入了解。

图的遍历是指从图中的某个顶点出发，按照某种方法对图中的所有顶点访问且仅访问一次。为了保证图中的各顶点在遍历过程中仅访问一次，需要为每个顶点设一个访问标志。例如可以为图设置一个访问标志数组visited[n]，用于标示图中每个顶点是否被访问过，其初始值为0（“假”）。如果访问过顶点vi ，则设置visited[i]为1（“真”）。图的遍历分为两种，分别是深度优先搜索（Depth-First Search，DFS）和广度优先搜索（Breadth-First Search，BFS）。

注意：图的遍历工作要比树的遍历工作复杂，这是因为图中的顶点关系是任意的，这说明图中顶点之间是多对多的关系，并且图中还可能有回路存在，所以在访问某个顶点后，可能沿着某条路径搜索后又回到该顶点上。

深度优先搜索的过程，是对每一个可能的分支路径深入到不能再深入为止的过程，并且每个节点只能访问一次。

图的深度优先遍历类似于二叉树的深度优先遍历，其基本思想是：从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。显然，这是一个递归的搜索过程。

以上图为例，假定V1是出发点，首先访问V1。这时两个邻接点V2、V3均未被访问，可以选择V2作为新的出发点，访问V2之后，再找到V2的未访问过的邻接点。同V2邻接的有V1、V4和V5，其中V1已经访问过了，可以选择V4作为新的出发点。重复上述搜索过程，继续依次访问V8、V5。访问V5之后，由于与V5相邻的顶点均已被访问过，搜索退回到V8，访问V8的另一个邻接点V6.接下来依次访问V3和V7，最后得到的访问序列为V1→V2→V4→V8→V5→V6→V3→V7。

图的广度优先遍历算法是一个分层遍历的过程，和二叉树的广度优先遍历类似，其基本思想在于：从图中的某一个顶点Vi触发，访问此顶点后，依次访问Vi的各个为层访问过的邻接点，然后分别从这些邻接点出发，直至图中所有顶点都被访问到。

　　对于上图所示的无向连通图，若从顶点V1开始，则广度优先遍历的顶点访问顺序是V1→V2→V3→V4→V5→V6→V7→V8。

这里用常用的邻接表表示法

type vertext struct {
	key   string
	value interface{}
}

type Graph struct {
	vers  []vertext           // 存储图所有的顶点
	edges map[string][]string // 存储各个顶点所有邻接的边
}

// 顶点是否已存在
func (g *Graph) IsVertextExist(k string) bool {
	for _, item := range g.vers {
		if k == item.key {
			return true
		}
	}
	return false
}

// 添加顶点
func (g *Graph) AddVertext(k string, v interface{}) bool {
	if g.IsVertextExist(k) {
		return false
	}
	g.vers = append(g.vers, vertext{k, v})
	g.edges[k] = make([]string, 0)
	return true
}

// 添加边
func (g *Graph) AddEdge(k1, k2 string) bool {
	if g.IsVertextExist(k1) && g.IsVertextExist(k2) {
		g.edges[k1] = append(g.edges[k1], k2)
		g.edges[k2] = append(g.edges[k2], k1)
		return true
	}
	return false
}

// 移除顶点
func (g *Graph) RemoveVertext(k string) bool {
	isExist := false
	count := len(g.vers)
	for i := 0; i < count; i++ {
		if g.vers[i].key == k {
			g.vers = append(g.vers[:i], g.vers[i+1:]...)
			isExist = true
			break
		}
	}
	if !isExist {
		return false
	}

	delete(g.edges, k)
	for key, slice := range g.edges {
		sCount := len(slice)
		for i := 0; i < sCount; i++ {
			if slice[i] == k {
				g.edges[key] = append(g.edges[key][:i], g.edges[key][i+1:]...)
				break
			}
		}
	}

	return true
}

// 移除边
func (g *Graph) RemoveEdges(k1, k2 string) bool {
	count := len(g.edges[k1])
	for i := 0; i < count; i++ {
		if g.edges[k1][i] == k2 {
			g.edges[k1] = append(g.edges[k1][:i], g.edges[k1][i+1:]...)
			return true
		}
	}

	return false
}

// 广度优先搜索：类似树的层级遍历，使用队列
func (g *Graph) BFS(startVerKey string, handler func(verKey string)) {

	// 1.队列容器
	q := queue.NewLinkQueue(len(g.vers))

	// 2.初始化颜色
	colors := g.initColors()

	// 3.将初始端点加入队列
	q.Enqueue(startVerKey)

	// 4.循环从队列中获取元素
	for {
		// 4.1从队列获取端点
		element := q.Dequeue()
                if element == nil {
			break
		}
		ver := element.(string)

		// 4.2 获取和该端点相连的其他端点
		vEdges := g.edges[ver]

		// 4.3 将该端点的颜色设置成灰色：已探索
		colors[ver] = "grey"

		// 4.4 遍历该端点的其他相连端点,进入队列，并设置灰色：已探索
		for _, item := range vEdges {
			if colors[item] == "white" {
				colors[item] = "grey"
				q.Enqueue(item)
			}
		}
		// 4.5 访问端点,并将端点设置成黑色：已访问
		handler(ver)
		colors[ver] = "black"
	}

}


// 初始化图端点颜色：未访问未探索：白色；未访问已探索：灰色；已访问：黑色
func (g *Graph) initColors() map[string]string {
	colors := make(map[string]string)
	for _, v := range g.vers {
		colors[v.key] = "white"
	}
	return colors
}

// 深度优先搜索
func (g *Graph) DFS(startVerKey string, handler func(string)) {
	// 1.初始化颜色
	colors := g.initColors()
	// 2. 开始递归遍历
	g.dfs(startVerKey,colors,handler)
}

// 深度优先搜索内部递归方法
func (g *Graph) dfs(vKey string,colors map[string]string ,handler func(string))  {
	// 1.将该端点颜色设置成灰色
	colors[vKey] = "grey"

	// 2.访问并处理该端点
	handler(vKey)

	// 3.遍历探索与该节点相连的其他节点
	vEdges := g.edges[vKey]
	for _,item := range vEdges{
		if colors[item] == "white" {
			// 递归遍历
			g.dfs(item,colors,handler)
		}
	}

	// 4. 将该节点设置成已访问
	colors[vKey] = "black"
}