图的概述
在众多数据结构中，图应该是最复杂的数据结构了，要了解图的全貌需要较深厚的数学基础，这里不可能在一篇文章内讲完，所以只做抛砖引玉。
图的基本概念
图的两种形式.png
-
有向图：图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种，分别是邻接矩阵、邻接表和十字链表。
1.邻接矩阵表示法
邻接矩阵表示法.png
邻接矩阵表示顶点直接的相邻关系，推出邻接矩阵的目的是表示一种关系。表示这种关系的方法非常简单，具体表示方法如下所示。
- 用一个一维数组存放顶点信息。
- 用一个二维数组表示n个顶点之间的关系”
2.邻接表表示法
虽然邻接矩阵比较简单，只需要使用二维数组即可实现存取操作。但是除了完全图之外，其他图的任意两个顶点并不都是相邻接的，所以邻接矩阵中有很多零元素，特别是当n较大，并且边数和完全图的边（n-1）相比很少时，邻接矩阵会非常稀疏，这样会浪费存储空间。为了解决这个问题，此时邻接表便光荣地登上了历史的舞台。
邻接表是由邻接矩阵改造而来的一种链接结构，因为它只考虑非零元素，所以就节省了零元素所占的存储空间。邻接矩阵的每一行都有一个线性链接表，链接表的表头对应着邻接矩阵该行的顶点，链接表中的每个节点对应着邻接矩阵中该行的一个非零元素。
以下用go代码实现邻接表表示法：
// 顶点数据结构体
type vertext struct {
key string
value interface{}
}
// 图结构体
type Graph struct {
vers []vertext // 存储图所有的顶点
edges map[string][]string // 存储各个顶点所有邻接的边
}
3.邻接矩阵与邻接表的比较
（1）在邻接表中，每个线性链接表中各个节点的顺序是任意的。
（2）只使用邻接表中的各个线性链接表，不能说明它们顶点之间的邻接关系。
（3）在无向图中，某个顶点的度数等于该顶点对应的线性链接表的节点数；在有向图中，某个顶点的“出度”数等于该顶点对应的线性链表的节点数。
邻接矩阵与邻接表对比.png
T1 (n)是指在输入边/弧时，输入的顶点信息是顶点的编号；而T2 (n)是指在输入边/弧时，输入的是顶点本身的信息，此时需要查找顶点在图中的位置。
最后还有一种邻接矩阵与邻接表相结合的表示方法：十字链表法，这里不再展开，感兴趣的可继续深入了解。
图的遍历
图的遍历是指从图中的某个顶点出发，按照某种方法对图中的所有顶点访问且仅访问一次。为了保证图中的各顶点在遍历过程中仅访问一次，需要为每个顶点设一个访问标志。例如可以为图设置一个访问标志数组visited[n]，用于标示图中每个顶点是否被访问过，其初始值为0（“假”）。如果访问过顶点vi ，则设置visited[i]为1（“真”）。图的遍历分为两种，分别是深度优先搜索（Depth-First Search，DFS）和广度优先搜索（Breadth-First Search，BFS）。
注意：图的遍历工作要比树的遍历工作复杂，这是因为图中的顶点关系是任意的，这说明图中顶点之间是多对多的关系，并且图中还可能有回路存在，所以在访问某个顶点后，可能沿着某条路径搜索后又回到该顶点上。
1.深度优先遍历(DFS)
深度优先搜索的过程，是对每一个可能的分支路径深入到不能再深入为止的过程，并且每个节点只能访问一次。
图的深度优先遍历类似于二叉树的深度优先遍历，其基本思想是：从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。显然，这是一个递归的搜索过程。
深度优先遍历.png
以上图为例，假定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。
1.广度优先遍历(BFS)
图的广度优先遍历算法是一个分层遍历的过程，和二叉树的广度优先遍历类似，其基本思想在于：从图中的某一个顶点Vi触发，访问此顶点后，依次访问Vi的各个为层访问过的邻接点，然后分别从这些邻接点出发，直至图中所有顶点都被访问到。
广度优先遍历.png
对于上图所示的无向连通图，若从顶点V1开始，则广度优先遍历的顶点访问顺序是V1→V2→V3→V4→V5→V6→V7→V8。
Go实现图数据结构及常用操作
这里用常用的邻接表表示法
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"
}
网友评论