实验4 无向图的深度优先搜索

绝地灬酷狼 2022-06-02 21:09 148阅读 0赞

实验4 无向图的深度优先搜索  
  
  
【实验内容】  
设无向图G有n个点e条边，写一算法建立无向图G的邻接表，并按照深度优先搜索输出顶点。  
  
  
【实验目的】  
1、了解图的定义、特点，区分无向图和有向图的概念；  
2、了解图的数据结构和搜索方法；  
3、掌握无向图的邻接矩阵、邻接表的表示方法；  
4、写出无向图的深度优先搜索程序。  
  
  
【实验步骤与要求】  
1、了解图的定义、特点，区分无向图和有向图的概念；  
2、了解图的数据结构和搜索方法；  
3、掌握无向图的邻接矩阵、邻接表的表示方法；

4、写出无向图的深度优先搜索程序。

代码：

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    int num[1005];//存与第i个节点相邻的节点数目
    int p[1005][1005];//静态邻接表，p[i][j]表示编号为i的节点相邻的第j个节点的标号为多少
    int vis[1005];//用于判断dfs时是否进过第i个节点
    void dfs(int index)//从下标为index的节点搜索
    {
        int i,u;
        printf("%d ",index);
        for(i=0;i<num[index];i++)//遍历与index相邻的所有节点
        {
            u=p[index][i];
            if(!vis[u])//如果没有访问过就递归访问
            {
                vis[u]=1;//标记置为1表示访问了
                dfs(u);
            }
        }
    }
    int main()
    {
        int i,j,n,m,x;
        printf("请输入点的个数:");
        scanf("%d",&n);
        memset(num,0,sizeof(num));//初始化与所有相邻的节点数目为0
        memset(vis,0,sizeof(vis));//初始化所有vis数组表示都没遍历过
        for(i=1;i<=n;i++)
        {
            printf("输入与%d相邻的点个数:",i);
            scanf("%d",&m);
            printf("输入与%d相邻的点:",i);
            for(j=0;j<m;j++)
            {
                scanf("%d",&x);
                p[i][num[i]]=x;
                num[i]++;
            }
        }
        vis[1]=1;//从下标为1开始dfs
        dfs(1);
        return 0;
    }