【数据结构C/C++】图操作之邻接矩阵与邻接表的深度优先遍历_邻接表深度优先遍历

先附上程序效果：

邻接表

邻接矩阵，也就是使用二维数组用来存放每个顶点与对应边的关系，例如两个顶点存在边，那么就将这个二维数组对应的下标设置为一个非0值。如下图：
无向图情况：

有向图情况：

邻接矩阵是一种不错的图存储结构，但是对于边数使用较少的图，比较浪费存储空间，
比如下面这种情况：

而学习线性表的时候我们都知道顺序存储结构浪费空间，所以引出了链式存储结构来节约空间。
因此，同样的我们可以对弧或边使用链式存储结构来避免空间浪费的问题。
于是我们引出了新的图存储结构，邻接表。
我们通过将数组与链表结合来存储一张图，而这种链表与数组相结合的的存储方法称为邻接表。


那么邻接表大概我们知道是什么样子了，那么实现起来就容易了。
接下来是结构体的定义：

typedef struct Adjvex		//邻接域
{
	int adjvex;		//顶点的邻接点在数组的下标
	int weight;		//权值 有没有都可以 看你用的是有向还是无向图
	Adjvex* next;	//下一个邻接点在数组的下标
}*Edgenode,Adjvex;
typedef struct Vertxnode	//顶点节点 顶点数组 存放节点以及邻接的顶点的下标指针
{
	ElemType data;
	Adjvex* firstedge;
}Vertexnode,Adjlist[MAXSIZE];
typedef struct Graphlist		//邻接表 将顶点数组与顶点数和边数结合
{
	Adjlist adjlist;		//顶点数组以及邻接域
	int vexnum, edgenum;	//顶点和边数目;
}Graphlist,*p_Graphlist;

int Visited[MAXSIZE] = {0}; //用来表示当前顶点是否被访问 1表示访问 0表示没有访问
int AdjRectangle[MAXSIZE][MAXSIZE]; //二维数组模拟邻接矩阵
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

对于无向图的构建，我们遵循对称原则，这是由于无向图一条边指向的两个顶点是互相指向对方的，所以在对方的邻接顶点域中都需要将对方的下标存放进来。

void CreateGraphlist(p_Graphlist p)
{
	int i, j, k;
	Edgenode e;
	cout << "输入顶点数和边数" << endl;
	cin >> p->vexnum >> p->edgenum;   //输入边数和表数
	for (i = 0; i < p->vexnum; i++)		//初始化顶点表
	{
		cout << "输入顶点数据" << endl;
		cin >> p->adjlist[i].data;  //顶点数据赋值
		p->adjlist[i].firstedge = NULL;	//暂定邻接边表为空
	}
	for (i = 0; i < p->vexnum; i++)//二维数组模拟邻接矩阵|0 0 1| 
	{										    //例如	 |0 0 1|
		for (k = 0; k < p->vexnum; k++)			//		 |1 1 0|
		{
			AdjRectangle[i][k] = 0;				//暂定初始化为全0
		}
	}
	for (k = 0; k < p->edgenum; k++)//这个for循环用于输入edgenum个边
	{
		cout << "输入边(vi,vj)上的顶点序号" << endl; //vi为边尾，vj为边头
		cin >> i >> j;			 //输入0，1则代表边尾为v0，边头尾v1
		AdjRectangle[i][j] = 1;  //对应的数组位置设置为1，代表有一个表
		AdjRectangle[j][i] = 1;	 //矩阵是对称的，对应的位置也置为1
		e = (Edgenode)malloc(sizeof(Adjvex)); //创建邻接顶点表指针
		e->adjvex = j;						  //邻接表的顶点指向j
		//e->next = p->adjlist[i].firstedge;
		p->adjlist[i].firstedge = e;		  //第一个边指向第一个边表
		e = (Edgenode)malloc(sizeof(Adjvex));  //对称式结构
		e->adjvex = i;
		//e->next = p->adjlist[j].firstedge;
		p->adjlist[j].firstedge = e;
	}
	for (int i = 0; i < p->vexnum; i++) {  //输出邻接矩阵
		for (int j = 0; j < p->vexnum; j++)
		{
			cout << AdjRectangle[i][j] << "  ";
		}
		cout << endl;
	}
	DFSTraverse(p);
}
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

注意:
这里必须着重讲解一下一个节点有多个邻接点的情况。

图中的每一个节点都不止一个邻接点，那么这些邻接点的next是如何指向下一个邻接点的呢？
光看程序不好想象，那么就让我们debug一下吧。
我们以v0点为例，输入v1与v3两条边(只是为了debug而已，了解一次过程就可以推导下一次的过程)
先建立v0与v1的一条边

中途由于不小心点了一下关闭所以可能和下面图片v1的地址是不一样的，但是要表达的意思一样。



可以发现我先输入了v1节点，firstedge会先指向v1节点，而由于firstedge的初始化是NULL，所以v1的next节点是NULL，而之后我输入了v3节点之后，firstedge指向了v3节点，v3节点的next会指向v1节点，这样就形成了一个环路，也就是先输入的反倒在越后面。

那么创建就结束了，比较好理解这个创建，如果实在不理解是怎么创建的，可以进行dubug查看。
那么最后就是重头戏如何遍历整个图了。
我们使用深度优先遍历的方法
那么什么是深度优先遍历？

深度优先遍历

思路大概是从图的某个节点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直到所有图中和v有路径的相通的顶点都被访问到。上图中v0节点先访问v1，v1被访问后v1先访问自己的邻接点v2，v2又访问自己的邻接点v3，v3访问自己的邻接点v0，之后发现v0已经被访问过了，那么就从v3退回到v2再从v2退回到v1，v1再退回到v0，这样就形成了深度优先遍历。可以发现这是由递归来实现的。
那么最后直接放代码吧。分为了邻接表和邻接矩阵的递归遍历。

代码

头文件代码：

#pragma once
#include<iostream>
#include <cstdio>
#include<cstdlib>
typedef int Status;
typedef int ElemType;
typedef char cElemType;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define MAXSIZE 20
#define make (struct student*)malloc(sizeof(struct student));
using namespace std;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

实现代码

#include<algo.h>
typedef struct Adjvex		//邻接域
{
	int adjvex;		//顶点的邻接点在数组的下标
	int weight;		//权值
	Adjvex* next;	//下一个邻接点在数组的下标
}*Edgenode,Adjvex;
typedef struct Vertxnode	//顶点节点
{
	ElemType data;
	Adjvex* firstedge;
}Vertexnode,Adjlist[MAXSIZE];
typedef struct Graphlist		//邻接表
{
	Adjlist adjlist;		//顶点数组以及邻接域
	int vexnum, edgenum;	//顶点和边数目;
}Graphlist,*p_Graphlist;

int Visited[MAXSIZE] = {0}; //用来表示当前顶点是否被访问 1表示访问 0表示没有访问
int AdjRectangle[MAXSIZE][MAXSIZE]; //二维数组模拟邻接矩阵
void DFS(p_Graphlist p, int i)//邻接矩阵的深度优先递归遍历
{
	int j;
	Visited[i] = 1;  //如果访问了该节点则设置为1
	cout << "顶点数据为:" << p->adjlist[i].data << endl; //输出当前节点数据
	for (j = 0; j < p->vexnum; j++)//循环调用递归
	{
		if (AdjRectangle[i][j] == 1 && !Visited[j])//如果边表是1且当前节点没有被访问过则调用递归
		{
			DFS(p, j);//j=0，1，2，3，4...,直到将每一个节点都递归访问了一次之后才结束
		}
	}
}
void DFSTraverse(p_Graphlist p)
{
	int i;
	for (i = 0; i < p->vexnum; i++)
	{
		Visited[i] = 0; //先将所有数据设置为未遍历状态0
	}
	cout << "数据如下：" << endl;
	for (i = 0; i < p->vexnum; i++)//
	{
		if (!Visited[i])
		{
			DFS(p,i);
		}
	}
}
//邻接表的深度优先递归算法
void AdjDFS(p_Graphlist p, int i)
{
	Edgenode e;
	Visited[i] = 1; //访问了当前节点就设置为1	
	cout << p->adjlist[i].data << endl; //输出当前数据
	e = p->adjlist[i].firstedge;  //将第一个邻接点赋值给边表结构体指针
	while (e)
	{
		if (!Visited[e->adjvex])//判断节点是否被访问过 没有则进行递归遍历
		{
			AdjDFS(p, e->adjvex);
		}
		e = e->next;//让e指向自己的下一个位置
	}
}
void AdjDFSTraverse(p_Graphlist p)
{
	int i;
	for (i = 0; i < p->vexnum; i++)
		Visited[i] = 0;//初始化访问数组
	for (i = 0; i < p->vexnum; i++)
	{
		if (!Visited[i])
		{
			AdjDFS(p, i);
		}
	}
}

void CreateGraphlist(p_Graphlist p)
{
	int i, j, k;
	Edgenode e;
	cout << "输入顶点数和边数" << endl;
	cin >> p->vexnum >> p->edgenum;   //输入边数和表数
	for (i = 0; i < p->vexnum; i++)		//初始化顶点表
	{
		cout << "输入顶点数据" << endl;
		cin >> p->adjlist[i].data;  //顶点数据赋值
		p->adjlist[i].firstedge = NULL;	//暂定邻接边表为空
	}
	for (i = 0; i < p->vexnum; i++)//二维数组模拟邻接矩阵|0 0 1| 
	{										    //例如	 |0 0 1|
		for (k = 0; k < p->vexnum; k++)			//		 |1 1 0|
		{
			AdjRectangle[i][k] = 0;				//暂定初始化为全0
		}
	}
	for (k = 0; k < p->edgenum; k++)//这个for循环用于输入edgenum个边
	{
		cout << "输入边(vi,vj)上的顶点序号" << endl; //vi为边尾，vj为边头
		cin >> i >> j;			 //输入0，1则代表边尾为v0，边头尾v1
		AdjRectangle[i][j] = 1;  //对应的数组位置设置为1，代表有一个表
		AdjRectangle[j][i] = 1;	 //矩阵是对称的，对应的位置也置为1
		e = (Edgenode)malloc(sizeof(Adjvex)); //创建邻接顶点表指针
		e->adjvex = j;						  //邻接表的顶点指向j
		e->next = p->adjlist[i].firstedge;	  //这句话的作用是为了使得
		p->adjlist[i].firstedge = e;		  //第一个边指向第一个边表
		e = (Edgenode)malloc(sizeof(Adjvex));  //对称式结构
		e->adjvex = i;
		e->next = p->adjlist[j].firstedge;
		p->adjlist[j].firstedge = e;
	}
	for (int i = 0; i < p->vexnum; i++) {  //输出邻接矩阵
		for (int j = 0; j < p->vexnum; j++)
		{
			cout << AdjRectangle[i][j] << "  ";
		}
		cout << endl;
	}
	DFSTraverse(p);
	AdjDFSTraverse(p);
}

int main()
{
	p_Graphlist p;
	p = (p_Graphlist)malloc(sizeof(Graphlist));
	CreateGraphlist(p);
	
}
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

可以发现邻接矩阵的遍历结果是1 4 3 2，这与我们debug得出的结果是一样的，我们先插入的节点反倒再链表的末尾，后插入的再链表的开头，所以最后插入的v3节点中的数据4最先输出。
那么另一种遍历情况是使用数组判断方法，由于数据是从小到大增加的，所以先插入的节点会先输出，这是邻接矩阵的遍历方法。

408考研各数据结构C/C++代码（Continually updating）

408考研各数据结构C/C++代码（Continually updating）
这个模块是我应一些朋友的需求，希望我能开一个专栏，专门提供考研408中各种常用的数据结构的代码，并且希望我附上比较完整的注释以及提供用户输入功能，ok，fine，这个专栏会一直更新，直到我认为没有新的数据结构可以讲解了。
目前我比较熟悉的数据结构如下：
数组、链表、队列、栈、树、B/B+树、红黑树、Hash、图。
所以我会先有空更新出如下几个数据结构的代码，欢迎关注。 当然，在我前两年的博客中，对于链表、哈夫曼树等常用数据结构，我都提供了比较完整的详细的实现以及思路讲解，有兴趣可以去考古。