【算法】深度优先搜索遍历的应用设计算法以求解无向图G的连通分量的个数和无向图G的边数

﹏ヽ暗。殇╰゛Y 2022-10-16 07:15 64阅读 0赞

# 应用一 #

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

图示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70]

深度遍历基本算法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）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 1]  
算法设计中需要注意的： 通过在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的放置，以便可被重新放入 
                    }
      }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70]: /images/20221014/39fdf611764c4068b5b0155de9fb3971.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 1]: /images/20221014/2d52c200d30446f6acf364f36ce3d138.png