【数据结构 |
您所在的位置：网站首页 › 图的遍历有哪些应用 › 【数据结构 |
【数据结构
|
【数据结构——图的遍历】
一、介绍二、深度优先搜索DFS(Depth First Search)1、深度优先搜索遍历的过程2、深度优先搜索遍历的算法实现3、非连通图的深度优先搜索遍历
三、广度优先搜索BFS(Breadth First Search)1、介绍2、算法思想和描述
一、介绍
图的遍历：从图的某个顶点出发，依次访问图中所有的顶点，每个顶点被访问一次且仅访问一次。 防止多次访问某一个顶点的思路：设置辅助数组visited[n],用来标记每个被访问的顶点， 初始化状态为visited[n]=0;如果顶点被访问到，则修改辅助数组的值 ：visited[i]=1 二、深度优先搜索DFS(Depth First Search) 1、深度优先搜索遍历的过程
递归的搜索算法：dfs(G,v) /*图的深度优先搜索遍历伪码*/ dfs(G, v) { 访问v，并对v作已访问标记 访问v的邻接点w,若w未被访问，则继续调用dfs(G,w) } /*图的深度优先搜索遍历伪码*/ bool visited[MVNum];//标志访问数组，初值为false void DFS(Graph G, int v) {//从第v个顶点开始深度优先搜索遍历图G cout |
深度优先搜索生成树： 对于无向连通生成图，如果将第一次深度优先搜索时前进操作经过的边保留下来则可以构成一棵深度优先搜索生成树 
【本文地址】
今日新闻 |
推荐新闻 |