【经典算法】:图的深度优先搜索与广度优先搜索的实现

旧城等待， 2022-06-07 03:21 189阅读 0赞

非常简单，深度优先搜索可以用递归或者栈来实现，广度优先搜索用队列来实现，仅仅是数据结构换了一下而已，其他任何的东西都没有变。

实现样例代码：

#include<iostream>
    #include<queue>
    #include<stack>
    #include<stdlib.h>
    #define MAX 100
    using namespace std;
    
    typedef struct 
    {
        int edges[MAX][MAX];    //邻接矩阵
        int n;                  //顶点数
        int e;                  //边数
    }MGraph;
    
    bool visited[MAX];          //标记顶点是否被访问过
    
    void creatMGraph(MGraph &G)    //用引用作参数
    {
        int i,j;
        int s,t;                 //存储顶点编号
        int v;                   //存储边的权值
        for(i=0;i<G.n;i++)       //初始化
        {
            for(j=0;j<G.n;j++)
            {
                G.edges[i][j]=0;
            }
            visited[i]=false;
        }
        for(i=0;i<G.e;i++)      //对矩阵相邻的边赋权值
        {
            scanf("%d %d %d",&s,&t,&v);   //输入边的顶点编号以及权值
            G.edges[s][t]=v;
        }
    }
    
    void DFS(MGraph G,int v)      //深度优先搜索
    {
        int i;
        printf("%d ",v);          //访问结点v
        visited[v]=true;
        for(i=0;i<G.n;i++)       //访问与v相邻的未被访问过的结点
        {
            if(G.edges[v][i]!=0&&visited[i]==false)
            {
                DFS(G,i);
            }
        }
    }
    
    void DFS1(MGraph G,int v)   //非递归实现
    {
        stack<int> s;
        printf("%d ",v);        //访问初始结点
        visited[v]=true;
        s.push(v);              //入栈
        while(!s.empty())
        {
            int i,j;
            i=s.top();          //取栈顶顶点
            for(j=0;j<G.n;j++)  //访问与顶点i相邻的顶点
            {
                if(G.edges[i][j]!=0&&visited[j]==false)
                {
                    printf("%d ",j);     //访问
                    visited[j]=true;
                    s.push(j);           //访问完后入栈
                    break;               //找到一个相邻未访问的顶点，访问之后则跳出循环
                }
            }
            if(j==G.n)                   //如果与i相邻的顶点都被访问过，则将顶点i出栈
                s.pop();
        }
    }
    
    void BFS(MGraph G,int v)      //广度优先搜索
    {
        queue<int> Q;             //STL模板中的queue
        printf("%d ",v);
        visited[v]=true;
        Q.push(v);
        while(!Q.empty()) 
        {
            int i,j;
            i=Q.front();         //取队首顶点
            Q.pop();
            for(j=0;j<G.n;j++)   //广度遍历
            {
                if(G.edges[i][j]!=0&&visited[j]==false)
                {
                    printf("%d ",j);
                    visited[j]=true;
                    Q.push(j);
                }
            }
        }
    }
    
    int main(void)
    {
        int n,e;    //建立的图的顶点数和边数
        while(scanf("%d %d",&n,&e)==2&&n>0)
        {
            MGraph G;
            G.n=n;
            G.e=e;
            creatMGraph(G);
            DFS(G,0);
            printf("\n");
        // DFS1(G,0);
        // printf("\n");
        // BFS(G,0);
        // printf("\n");
        }
        return 0;
    }