龙岩网站建设较好的公司,如何提高网站关键词的排名,稳定一天赚200块游戏,房产交易网站6.3图的遍历
遍历定义#xff1a;
从已给的连通图中某一顶点出发#xff0c;沿着一些边访问遍历图中所有的顶点#xff0c;且使每个顶点仅被访问一次#xff0c;就叫作图的遍历#xff0c;它是图的基本运算。
遍历实质#xff1a;找每个顶点的邻接点的过程。
图的…6.3图的遍历
遍历定义
从已给的连通图中某一顶点出发沿着一些边访问遍历图中所有的顶点且使每个顶点仅被访问一次就叫作图的遍历它是图的基本运算。
遍历实质找每个顶点的邻接点的过程。
图的特点
图中可能存在回路且图的任一顶点都可能与其他顶点相通在访问某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。 怎样避免重复访问 解决思路设置辅助数组visited[n]用来标记每个被访问过的顶点。 初始状态visited[i]为0顶点i被访问改visited[i]为1防止被多次访问 图常用的遍历
深度优先搜索Depth First Search——DFS广度优先搜索Breadth Frist Search——BFS
6.3.1深度优先遍历(DFS)
方法
在访问图中某一起始顶点v后由v出发访问它的任一邻接顶点w1再用w1出发访问与w1邻接但还未被访问过的顶点w2然后再从w2出发进行类似的访问…如此进行下去直至到达所有的邻接顶点都被访问过的顶点u为止。接着退回一步退到前一次刚访问过的顶点看是否还有其他没有被访问的邻接顶点。如果有则访问此顶点之后再从此顶点出发进行与前述类似的访问如果没有就再退回一步进行搜索。重复上述过程直到连通图中所有顶点都被访问过为止。
例如 连通图的深度优先遍历类似于树的先根遍历
6.3.2深度优先搜索遍历算法实现
邻接矩阵无向图深度遍历实现连通图 void DFS(AMGraph G,int v){//图G为邻接矩阵类型coutv;visited[v]true;//访问第v个顶点for(w0;wG.vexnum;w)//依次检查邻接矩阵v所在的行if((G.arcs[v][w]!0)(!visited[w]))DFS(G,w);//w是v的邻接点如果w未访问则递归调用DFS
}DFS算法效率分析
用邻接矩阵来表示图遍历图中每一个顶点都要从头扫描该顶点所在行时间复杂度为O(n2)。用邻接表来表示图虽然有2e个表结点但只需扫描e个结点即可完成遍历加上访问n个头结点的时间时间复杂度为O(ne)。 结论 稠密图适于在邻接矩阵上进行深度遍历稀疏图适于在邻接表上进行深度遍历。 非连通图的遍历 6.3.3广度优先搜索(BFS)
方法从图的某一结点出发首先依次访问该结点的所有邻接点v1v2…vn再按这些顶点被访问的先后次序依次访问与他们相邻接的所有未被访问的顶点。
重复此过程直至所有顶点均被访问为止。 非连通图的广度遍历 顶点访问次序a c d e f h k b g void BFS(Graph G,int v){//按广度优先非递归遍历连通图Gcoutv;visited[v]true;//访问第v个顶点InitQueue(Q);//辅助队列Q初始化置空EnQueue(Q,v);//v进队while(!QueueEmpty(Q)){//队列非空DeQueue(Q,u);//队头元素出队并置为ufor(wFirstAdjVex(G,u);w0;wNextAdjVex(G,u,w))if(!visited[w]){//w为u的尚未访问的邻接顶点coutw;visited[w]true;EnQueue(Q,w);//w进队}}
}BFS算法效率分析
如果使用邻接矩阵则BFS对于每一个被访问到的顶点都要循环检测矩阵中的整整一行n个元素总的时间代价为O(n2。用邻接表来表示图虽然有2e个表结点但只需扫描e个结点即可完成遍历加上访问n个头结点的时间时间复杂度为O(ne)。
6.3.4DFS和BFS算法效率比较
空间复杂度相同都是O(n)借用了堆栈或队列时间复杂度只与存储结构邻接矩阵或邻接表有关而与搜索路径无关。
