邻接矩阵存图及遍历——————数据结构作业

今天药忘吃喽~ 2022-04-22 10:20 137阅读 0赞

### 实现 ###

*  邻接矩阵存图
 *  DFS递归遍历
 *  DFS非递归遍历
 *  BFS递归遍历

#include<cstdio>
    #include<cstring>
    #include<queue>
    #include<stack>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    typedef char VerTexType;
    typedef int  ArcType;
    const int MaxInt = 32767;
    const int MVNum  = 100;
    
    typedef struct{
        
            VerTexType vexs[MVNum];//顶点表
            ArcType arcs[MVNum][MVNum];//邻接链表
            int vexnum, arcnum;//当前点数和边数
    }AMGraph;
    
    AMGraph G;
    
    int GreateUDN(AMGraph &G)
    {
        
            cout<<"请输入图点的个数和边的个数："<<endl;
            cin>>G.vexnum>>G.arcnum;
            memset(G.arcs,0,sizeof(G.arcs));
            int v1,v2;
            for(int i=0;i<G.arcnum;++i)
            {
        
                    cin>>v1>>v2;
                    G.arcs[v1][v2]=G.arcs[v2][v1]=1;
            }
            return 1;
    }
    
    bool vis[MVNum];
    void DFS_Recursion(AMGraph G,int v)//DFS递归写法
    {
        
            cout<<v<<" ";
            vis[v]=1;
            for(int i=1;i<=G.vexnum;i++)
            {
        
                    int x = G.arcs[v][i];
                    if(x&&!vis[i])
                            DFS_Recursion(G,i);
            }
    }
    void DFS_NonRecursion(AMGraph G,int v)//DFS非递归
    {
        
            memset(vis,0,sizeof(vis));
            stack<int> s;
            s.push(v);
            while(!s.empty())
            {
        
                    int u=s.top();
                    s.pop();
                    if(!vis[u])
                    {
        
                            cout<<u<<" ";
                            vis[u]=1;
                            for(int i=G.vexnum;i>0;--i)
                                    if(G.arcs[u][i] && !vis[i])
                                            s.push(i);
                    }
            }
    
    }
    void BFS_NonRecursion(AMGraph G,int v)//BFS非递归
    {
        
            memset(vis,0,sizeof(vis));
            queue<int> que;
            que.push(v);
            vis[v]=1;
            cout<<v<<" ";
            while(que.size())
            {
        
                    int  w = que.front();
                    que.pop();
                    for(int i=1;i<=G.vexnum;++i)
                    {
        
                            int x = G.arcs[w][i];
                            if(x&&!vis[i])
                            {
        
                                    cout<<i<<" ";
                                    que.push(i);
                                    vis[i]=1;
                            }
                    }
            }
    
    }
    int main()
    {
        
            printf("         ********************************************************\n"
                   "         *                                                      *\n"
                   "         *             此程序解决无向图的遍历问题               *\n"
                   "         *             由邻接矩阵存储                           *\n"
                   "         *             DFS BFS遍历                              *\n"
                   "         *                                                      *\n"
                   "         ********************************************************\n"
                   );
    
            GreateUDN(G);
    //        for(int i=1;i<=G.vexnum;i++)
    //        {
        
    //                for(int j=1;j<=G.vexnum;j++)
    //                        printf("%d ",G.arcs[i][j]);
    //                puts("");
    //        }
            memset(vis,0,sizeof(vis));
            cout<<"DFS_Recursion:";
            DFS_Recursion(G,1);
            puts("");
            cout<<"DFS_NonRecursion:";
            DFS_NonRecursion(G,1);
            puts("");
            cout<<"BFS_NonRecursion:";
            BFS_NonRecursion(G,1);
            return 0;
    }
    
    /*
            1
          /   \
         2     3
        / \   / \
       4   5 6   7
    
    7 6
    1 2
    1 3
    2 4
    2 5
    3 6
    3 7
    DFS_ans: 1 2 4 5 3 6 7
    BFS_ans: 1 2 3 4 5 6 7
    */

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hwdWVyX1JhbmRvbQ_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hwdWVyX1JhbmRvbQ_size_16_color_FFFFFF_t_70]: /images/20220422/e2e94c67595f4e0da00516ac50b032de.png