文档介绍：解决图的编程问题
现在学****的是第1页，共48页
目标
在本章中,你将学到:
在图中存储数据
图的深度优先搜索和广度优先搜索算法
最小生成树
图的最短路径
现在学****的是第2页，共48页
学****情境——用图高速结构如右图所示。
其中
邻接点域(adjvex)：指示与顶点邻接点在图中的位置，对应着一维
数组中的序号，对于有向图，存放的是该边结点所表示的弧的弧头
顶点在一维数组中的序号；
数据域(info)：存储边或弧相关的信息，如权值等，当图中边（或弧）
不含有信息时，该域可以省略。
链域(nextadj)：指向依附于该顶点的下一个边结点的指针。
无向图邻接表的邻接表结点类的代码参见P197页 。
现在学****的是第9页，共48页
用邻接表解决图的编程问题 ——用邻接表表示图 （举例）
对邻接表进行操作的代码参见P199页 。
现在学****的是第10页，共48页
——深度优先搜索
从图的某一顶点x出发，访问x，然后遍历任何一个与x相邻的未被访问的顶点y，再遍历任何一个与y相邻的未被访问的顶点z……，如此下去，直到到达一个所有邻接点都被访问的顶点为止。然后依次回退到尚有邻接点未被访问过的顶点，重复上述过程，直到图中的全部顶点都被访问过为止。
对图进行深度优先遍历。深度优先遍历背后基于堆栈，有2种形式: 第一种是程序中显示构造堆栈，利用压栈出栈操作实现;第二种是利用递归函数调用，基于 递归程序栈实现。本章介绍压栈和出栈的操作。
现在学****的是第11页，共48页
v1
将起始顶点v1压入栈。
——深度优先搜索
现在学****的是第12页，共48页
v1
将顶点v1弹出栈
访问 v1
在栈中压入所有与v1相邻接的未访问顶点
v1
Visited:
——深度优先搜索
现在学****的是第13页，共48页
v4
从栈中弹出顶点 v1
访问 v1
在栈中压入所有与v1相邻接的未访问顶点
v1
Visited:
v2
——深度优先搜索
现在学****的是第14页，共48页
Visited:
从栈中弹出顶点 v2
访问 v2
在栈中压入所有与v2相邻接的未访问顶点
v1
v2
v4
v2
——深度优先搜索
现在学****的是第15页，共48页
Visited:
从栈中弹出顶点 v2
访问 v2
在栈中压入所有与v2相邻接的未访问顶点
v1
v2
v3
v6
v4
——深度优先搜索
现在学****的是第16页，共48页
Visited:
从栈中弹出顶点 v3
访问v3
在栈中压入所有与v3相邻接的未访问顶点
v1
v2
v3
有与v3相邻接的未访问顶点
v6
v3
v4
——深度优先搜索
现在学****的是第17页，共48页
Visited:
从栈中弹出顶点 v3
访问v3
在栈中压入所有与v3相邻接的未访问顶点
v1
v2
v3
有与v3相邻接的未访问顶点
v6
v5
v4
——深度优先搜索
现在学****的是第18页，共48页
Visited:
从栈中弹出顶点 v5
访问v5
在栈中压入所有与v5相邻接的未访问顶点
v1
v2
v3
v5
v6
v4
——深度优先搜索
v5
现在学****的是第19页，共48页
Visited:
从栈中弹出顶点 v6
访问v6
在栈中压入所有与v6相邻接的未访问顶点
v1
v2
v3
v5
v6
v6
v4
——深度优先搜索
现在学****的是第20页，共48页
Visited:
从栈中弹出顶点 v4
访问v4
在栈中压入所有与v4相邻接的未访问顶点
v1
v2
v3
v5
v6
v4
v4
——深度优先搜索
现在学****的是第21页，共48页
Visited:
栈现在是空的
因此，遍历完成
v1
v2
v3
v5
v6
v4
——深度优先搜索
现在学****的是第22页，共48页
尽管上述算法提供了一个简单和常用的方法来遍历图，但是，如果图不是连接的，算法将不能正确工作。
在这样的情况下，你将不能够从单个起始顶点开始遍历所有顶点。
——深度优先搜索
现在学****的是第23页，共48页
为了解决这个问题，你需要对图中所有未访问顶点重复执行上述算法。
对图中每个顶点v重复步骤2
如果v未被访问：