数据结构与算法.ppt

该【数据结构与算法 】是由【762357237】上传分享，文档一共【105】页，该文档可以免费在线阅读，需要了解更多关于【数据结构与算法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据结构与算法
从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历 ( Graph Traversal )。
图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。
为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组 visited [ ]，它的初始状态为 0，在图的遍历过程中，一旦某一个顶点 i 被访问，就立即让 visited [i] 为 1，防止它被多次访问。
图的遍历与连通性
深度优先搜索DFS ( Depth First Search )
深度优先搜索的示例
DFS 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；再从 w1 出发，访问与 w1邻 接但还没有访问过的顶点 w2；然后再从 w2 出发，进行类似的访问，…
如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。
图的深度优先搜索算法
template<class NameType, class DistType>
void Graph <NameType, DistType> :: DFS ( ) {
int * visited = new int [NumVertices];
for ( int i = 0; i < NumVertices; i++ )
visited [i] = 0; //访问标记数组 visited 初始化
DFS (0, visited );
delete [ ] visited; //释放 visited
}
template<class NameType, class DistType>
void Graph<NameType, DistType> ::
DFS ( const int v, int visited [ ] ) {
cout << GetValue (v) << ‘ ’; //访问顶点 v
visited[v] = 1; //顶点 v 作访问标记
int w = GetFirstNeighbor (v);
//取 v 的第一个邻接顶点 w
while ( w != -1 ) { //若邻接顶点 w 存在
if ( !visited[w] ) DFS ( w, visited );
//若顶点 w 未访问过, 递归访问顶点 w
w = GetNextNeighbor ( v, w );
//取顶点 v 的排在 w 后面的下一个邻接顶点
}
}
图中有 n 个顶点，e 条边。
1
2
如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为O(n)，则遍历图中所有的顶点所需的时间为O(n2)。
3
如果用邻接表表示图，沿 Firstout  link 链可以找到某个顶点 v 的所有邻接顶点 w。由于总共有 2e 个边结点，所以扫描边的时间为O(e)。而且对所有顶点递归访问1次，所以遍历图的时间复杂性为O(n+e)。
算法分析
广度优先搜索BFS ( Breadth First Search )
广度优先搜索的示例
广度优先搜索过程 广度优先生成树
使用广度优先搜索在访问了起始顶点 v 之后，由 v 出发，依次访问 v 的各个未曾被访问过的邻接顶点 w1, w2, …, wt，然后再顺序访问 w1, w2, …, wt 的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，… 如此做下去，直到图中所有顶点都被访问到为止。
01
广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。
02
为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。
为避免重复访问，需要一个辅助数组 visited [ ]，给被访问过的顶点加标记。
图的广度优先搜索算法
template<class NameType, class DistType>
void Graph <NameType, DistType> ::
BFS ( int v ) {
int * visited = new int[NumVertices];
for ( int i = 0; i < NumVertices; i++ )
visited[i] = 0; //visited 初始化