数据结构与算法 图的遍历与连通性.ppt

该【数据结构与算法 图的遍历与连通性 】是由【fanluqian】上传分享，文档一共【43】页，该文档可以免费在线阅读，需要了解更多关于【数据结构与算法 图的遍历与连通性 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。图的遍历与连通性
图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。
为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组 visited [ ]。
从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历 (Graph Traversal)。
辅助数组visited[ ]的初始状态为 0, 在图的遍历过程中, 一旦某一个顶点 i 被访问, 就立即让visited[i]为 1, 防止它被多次访问。
图的遍历的分类:
深度优先搜索
DFS (Depth First Search)
广度优先搜索
BFS (Breadth First Search)
深度优先搜索的示例
A
C
D
E
G
B
F
I
H
A
C
D
E
G
B
F
I
H
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9
前进
回退
深度优先搜索过程 深度优先生成树
深度优先搜索DFS (Depth First Search)
DFS 在访问图中某一起始顶点 v 后, 由 v 出发, 访问它的任一邻接顶点 w1; 再从 w1 出发, 访问与 w1邻接但还没有访问过的顶点 w2; 然后再从 w2 出发, 进行类似的访问, … 如此进行下去, 直至到达所有的邻接顶点都被访问过的顶点 u 为止。接着, 退回一步, 退到前一次刚访问过的顶点, 看是否还有其它没有被访问的邻接顶点。如果有, 则访问此顶点, 之后再从此顶点出发, 进行与前述类似的访问; 如果没有, 就再退回一步进行搜索。重复上述过程, 直到连通图中所有顶点都被访问过为止。
单击此处可添加副标题
template<class T, class E>
void DFS (Graph<T, E>& G, const T& v) {
// 从顶点 v 出发对图 G 进行深度优先遍历的主过程
int i, loc, n = ( ); // 顶点个数
bool *visited = new bool[n]; // 创建辅助数组
for (i = 0; i < n; i++) visited [i] = false;
// 辅助数组 visited 初始化
loc = (v);
DFS (G, loc, visited);// 从顶点0开始深度优先搜索
delete [ ] visited; // 释放visited
}
图的深度优先搜索算法
单击此处可添加副标题
template<class T, class E>
void DFS (Graph<T, E>& G, int v, bool visited[ ]) {
cout << (v) << ' '; //访问顶点v
visited[v] = true; //作访问标记
int w = (v); //第一个邻接顶点
while (w >= 0) { //若邻接顶点w存在
if ( !visited[w] ) DFS(G, w, visited);
//若w未访问过, 递归访问顶点w
w = (v, w); //下一个邻接顶点
}
}
单击此处添加大标题内容
广度优先搜索的示例
广度优先搜索过程 广度优先生成树
A
C
D
E
G
B
F
I
H
A
C
D
E
G
B
F
H
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9
I
广度优先搜索BFS (Breadth First Search)
广度优先搜索是一种分层的搜索过程, 每向前走一步可能访问一批顶点, 不像深度优先搜索那样有往回退的情况。因此, 广度优先搜索不是一个递归的过程。
BFS在访问了起始顶点 v 之后, 由 v 出发, 依次访问 v 的各个未被访问过的邻接顶点 w1, w2, …, wt , 然后再顺序访问 w1, w2, …, wt 的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，… 如此做下去，直到图中所有顶点都被访问到为止。
单击此处可添加副标题
为了实现逐层访问, 算法中使用了一个队列, 以记忆正在访问的这一层和上一层的顶点, 以便于向下一层访问。
为避免重复访问, 需要一个辅助数组 visited [ ]，给被访问过的顶点加标记。
template <class T, class E>
void BFS (Graph<T, E>& G, const T& v) {
int i, w, n = ( );
// 图中顶点个数
图的广度优先搜索算法
bool *visited = new bool[n];
for (i = 0; i < n; i++) visited[i] = false;
int loc = (v); // 取顶点号
cout << (loc) << ' '; // 访问顶点v
visited[loc] = true; // 做已访问标记
Queue<int> Q; (loc);
// 顶点进队列, 实现分层访问
while (!( ) ) { // 循环, 访问所有结点
(loc);
w = (loc); // 第一个邻接顶点
while (w >= 0) { // 若邻接顶点w存在
if (!visited[w]) { // 若未访问过