怎么做一种网站为别人宣传,开设网站维护公司,wordpress shortcodes,个人网站免费域名和服务器一、图的遍历的定义#xff1a;
从图的某个顶点出发访问遍图中所有顶点#xff0c;且每个顶点仅被访问一次。#xff08;连通图与非连通图#xff09;
二、深度优先遍历#xff08;DFS#xff09;#xff1b;
1、访问指定的起始顶点#xff1b;
2、若当前访问的顶点…一、图的遍历的定义
从图的某个顶点出发访问遍图中所有顶点且每个顶点仅被访问一次。连通图与非连通图
二、深度优先遍历DFS
1、访问指定的起始顶点
2、若当前访问的顶点的邻接顶点有未被访问的则任选一个访问之反之退回到最近访问过的顶点直到与起始顶点相通的全部顶点都访问完毕
3、若此时图中尚有顶点未被访问则再选其中一个顶点作为起始顶点并访问之转 2 反之遍历结束。
连通图的深度优先遍历类似于树的先根遍历
1、如何判别V的邻接点是否被访问
解决办法为每个顶点设立一个“访问标志”。首先将图中每个顶点的访问标志设为 FALSE, 之后搜索图中每个顶点如果未被访问则以该顶点为起始点进行深度
优先遍历否则继续检查下一顶点。 访问指定的起始顶点若当前访问的顶点的邻接顶点有未被访问的则任选一个访问之 反之退回到最近访问过的顶点直到与起始顶点相通的全部顶点都访问完毕 回退到1发现了新的没有被访问的结点 继续回退回退到0 再也找不到新的结点了那么回退回退到起始顶点结束搜索 顶点的访问序列为 v0 , v1 , v4 , v5 , v6 , v2 , v3不唯一
2、实现过程依靠栈一维数组和图的邻接矩阵存储方式 图的邻接矩阵存储方式 使用一个一维数组存储所有的顶点对应的下标的元素为1代表已经被访问0代表没有被访问 先访问 v10进栈0处置为1 继续访问 v21进栈1处置为1 继续访问v4依据邻接矩阵3入栈3处置为1 继续访问 v87入栈7处置为1 继续访问 v54入栈4处置为1 继续访问发现没有还没访问的结点了那么好退栈也就是回退开始回退到 v1处也就是0的时候发现了没有被访问的结点那么继续访问之 继续访问 v32进栈2处置为1继续访问v65进栈5处置为1继续访问v76进栈6处置为1 发现没有还没被访问的结点了那么好继续回退也就是退栈的过程 一直到栈空说明深度优先搜索完毕。结束程序。
遍历图的过程实质上是对每个顶点查找其邻接点的过程所耗费的时间取决于所采用的存储结构。
对图中的每个顶点至多调用1次DFS算法因为一旦某个顶点已访问过则不再从它出发进行搜索。
邻接链表表示查找每个顶点的邻接点所需时间为O(e)e为边(弧)数算法时间复杂度为O(ne)。
数组表示查找每个顶点的邻接点所需时间为O(n2)n为顶点数算法时间复杂度为O(n2)。
3、代码实现 //访问标志数组 int visited[MAX] {0}; //用邻接表方式实现深度优先搜索(递归方式 //v 传入的是第一个需要访问的顶点 void DFS(MGraph G, int v) { //图的顶点的搜索指针 ArcNode *p; //置已访问标记 visited[v] 1; //输出被访问顶点的编号 printf(%d , v); //p指向顶点v的第一条弧的弧头结点 p G.vertices[v].firstarc; while (p ! NULL) { //若p-adjvex顶点未访问,递归访问它 if (visited[p-adjvex] 0) { DFS(G, p-adjvex); } //p指向顶点v的下一条弧的弧头结点 p p-nextarc; } } 二、度优先搜索BFS
方法从图的某一结点出发首先依次访问该结点的所有邻接顶点 Vi1, Vi2, …, Vin 再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点重复此过程直至所有顶点均被访问为止。 顶点的访问次序 1、实现过程依靠队列和一维数组来实现
2、代码实现 #include iostream #includequeue using namespace std; const int MAX 10; //辅助队列的初始化置空的辅助队列Q类似二叉树的层序遍历过程 queueint q; //访问标记数组 bool visited[MAX]; //图的广度优先搜索算法 void BFSTraverse(Graph G, void (*visit)(int v)) { int v 0; //初始化访问标记的数组 for (v 0; v G.vexnum; v) { visited[v] false; } //依次遍历整个图的结点 for (v 0; v G.vexnum; v) { //如果v尚未访问则访问 v if (!visited[v]) { //把 v 顶点对应的数组下标处的元素置为真代表已经访问了 visited[v] true; //然后v入队列利用了队列的先进先出的性质 q.push(v); //访问 v打印处理 cout q.back() ; //队不为空时 while (!q.empty()) { //队头元素出队,并把这个出队的元素置为 u类似层序遍历 Graph *u q.front(); q.pop(); //w为u的邻接顶点 for (int w FirstAdjVex(G, u); w 0; w NextAdjVex(G,u,w)) { //w为u的尚未访问的邻接顶点 if (!visited[w]) { visited[w] true; //然后 w 入队列利用了队列的先进先出的性质 q.push(w); //访问 w打印处理 cout q.back() ; }//end of if }//end of for }//end of while }//end of if }// end of for }
