应用一

设计算法以求解无向图G的连通分量的个数

图示：

深度遍历基本算法dfs(v0)如下 :

 void  dfs(int v0) {  visite(v0);  visited[v0]=TRUE;w=firstadj(G,v0);while(w!=0) {if(!visited[w]) dfs(w);w=nextadj(G,v0,w);}}

    firstadj(G,v) ：返回v的第一个邻接点（号），或0（不存在时）。nextadj(G,v,w);返回v的第w邻接点中处于邻接点w之后的邻接点号,  或0（不存在时）

对整个图的遍历算法如下：

void  travel_dfs(graph G) 
{for (i=1; i<=n; i++)  visited[i]=FALSE;for (i=1; i<=n; i++)if(!visited[i])    dfs(i);}

对无向图G来说，选择某一顶点v执行dfs(v)，可访问到所在连通分量中的所有顶点因此，选择起点的次数就是图G的连通分量数， 这可通过修改遍历整个图的算法dfs_travel来实现：每调用一次dfs算法计数一次。另外，考虑到要求求解连通分量数，因而可以将算法设计为整型函数。
具体算法如下

int numofGC(graph G)
{ int i;  int k=0;                   // k用于连通分量的计数for (i=1; i<=n; i++)visited[i]=FALSE;             for (i=1; i<=n; i++)if (visited[i]==FALSE){ k++;  dfs(G,i); }         //用k来累计连通分量个数return  k ;
}

2 设计算法求出无向图G的边数

void  dfs (graph G, int v )
{  int w;visited[v]=TRUE;     //设置访问标志（访问结点的其它操作被省去）w=firstadj(G,v);while (w!=0){ E++;                  //此处意味着找到一条边，故累计到变量E中if (visited[w]==FALSE)dfs(G,w);w=nextadj(G,v,w);}
}int  Enum (graph G )
{  int  i;  E=0;            //全局变量E记录整个图中的边数for (i=1;  i<=n;  i++) visited[i]=FALSE;           for (i=1;  i<=n;  i++)if (visited[i]==FALSE;) dfs(G,i);return  E/2;//注意，因为是无向图，每一条边统计了两次，返回E/2
}

与上面最初的dfs相比多了一个用于统计的E

深度遍历算法的应用二

设计算法，将1–n(=20,或其他数)放在一个环上，使环上任意两个相邻元素的和为质数。
分析：可以用图来描述该问题：
① 用顶点表示一个数
② 若两个数的和为质数，
则对应顶点之间有一条边。 例如，若n=10，对应图如右所示。
在这一表示下，问题转化为：求图中包含所有顶点的简单回路。
如图所示的一个解。
（1，2，3，4，7，6，5，8，9，10）

算法设计中需要注意的： 通过在dfs算法的基础上变化而得：
（1）路径的记录：需要增加变量或参数以记录路径，因此，不妨设一个数组以记录路径中的顶点序列和一个记录长度的变量。
（2）若某些走法行不通，需要重来，为此，要恢复visited[i]标志。
（3）需要判断首尾相接

void   getcc(int k)// A,B,visited为全局变量，k初值为1，B[1]固定为1 { int i;if (k==n && A[B[n],B[1]]==1)      // 所有顶点在路径上，且构成回路，输出print(B);                              else  if (k<n && k>0) for (i=1;i<=n; i++)if (visited[i]==FALSE && A[B[k],i]==1) // 搜索与B[k]相邻的下一个数i{  visited[i]=TRUE; B[k+1]=i;          // 将i放入路径中getcc(k+1);                     // 往后搜索visited[i]=FALSE;     // 取消顶点i的放置，以便可被重新放入 }}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！