邻接矩阵无向图的深度优先遍历C/C++代码实现

我就是我 2023-02-17 12:30 31阅读 0赞

## 图的顺序存储： ##

图没有顺序存储结构，但可以借助二维数组来表示元素 之间的关系，即邻接矩阵表示法。  
用邻接矩阵表示法表示图，除了一个用千存储邻接矩阵的二维数组外， 还需要用一个一维数 组来存储顶点信息。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]

## 深度优先遍历： ##

为了避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点。 为此，设一 个辅助数组visited\[n\] , 其初始值置为"false"或者0, 一旦访问了顶点V, 便置visited\[i\]为"true" 或者1。  
以该图为例：  
![在这里插入图片描述][2020061410443990.png]

## 代码如下： ##

#include<stdio.h>
    
    #define MaxInt 0
    #define MVNum 100
    typedef char VerTexType;    //顶点类型
    typedef int ArcType;		//边权值类型
    
    //邻接矩阵存储结构
    typedef struct
    {
        
    	VerTexType vexs[MVNum];				//顶点表
    	ArcType arcs[MVNum][MVNum];			//邻接矩阵
    
    	int vexnum, arcnum;					//图的当前点数和边数
    }AMGraph;
    void printGraph(AMGraph G);
    int LocateVex(AMGraph G, char v);
    
    //创建无向图
    void CreateUDN(AMGraph &G)
    {
        
    	G.vexnum = 8;						//输入总顶点数和边数
    	G.arcnum = 9;
    	G.vexs[0] = 'v1';					//输入顶点信息
    	G.vexs[1] = 'v2';
    	G.vexs[2] = 'v3';
    	G.vexs[3] = 'v4';
    	G.vexs[4] = 'v5';
    	G.vexs[5] = 'v6';
    	G.vexs[6] = 'v7';
    	G.vexs[7] = 'v8';
    
    	for (int i = 0; i < G.vexnum; i++)			//初始化邻接矩阵为极大值
    	{
        
    		for (int j = 0; j < G.vexnum; j++)
    		{
        
    			G.arcs[i][j] = MaxInt;
    		}
    	}
    
    	//输入并建立边，由于是无向图，故一条边需要建立两次
    	int i, j;
    	i = LocateVex(G, 'v1');
    	j = LocateVex(G, 'v2');
    	G.arcs[i][j] = G.arcs[j][i] = 1;
    	i = LocateVex(G, 'v1');
    	j = LocateVex(G, 'v3');
    	G.arcs[i][j] = G.arcs[j][i] = 1;
    	i = LocateVex(G, 'v2');
    	j = LocateVex(G, 'v4');
    	G.arcs[i][j] = G.arcs[j][i] = 1;
    	i = LocateVex(G, 'v2');
    	j = LocateVex(G, 'v5');
    	G.arcs[i][j] = G.arcs[j][i] = 1;
    	i = LocateVex(G, 'v5');
    	j = LocateVex(G, 'v8');
    	G.arcs[i][j] = G.arcs[j][i] = 1;
    	i = LocateVex(G, 'v4');
    	j = LocateVex(G, 'v8');
    	G.arcs[i][j] = G.arcs[j][i] = 1;
    	i = LocateVex(G, 'v3');
    	j = LocateVex(G, 'v6');
    	G.arcs[i][j] = G.arcs[j][i] = 1;
    	i = LocateVex(G, 'v3');
    	j = LocateVex(G, 'v7');
    	G.arcs[i][j] = G.arcs[j][i] = 1;
    	i = LocateVex(G, 'v6');
    	j = LocateVex(G, 'v7');
    	G.arcs[i][j] = G.arcs[j][i] = 1;
    
    	//打印图的邻接矩阵
    	printGraph(G);
    }
    
    //确定顶点在顶点表数组中的下边，并返回
    int LocateVex(AMGraph G, char v)
    {
        
    	for (int i = 0; i < G.vexnum; i++)
    	{
        
    		if (G.vexs[i] == v)
    		{
        
    			return i;
    		}
    	}
    }
    
    //输出打印
    void printGraph(AMGraph G)
    {
        
    	for (int i = 0; i < G.vexnum; i++)
    	{
        
    		printf("v%d :", i + 1);
    
    		for (int j = 0; j < G.vexnum; j++)
    		{
        
    			printf("%d ", G.arcs[i][j]);
    		}
    		printf("\n");
    	}
    }
    
    //邻接矩阵深度优先遍历
    bool visited[MVNum];			//辅助数组，false表示没被访问
    void DFS_AM(AMGraph G, int v)
    {
        
    	printf("v%c->", G.vexs[v]);
    	visited[v] = true;
    	for (int w = 0; w < G.vexnum; w++)
    	{
        
    		if ((G.arcs[v][w]) != 0 && (!visited[w]))
    		{
        
    			DFS_AM(G, w);
    		}
    	}
    }
    
    int main()
    {
        
    	AMGraph G;
    	CreateUDN(G);
    	
    	int v = 0;		//从0号下标开始遍历访问
    	DFS_AM(G, v);
    }

## 运行结果： ##

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020061410434296.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70
[2020061410443990.png]: https://img-blog.csdnimg.cn/2020061410443990.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200614105434368.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70