本文共 2340 字，大约阅读时间需要 7 分钟。

应用一

设计算法以求解无向图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
   
    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的放置，以便可被重新放入                 }  }
   

转载地址：http://ptten.baihongyu.com/