数据结构——图的深度遍历（邻接矩阵DFS）（无向图）_邻接矩阵的dfs

  *==图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中的顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。==*
  简单的来说： 图的邻接矩阵是使用一个二维数组来表示图中两个顶点之间的关系的方法。
  例如：图1就是一个简单的图
1
2
3

用二维数组来表示图之间的关系即如图2所示

在这个二维数组当中，如果两个顶点是直接相连的，就在数组中用1来表示，否则使用0。
图中的A与A肯定是没有距离而言的，在无向图中二维数组是一个对称的数组。
访问时也是从第一行开始访问，当遍历到(a,b)时会跳转到b所在行继续遍历，这也就是深度遍历的特点。（但是问题又来了，在b行遍历时又遇到了（b,a），此时a已经遍历过了，我们会使用布尔类型的visited[]来判断该顶点是否被遍历过，是则赋值为1，否则赋值为0，在每次遍历到一个顶点时，先检查一下是否被遍历过，就可以解决了）

#include <stdio.h>
#include <stdlib.h>
typedef char VertexType;//顶点类型
typedef int EdgeType;//边上的权值
#define MAXVEX 100
#define INFINITY 65535 //65535代表无穷大
#define TRUE 1
#define FALSE 0
typedef int Boolean;
Boolean visited[MAXVEX];

typedef struct
{
	VertexType vexs[MAXVEX];//顶点表
	EdgeType arc[MAXVEX][MAXVEX];//邻接矩阵
	int numVertexes, numEdges;//顶点数以及边数
}MGraph;

void CreateMGraph(MGraph* G)
{
	int  k, w;
	char i, j;
	printf("输入顶点数和边数：\n");
	scanf("%d%d", &G->numVertexes, &G->numEdges);
	printf("请输入顶点信息：");
	getchar();
	for (i = 0; i < G->numVertexes; i++)//分别输入顶点信息
	{
		scanf("%c", &G->vexs[i]);
		getchar();
	}
	for (i = 0; i < G->numVertexes; i++)
		for (j = 0;j < G->numVertexes; j++)
			G->arc[i][j] = INFINITY;    //初始化所有点之间权无穷大

	for (k = 0; k < G->numEdges; k++)
	{
		printf("输入边(vi,vj)上的下标i，下标j和权w:\n");
		scanf("%d%d%d", &i, &j, &w);
		G->arc[i][j] = w;
		G->arc[j][i] = G->arc[i][j];//无向图，矩阵对称
	}
}

//邻接矩阵的深度优先操作
void DFS(MGraph G, int i)
{
	int j;
	visited[i] = TRUE;
	printf("%c", G.vexs[i]);      //打印顶点
	for (j = 0; j < G.numVertexes; j++)
	{
		if (G.arc[i][j] == 1 && !visited[j])
			DFS(G, j);           //对未访问的邻接顶点进行访问
	}
}

//邻接矩阵的深度遍历操作
void DFSTraverse(MGraph G)
{
	int i;
	for (i = 0; i < G.numVertexes; i++)
	
		visited[i] = FALSE;     //初始化所有顶点都为未访问
	

	for (i = 0; i < G.numVertexes; i++)
		if (!visited[i])        //从创造的邻接矩阵中第一行开始遍历
			DFS(G, i);
}

int main()
{
	MGraph G;
	CreateMGraph(&G);
	DFSTraverse(G);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

要提一点ABCDE四个顶点的信息分别存储在邻接矩阵的数组中依次下标为0，1，2，3，4.