数据结构15-图的创建及其遍历方法(BFS+DFS)

1.使用邻接矩阵表示

第一种小写法:

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
#include<iostream>
using namespace std;

#define max_vexs 100
#define max_number 9999

typedef struct Graph {
	char vexs[max_vexs];
	int arcs[max_vexs][max_vexs];
	int vexsnumber;
	int arcsnumber;
};
// 初始化的是这个有权图的顶点数目已经这个有权图的边的数目,还有这个有权图的边进行初始化
Graph* InitGraph(int vexs,int arcs) { // 初始化这个有权图
	Graph* G = new Graph;
	G->vexsnumber = vexs;
	G->arcsnumber = arcs;
	for (int i = 0;i < vexs;i++) {
		for (int j = 0;j < vexs;j++) {
			G->arcs[i][j] = max_number;
		}
	}
	return G;
}
int LocateVex(Graph* G, char app) { // 用来寻找顶点值所对应的下标值,减少时间复杂度
	for (int i = 0;i < G->vexsnumber;i++) {
		if (G->vexs[i] == app) {
			return i;
		}
	}
	return -1;
}
Graph* CreateGraph() { // 进行创建一个有权图出来
	int vexs, arcs;
	cout << "请输入图的顶点个数以及边的个数:" << endl;
	cin >> vexs >> arcs;
	Graph* G = InitGraph(vexs,arcs);
	cout << "请依次输入顶点的信息:" << endl;
	for (int i = 0;i < G->vexsnumber;i++) {// 依次初始化这个有权图的各个顶点的值
		cin >> G->vexs[i];
	}
	cout << "请输入一条边两端的顶点以及这个边的权值大小:" << endl;
	for (int i = 0;i < G->arcsnumber;i++) {
		char vexs1, vexs2;int number;
		cin >> vexs1 >> vexs2 >> number;
		int number1 = LocateVex(G, vexs1);
		int number2 = LocateVex(G, vexs2);
		G->arcs[number1][number2] = number;
		G->arcs[number2][number1] = G->arcs[number1][number2];// 因为我创建的这个图是无向图,可以这么弄
	}
	return G;
}
void printGraph(Graph* app) {
	for (int i = 0;i < app->vexsnumber;i++) {
		for (int j = 0;j < app->vexsnumber;j++) {
			cout << app->arcs[i][j] << "  ";
		}
		cout << endl;
	}
}
int main() {
	Graph* APP = CreateGraph();
	printGraph(APP);
	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
#include<iostream>
using namespace std;

#define max_vexs 100
#define max_number 9999

typedef struct Graph {
	char vexs[max_vexs];
	int arcs[max_vexs][max_vexs];
	int vexsnumber;
	int arcsnumber;
};
// 初始化的是这个有权图的顶点数目已经这个有权图的边的数目,还有这个有权图的边进行初始化
Graph* InitGraph(int vexs, int arcs) { // 初始化这个有权图
	Graph* G = new Graph;
	G->vexsnumber = vexs;
	G->arcsnumber = arcs;
	for (int i = 0;i < vexs;i++) {
		for (int j = 0;j < vexs;j++) {
			G->arcs[i][j] = max_number;
		}
	}
	return G;
}
Graph* CreateGraph() { // 进行创建一个有权图出来
	int vexs, arcs;
	cout << "请输入图的顶点个数以及边的个数:" << endl;
	cin >> vexs >> arcs;
	Graph* G = InitGraph(vexs, arcs);
	cout << "请依次输入顶点的信息:" << endl;
	for (int i = 0;i < G->vexsnumber;i++) {// 依次初始化这个有权图的各个顶点的值
		cin >> G->vexs[i];
	}
	cout << "请输入这个矩阵:" << endl;
	for (int i = 0;i < G->vexsnumber;i++) {
		for (int j = 0;j < G->vexsnumber;j++) {
			cin >> G->arcs[i][j];
		}
	}
	return G;
}
void printGraph(Graph* app) {
	for (int i = 0;i < app->vexsnumber;i++) {
		for (int j = 0;j < app->vexsnumber;j++) {
			cout << app->arcs[i][j] << "  ";
		}
		cout << endl;
	}
}
int main() {
	Graph* APP = CreateGraph();
	printGraph(APP);
	return 0;
}

邻接矩阵的遍历方法

BFS:
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
#include<iostream>
using namespace std;

#define max_vexs 100
#define max_number 9999

typedef struct Graph { // 定义一个图
	char vexs[max_vexs];
	int arcs[max_vexs][max_vexs];
	int vexsnumber;
	int arcsnumber;
};
struct node { // 定义一个链表的结构体
    int data;
    struct node* next;
};
class queue {// 封装这个队列到class中
private:
    node* root;
public:
    queue() {
        root = new node;
        root->next = NULL;
    }
    void pushqueue(int data) {// 入队
        node* node1 = root;
        while (node1->next) {
            node1 = node1->next;
        }
        node* node2 = new node;
        node2->data = data;
        node2->next = nullptr;
        node1->next = node2;
    }
    int popqueue() {// 出队
        if (root->next == NULL) return NULL;
        node* node1 = root->next;
		int number = node1->data;
        root->next = node1->next;
        free(node1);
		return number;
    }
    bool empty() {// 判断这个队列是不是为空
        return root->next == NULL;
    }
    ~queue() { // 析构函数
        while (root) {
            node* temp = root;
            root = root->next;
            delete temp;
        }
    }
};
// 初始化的是这个有权图的顶点数目已经这个有权图的边的数目,还有这个有权图的边进行初始化
Graph* InitGraph(int vexs, int arcs) { // 初始化这个有权图
	Graph* G = new Graph;
	G->vexsnumber = vexs;
	G->arcsnumber = arcs;
	for (int i = 0;i < vexs;i++) {
		for (int j = 0;j < vexs;j++) {
			G->arcs[i][j] = max_number;
		}
	}
	return G;
}
Graph* CreateGraph() { // 进行创建一个有权图出来
	int vexs, arcs;
	cout << "请输入图的顶点个数以及边的个数:" << endl;
	cin >> vexs >> arcs;
	Graph* G = InitGraph(vexs, arcs);
	cout << "请依次输入顶点的信息:" << endl;
	for (int i = 0;i < G->vexsnumber;i++) {// 依次初始化这个有权图的各个顶点的值
		cin >> G->vexs[i];
	}
	cout << "请输入这个矩阵:" << endl;
	for (int i = 0;i < G->vexsnumber;i++) {
		for (int j = 0;j < G->vexsnumber;j++) {
			cin >> G->arcs[i][j];
		}
	}
	return G;
}
void BFS(Graph* app, bool visted[], int index) {
	queue newqueue;
	visted[index] = true;
	cout << app->vexs[index] << "   ";
	newqueue.pushqueue(index);
	while (!newqueue.empty()) {
		int indexnumber = newqueue.popqueue();
		for (int i = 0;i < app->vexsnumber;i++) {
			if (!visted[i] && app->arcs[indexnumber][i] != max_number) {
				cout << app->vexs[i] << "   ";
				visted[i] = true;
				newqueue.pushqueue(i);
			}
		}
	}
}
int main() {
	Graph* APP = CreateGraph();
	bool visted[max_vexs] = { false };
	BFS(APP, visted, 0);
	return 0;
}


DFS:
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
#include<iostream>
using namespace std;

#define max_vexs 100
#define max_number 9999

typedef struct Graph {
	char vexs[max_vexs];
	int arcs[max_vexs][max_vexs];
	int vexsnumber;
	int arcsnumber;
};
// 初始化的是这个有权图的顶点数目已经这个有权图的边的数目,还有这个有权图的边进行初始化
Graph* InitGraph(int vexs, int arcs) { // 初始化这个有权图
	Graph* G = new Graph;
	G->vexsnumber = vexs;
	G->arcsnumber = arcs;
	for (int i = 0;i < vexs;i++) {
		for (int j = 0;j < vexs;j++) {
			G->arcs[i][j] = max_number;
		}
	}
	return G;
}
Graph* CreateGraph() { // 进行创建一个有权图出来
	int vexs, arcs;
	cout << "请输入图的顶点个数以及边的个数:" << endl;
	cin >> vexs >> arcs;
	Graph* G = InitGraph(vexs, arcs);
	cout << "请依次输入顶点的信息:" << endl;
	for (int i = 0;i < G->vexsnumber;i++) {// 依次初始化这个有权图的各个顶点的值
		cin >> G->vexs[i];
	}
	cout << "请输入这个矩阵:" << endl;
	for (int i = 0;i < G->vexsnumber;i++) {
		for (int j = 0;j < G->vexsnumber;j++) {
			cin >> G->arcs[i][j];
		}
	}
	return G;
}
void DFS(Graph* app,int arr[], int index) {
	cout << app->vexs[index] << "    ";
	arr[index] = 1;
	for (int i = 0;i < app->vexsnumber;i++) {
		if (app->arcs[index][i] != max_number && !arr[i]) {
			DFS(app, arr, i);
		}
	}
}
int main() {
	Graph* APP = CreateGraph();
	int visted[max_vexs] = { 0 };
	DFS(APP, visted, 0);
	delete APP;
	return 0;
}

2.使用邻接表表示

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
#include<iostream>
using namespace std;

#define max_vexs 100
#define max_number 9999

typedef struct ArcNode {// 定义一个邻接表边的表示方法
	int adjvexs;// 定义所指向的顶点的下标位置
	int weight;// 这个边的权重
	struct ArcNode* next;
};

typedef struct VexsNode {// 定义表头,存储节点数据data
	char data;
	ArcNode* next;
};

typedef struct Grapth {// 主要集中的图
	VexsNode vexs[max_vexs];
	int vexsnumber;// 顶点的个数
	int arcsnumber;// 边的个数
};
int LocateVex(Grapth G, char app) { // 用来寻找顶点值所对应的下标值,减少时间复杂度
	for (int i = 0;i < G.vexsnumber;i++) {
		if (G.vexs[i].data == app) {
			return i;
		}
	}
	return -1;
}
void CreateGrapth(Grapth& app) {
	cout << "请输入图的顶点个数以及边的个数:" << endl;
	cin >> app.vexsnumber >> app.arcsnumber;
	cout << "请依次输入顶点的信息:" << endl;
	for (int i = 0;i < app.vexsnumber;i++) {// 初始化给个顶点的信息
		cin >> app.vexs[i].data;// 初始化顶点的值
		app.vexs[i].next = NULL;// 刚开始链表的next为NULL
	}
	cout << "请依次输入边的信息（起点 权重 终点）:" << endl;
	for (int b = 0;b < app.arcsnumber;b++) {//接下来就是输入给个边的左右节点,以及自己的边的权值的大小
		char v1, v2;int weight;
		cin >> v1 >> weight >> v2;
		int c = LocateVex(app, v1);
		int s = LocateVex(app, v2);

		ArcNode* p1 = new ArcNode;// 初始化这个第一个边到一个顶点c的链表当中
		p1->weight = weight;
		p1->adjvexs = c;
		p1->next = app.vexs[c].next;
		app.vexs[c].next = p1;

		ArcNode* p2 = new ArcNode;// 初始化这个第一个边到一个顶点s的链表当中
		p2->weight = weight;
		p2->adjvexs = s;
		p2->next = app.vexs[s].next;
		app.vexs[s].next = p2;
	}
}
// 打印邻接表
void PrintGraph(Grapth& app) {
	cout << "图的邻接表表示如下:" << endl;
	for (int i = 0; i < app.vexsnumber; i++) {
		cout << app.vexs[i].data;
		ArcNode* temp = app.vexs[i].next;
		while (temp) {
			cout << " -> (" << app.vexs[temp->adjvexs].data << ", " << temp->weight << ")";
			temp = temp->next;
		}
		cout << endl;
	}
}
int main() {
	Grapth app;
	CreateGrapth(app);
	PrintGraph(app);
	return 0;
}