无向图的深度遍历

#include <iostream>

using namespace std;
const int MAXVEX=100;
int visited[MAXVEX];
typedef struct MGraph        /*邻接矩阵表示边的图的逻辑结构*/
{
    char VertexNode[MAXVEX];
    int arc[MAXVEX][MAXVEX];
    int numVertexes,numEdges;
}MGraph;
void DFS(MGraph G,int i)  /*图的深度遍历算法*/
{
    visited[i]=1;
    cout<<G.VertexNode[i]<<endl;
    for(int j=0;j<G.numVertexes;j++)
    {
        if(visited[j]==0&&G.arc[i][j]==1)  /*找到与i顶点相连的顶点，然后继续遍历*/
            DFS(G,j);
    }
}
void DFSTraverse(MGraph G)   /*对图进行深度遍历*/
{
    int i;
    for(i=0;i<G.numVertexes;i++)   /*初始化集合，visited用来表示顶点中哪些是遍历过的，哪些没有*/
      visited[i]=0;
      for(i=0;i<G.numVertexes;i++)   /*这个式子确保了图无论是几个连通分量都可以被遍历*/
        if(visited[i]==0)
        DFS(G,i);
}
int main()
{
    MGraph G;
    /*初始化图*/
    cout<<"请输入图的顶点数数与边数:"<<endl;
    cin>>G.numVertexes>>G.numEdges;
    cout<<"请输入顶点:"<<endl;
    for(int i=0;i<G.numVertexes;i++)
        cin>>G.VertexNode[i];
    for(int i=0;i<G.numVertexes;i++)
    {
        for(int j=0;j<G.numVertexes;j++)
            G.arc[i][j]=0;
    }
    cout<<"请输入边的两个端点"<<endl;
    for(int i=0;i<G.numEdges;i++)
    {
        int m,n;
        cin>>m>>n;
        G.arc[m][n]=1;
        G.arc[n][m]=1;
    }
    DFSTraverse(G);  /*图的深度遍历*/
    return 0;
}

图的深度遍历实例.png

深度遍历实例结果.png

思路

图的深度遍历的思路并不难，它的实质是按照某种规则找到连通图的生成树。深度遍历其实就是树的先序遍历算法。遍历就是按照一定的顺序访问，显而易见有两个要点：顺序、访问。图的深度遍历从宏观上来说就是将顶点按照一定的顺序放入到一个集合中，在上述的算法中visited数组就可以表示哪些顶点已经放入集合中了。

疑问

我在编辑代码时在想，是否这个算法生成的就是生成树，会不会不是呢？算法的正确性如何保证。

解答

如果不是生成树，就会出现大于顶点总数-1的边数。而出现这样的边数就说明出现了环，而放入集合的顶点无法被二次遍历。因而排除这个可能。然后我想说一说我自己对于递归的理解，我之前看了一些人对于递归的理解，心里也明白是那回事，但就是在应用的时候不是那么得心应手。我对于递归的理解就几个字：方向（接口、管道）、功能。在函数里调用自身，它更多体现的是一个方向问题或者说层次、管道接口之类的，看你怎么理解；其次在自身函数里非调用自身的才是真正要做的事情儿。对于算法的正确性，我主要是靠模拟真实环境，自己手动模拟出图的深度遍历场景。看这个点是否在集合内，不在就输出这个点，并将这个点放入集合，然后找到与之联通的顶点，按照一定的先后顺序，观察是否在集合内，不在就输出并放入集合，然后如此往复。

最后编辑于：2019.08.17 21:23:06