《数据结构》实验报告（五）——图的深度优先搜索

妖狐艹你老母 2022-12-29 04:42 63阅读 0赞

一、实验目的  
(1) 掌握用C语言调试程序的基本方法。  
(2) 掌握图的基本定义及其存储实现。  
(3) 掌握图的基本操作，如图的深度优先搜索。  
二、实验环境  
Windows 10，Microsoft Visual C++ 2010 Express  
三、实验内容  
1、内容描述  
1.采用邻接矩阵表示法创建下图并输出它。  
2.对下图进行深度优先搜索遍历(1为起始点)。  
![在这里插入图片描述][20201220001750389.png]

2、实现代码

#include <stdio.h>
    
    #define MAXV 50
    #define INF 32767
    
    typedef struct
    {
        
    	int vexs[MAXV];
    	int edges[MAXV][MAXV];
    	int n,e;
    }Graph;
    
    //打印邻接矩阵
    void display(Graph G)
    {
        
    	for (int i=0;i<G.n;i++)
    		printf(" %d",(G.vexs)[i]);
    	printf("\n");
    	for (int i=0;i<G.n;i++)
    	{
        
    		printf("%d",(G.vexs)[i]);
    		for(int j=0;j<G.n;j++)
    			printf("%d ",(G.edges)[i][j]);
    		printf("\n");
    	}
    }
    
    //建立
    void create(Graph &G)
    {
        
    	for(int i=0;i<MAXV;i++)
    		for(int j=0;j<MAXV;j++)
    			(G.edges)[i][j]=0;
    	G.n=0;
    	G.e=0;
    }
    
    //插入结点
    void insertvex(Graph &G,int v)
    {
          
    	(G.n)++;
    	int a=G.n;
    	(G.vexs)[a-1]=v;
    	for(int i=0;i<G.n;i++)
    	{
        
    		G.edges[i][a-1]=0;
    		G.edges[a-1][i]=0;
    	}
    }
    
    //插入边
    void insertarc(Graph &G,int v,int w)
    {
        
    	G.e++;
    	int vn=0,wn=0;
    	for(int i=0;i<G.n;i++)
    	{
        
    		if((G.vexs)[i]==v)
    			vn=i;
    		if((G.vexs)[i]==w)
    			wn=i;
    	}
    	(G.edges)[vn][wn]=1;
    	(G.edges)[wn][vn]=1;
    }
    
    //图的深度优先搜索
    bool visited[MAXV] ; //访问标记数组
    int FirstNeighbor(Graph G , int v){
        
    	int i;
    	for(i=0;i<G.n;++i){
        
    		if(G.edges[v][i] == 1 && visited[i] == false)
    			return i;
    	}
    	return -1;
    }
    int NextNeighor(Graph G , int v , int w){
        
    	int i;
    	for(i=w;i<G.n;++i){
        
    		if(G.edges[v][i] == 1 && visited[i] == false)
    			return i;
    	}
    	return -1;
    }
    void DFS(Graph G,int v) {
        
    	int w;
    	printf("%d ",G.vexs[v]);
    	visited[v]=true;
    	for(w=FirstNeighbor(G,v);w>=0;w=NextNeighor(G,v,w)) 
    		if (!visited [w]){
        
    			DFS(G,w);
    		}
    	
    }
    void DFSTraverse(Graph G){
        
    	for (int v=0;v<G.n;++v)
    		visited[v]=false;
    	for (int v=0;v<G.n;++v)
    		if (!visited[v]) 
    			DFS(G,v);
    }
    
    void main()
    {
        
    	Graph G;
    	int a=-1;
    	int v,i,j=1;
        create(G);
    	printf("输入所有结点(-1结束输入）：\n");
    	printf("输入第1个结点：");
    	scanf("%d",&v);
    	int p=2;
    	while(v!=-1){
        
    		insertvex(G,v);
    		printf("输入第%d个结点：",p);
    		scanf("%d",&v);
    		p++;
    	}
    	printf("\n输入边两端的结点(-1 -1结束输入）：\n");
    	printf("输入第1条边：");
    	scanf("%d %d",&i,&j);
    	int k=2;
    	while(i!=-1&&j!=-1){
        
    		insertarc(G,i,j);
    		printf("输入第%d条边：",k);
    		scanf("%d %d",&i,&j);
    		k++;
    	}
    	printf("\n邻接矩阵：\n");
    	display(G);
    	printf("\n深度优先搜索结果：\n");
    	DFSTraverse(G);
    	printf("\n");
    }

四、运行结果  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5Nzc0OQ_size_16_color_FFFFFF_t_70]

[20201220001750389.png]: /images/20221120/a679ea1750b94020aa8833502d0f287b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5Nzc0OQ_size_16_color_FFFFFF_t_70]: /images/20221120/39b7650348f94bfaa57ca7fdff1989bd.png