数据结构实验–图的深度优先搜索

系统管理员 2023-07-13 15:10 18阅读 0赞

## 数据结构实验–图的深度优先搜索 ##

**描述**  
图的遍历操作是从图的某一顶点出发，依次访问图中其余顶点，且每个顶点仅被访问一次。请完成无向连通图的深度优先搜索。

邻接矩阵的类型定义为:

typedef struct  
\{

int arcs[MAXVEX][MAXVEX];
    int vexnum;

\}Mgraph;

主函数代码已经给出，请将其余代码补充完整，提交时请勿包含给定代码。

int main()  
\{  
Mgraph g;  
int m,n,i;  
while(scanf("%d%d",&m,&n)!=EOF)  
\{  
creat\_Mgraph(&g,m,n);  
for(i=1;i<=m;i++)  
visited\[i\]=0;  
dfs(g,1);  
printf("\\n");  
\}  
return 0;  
\}  
**输入**  
输入数据为多组，每组数据包含多行，第一行为2个整数n,e，n为图的顶点数，e为边数，接下来是e行，每行2个整数，是一个顶点对，代表一条边所依附的两个顶点。

输入数据为：  
4 5  
1 2  
1 3  
1 4  
2 4  
3 4  
**输出**  
每个图的深度优先搜索序列，每个序列占一行，输出的每个顶点后有一个空格。  
**样例输入**  
3 3  
1 2  
1 3  
2 3  
5 6  
1 2  
1 3  
2 4  
3 4  
2 5  
4 5  
**样例输出**  
1 2 3  
1 2 4 3 5

#include <iostream>
    #include<bits/stdc++.h>
    #include<algorithm>
    #define MAXVEX 35
    using namespace std;
    
    typedef struct{
        
        int arcs[MAXVEX][MAXVEX];
        int vexnum;
    }Mgraph;
    
    int visited[MAXVEX];
    void dfs(Mgraph g,int x)
    {
        
        if(x==1)
        {
        
            visited[x]=1;
            printf("%d ",x);
        }
        int i;
        for(i=1;i<=g.vexnum;i++)
        {
        
            if(g.arcs[x][i]==1&&visited[i]==0)
                {
        
                    printf("%d ",i);
                    visited[i]=1;
                    dfs(g,i);
                }
    
        }
        return;
    
    }
    void creat_Mgraph(Mgraph *g,int m,int n)
    {
        
        int i,j,a,b;
        for(i=1;i<=m;i++)
            for(j=1;j<=m;j++)
            {
        
                g->arcs[i][j]=0;
                g->arcs[j][i]=0;
            }
        g->vexnum=m;
        for(i=0;i<n;i++)
        {
        
                scanf("%d%d",&a,&b);
                g->arcs[a][b]=1;
                g->arcs[b][a]=1;
        }
    }
    int main()
    {
        
        Mgraph g;
        int m,n,i;
        while(scanf("%d%d",&m,&n)!=EOF)
        {
        
            creat_Mgraph(&g,m,n);
            for(i=1;i<=m;i++)
                visited[i]=0;
            dfs(g,1);
            printf("\n");
        }
        return 0;
    }