贵卅省住房和城乡建设厅网站,百度广告代理公司,做企业的网站的如何推广,卡盟网站制作目录
一. 深度优先遍历
二. 广度优先遍历 图的遍历算法和二叉树不同的是#xff0c;图中可能存在回路#xff0c;且图的任一顶点都可能与其它顶点相通#xff0c;在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。为了避免重复访问#xff0c;我们的解决思…目录
一. 深度优先遍历
二. 广度优先遍历 图的遍历算法和二叉树不同的是图中可能存在回路且图的任一顶点都可能与其它顶点相通在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。为了避免重复访问我们的解决思路是设置辅助数组visited[n]用来标记每个被访问过的顶点。初始状态visited[i]都为0当顶点i被访问改visited[i]为1防止被多次访问。
图的遍历算法主要有深度优先搜索(Depth_First Search——DFS)和广度优先搜索Breadth_Frist Search———BFS)两种。
一. 深度优先遍历
基本思想“一条道走到黑”直到走不了往回退。
在访问图中某一起始顶点v后由v出发访问它的任一邻接顶点w_1所以深度优先搜索操作实现可以不唯一再从w_1出发访问与w_1邻接但还未被访问过的顶点w_2然后再从w_2出发进行类似的访问...如此进行下去直至到达所有的邻接顶点都被访问过的顶点u为止。接着退回一步退到前一次刚访问过的顶点看是否还有其它没有被访问的邻接顶点。如果有则访问此顶点之后再从此顶点出发进行与前述类似的访问如果没有就再退回一步进行搜索。重复上述过程直到连通图中所有顶点都被访问过为止。 观察上面的访问路径连通图的深度优先遍历类似于树的先根遍历。
下面讨论邻接矩阵表示的无向图深度优先遍历的实现对无向图邻接矩阵的每一行代表了这个点与其他点的连接情况。我们从左向右看哪一个元素不为零且这个结点没被访问过visited0就优先访问哪个结点这样给定起点就能唯一确定一条深度优先的遍历路径。
void DFS(AMGraph G, int v){ //图G为邻接矩阵类型v是起点coutv; visited[v] true; //访问第v个顶点for(w 0; w G.vexnum; w) //依次检查邻接矩阵v所在的行if((G.arcs[v][w]!0)(!visited[w])) //路径存在且w未被访问DFS(G, w); //w是v的邻接点如果w未访问则递归调用DFS
}用邻接矩阵来表示图遍历图中每一个顶点都要从头扫描该顶点所在的行时间复杂度为O(n^2)。 用邻接表来表示图虽然有2e个表结点但只需扫描e个结点即可完成遍历加上访问n个头结点的时间时间复杂度为O(ne)。 结论稠密图适于在邻接矩阵上进行深度遍历稀疏图适于在邻接表上进行深度遍历。
二. 广度优先遍历
方法从图的某一结点出发首先依次访问该结点的所有邻接点Vi1, Vi2 ... Vin,再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点。重复此过程直至所有顶点均被访问为止。 void BFS(Graph G, int v){ //按广度优先非递归遍历连通图G起始点为vcoutv; visited[v] true; //访问第v个顶点InitQueue(Q); //辅助队列Q初始化置空EnQueue(Q, v); //v进队while(!QueueEmpty(Q)){ //队列非空DeQueue(Q, u); //队头元素出队并置为ufor(w FirstAdjVex(G,u); w0; w NextAdjVex(G, u, w))if(!visited[w]){ //w为u的尚未访问的邻接顶点coutw; visited[w] true;EnQueue(Q, w); //w进队}//if} //while
} //BFS上述代码实现了广度优先搜索Breadth First SearchBFS算法。BFS是一种用于图的遍历算法通过队列的方式依次访问图中的每个节点。
该代码中的BFS函数接受两个参数图G和起始节点v。首先输出当前节点v的值然后将该节点标记为已访问。接着初始化一个队列Q并将节点v入队。进入循环直到队列Q为空为止。在循环中从队列Q中出队一个节点u然后遍历节点u的邻接节点w。如果节点w未被访问过则输出节点w的值将节点w标记为已访问并将节点w入队。
在BFS函数中visited数组用于记录每个节点是否已经被访问过。InitQueue(Q)用于初始化队列QEnQueue(Q, v)用于将节点v入队DeQueue(Q, u)用于从队列Q中出队一个节点u。
FirstAdjVex(G,u)函数用于获取节点u的第一个邻接节点。它接受两个参数图G和节点u。该函数会返回节点u的第一个邻接节点的索引值或编号。如果节点u没有邻接节点则返回一个特定的标识值比如-1。而NextAdjVex(G, u, w)函数用于获取节点u在节点w之后的下一个邻接节点。它接受三个参数图G、节点u和当前节点w。该函数会返回节点u在节点w之后的下一个邻接节点的索引值或编号。如果节点u在节点w之后没有更多的邻接节点则返回一个特定的标识值比如-1。这两个函数的作用是帮助遍历节点u的邻接节点。通过调用FirstAdjVex(G,u)函数可以获取节点u的第一个邻接节点然后通过调用NextAdjVex(G, u, w)函数可以获取节点u在当前邻接节点w之后的下一个邻接节点以此类推直到遍历完所有的邻接节点。
通过调用BFS函数可以遍历图中所有与起始节点v连通的节点且按照广度优先的顺序进行访问。
