数据结构-实验三

图的操作与实现

利用图的邻接表和邻接矩阵存储结构设计并实现各种操作算法(任选一种存储结构 来实现算法)。

1、图的邻接表和邻接矩阵存储

建立下图的邻接表和邻接矩阵，并输出之。

1
2
3
4
5
6
7
8
9
10
graph LR
    0 ---|28| 1
    1 ---|16| 2
    2 ---|12| 3
    3 ---|22| 4
    4 ---|25| 5
    5 ---|10| 0
    1 ---|14| 6
    3 ---|18| 6
    4 ---|24| 6
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
#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) {
	cout << "邻接矩阵表示的图:" << endl;
	cout << endl;
	for (int i = 0; i < app->vexsnumber; i++) {// 打印矩阵内容
		for (int j = 0; j < app->vexsnumber; j++) {
			if (app->arcs[i][j] == max_number) { // max_number表示无穷大，无边
				cout << "  ∞  ";
			}
			else {
				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
7 9
0 1 2 3 4 5 6
0    28  9999  9999  9999    10  9999
28     0    16  9999  9999  9999    14
9999    16     0    12  9999  9999    18
9999  9999    12     0    22  9999    18
9999  9999  9999    22     0    25    24
10  9999  9999  9999    25     0  9999
 9999    14    18    18    24  9999     0

参考结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
请输入图的顶点个数以及边的个数:
7 9
请依次输入顶点的信息:
0 1 2 3 4 5 6
请输入这个矩阵:
0    28  9999  9999  9999    10  9999
28     0    16  9999  9999  9999    14
9999    16     0    12  9999  9999    18
9999  9999    12     0    22  9999    18
9999  9999  9999    22     0    25    24
10  9999  9999  9999    25     0  9999
 9999    14    18    18    24  9999     0
邻接矩阵表示的图:
0  28    ∞    ∞    ∞  10    ∞
28  0  16    ∞    ∞    ∞  14
  ∞  16  0  12    ∞    ∞  18
  ∞    ∞  12  0  22    ∞  18
  ∞    ∞    ∞  22  0  25  24
10    ∞    ∞    ∞  25  0    ∞
  ∞  14  18  18  24    ∞  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 = s;
		p1->next = app.vexs[c].next;
		app.vexs[c].next = p1;

		ArcNode* p2 = new ArcNode;// 初始化这个第一个边到一个顶点s的链表当中
		p2->weight = weight;
		p2->adjvexs = c;
		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;
}

参考数据:

1
2
3
4
5
6
7
8
9
10
11
7 9
0 1 2 3 4 5 6
0 28 1
0 10 5
1 16 2
1 14 6
2 12 3
2 18 6
3 22 6
4 25 5
4 24 6

参考结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
请输入图的顶点个数以及边的个数:
7 9
请依次输入顶点的信息:
0 1 2 3 4 5 6
请依次输入边的信息（起点 权重 终点）:
0 28 1
0 10 5
1 16 2
1 14 6
2 12 3
2 18 6
3 22 6
4 25 5
4 24 6
图的邻接表表示如下:
0 -> (5, 10) -> (1, 28)
1 -> (6, 14) -> (2, 16) -> (0, 28)
2 -> (6, 18) -> (3, 12) -> (1, 16)
3 -> (6, 22) -> (2, 12)
4 -> (6, 24) -> (5, 25)
5 -> (4, 25) -> (0, 10)
6 -> (4, 24) -> (3, 22) -> (2, 18) -> (1, 14)

2、图的各种遍历算法实现

以任意结点v为起点，实现上述图的深度优先和广度优先遍历算法

深度优先
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
#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;
}
广度优先
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
#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;
}

3、最小生成树的算法实现

利用普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法求上图的最小生成树，算法实现 代码必须有注释。

普里姆(Prim)算法
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
#include<iostream>
using namespace std;

//在这里需要注意的是:对于weight的值得问题就是:如果就在这个Prime树里面的weight就为0;还有一点自身的weight为0
//如果weight不为0的话,就说明这个顶点还没有加入到这个prim树里面

#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;
};
typedef struct CloseEdge { // 定义一个辅助的数组
	char vexs;// 记录顶点
	int weight;// 记录这个顶点到这个已经有的树的最小距离
};
// 初始化的是这个有权图的顶点数目已经这个有权图的边的数目,还有这个有权图的边进行初始化
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;
}
CloseEdge* InitCloseEdge(Graph* app, int indexnumber) { // 初始化这个距离prim树最小距离
	CloseEdge* closeedge = new CloseEdge[app->vexsnumber];
	for (int i = 0;i < app->vexsnumber;i++) {
		closeedge[i].vexs = app->vexs[indexnumber]; // 记录这个在prim里面的顶点
		closeedge[i].weight = app->arcs[indexnumber][i];// 给每一个在prime树之外的顶点距离目标indexnumber的权值大小
	}
	return closeedge;
}
int GetMinEdge(Graph* app, CloseEdge* closeedge) { // 获取最小权值的顶点的权值的下标
	int indexnumber = -1;
	int minnumber = max_number;
	for (int i = 0;i < app->vexsnumber;i++) {
		if (closeedge[i].weight != 0 && closeedge[i].weight < minnumber) {
			minnumber = closeedge[i].weight;
			indexnumber = i;
		}
	}
	return indexnumber;
}
void Prim(Graph* app,int indexnumber) {
	int minnumber;// 声明一个最小值变量
	CloseEdge* closeedge = InitCloseEdge(app, indexnumber);
	cout << "Prim最小生成树为:" << endl;
	for (int i = 0;i < app->vexsnumber - 1;i++) {
		minnumber = GetMinEdge(app, closeedge);
		if (minnumber == -1) {
			cout << "无法找到最小权值的边，可能图不连通。" << endl;
			break;
		}
		cout << closeedge[minnumber].vexs << "--->" << app->vexs[minnumber] << "   " << closeedge[minnumber].weight << endl;
		closeedge[minnumber].weight = 0;
		for (int j = 0;j < app->vexsnumber;j++) {
			if (app->arcs[minnumber][j] < closeedge[j].weight) {
				closeedge[j].weight = app->arcs[minnumber][j];
				closeedge[j].vexs = app->vexs[minnumber];
			}
		}
	}
}
int main() {
	Graph* APP = CreateGraph();
	int visted[max_vexs] = { 0 };
	Prim(APP, 0);
	delete APP;
	return 0;
}
克鲁斯卡尔(Kruskal)算法
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
#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;
};
typedef struct Edge {
	int start;
	int end;
	int weight;
};
Edge* InitEdge(Graph* app) {// 初始化储存顶点以及边的信息以及权值
	int index = 0;
	Edge* edge = new Edge[app->arcsnumber];
	for (int i = 0; i < app->vexsnumber; i++) {
		for (int j = i + 1; j < app->vexsnumber; j++) {
			if (app->arcs[i][j] != max_number) {
				edge[index].start = i;
				edge[index].end = j;
				edge[index].weight = app->arcs[i][j];
				index++;
			}
		}
	}
	return edge;
}
// 初始化的是这个有权图的顶点数目已经这个有权图的边的数目,还有这个有权图的边进行初始化
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 sortEdge(Edge* edge, Graph* G) { // 冒泡排序对这个初始化的边的权值进行排序,小的在前面
	Edge temp;
	for (int i = 0; i < G->arcsnumber - 1; i++) {
		for (int j = 0; j < G->arcsnumber - i - 1; j++) {
			if (edge[j].weight > edge[j + 1].weight) {
				temp = edge[j];
				edge[j] = edge[j + 1];
				edge[j + 1] = temp;
			}
		}
	}
}
void kruskal(Graph* G) { // kruskal算法
	int connected[max_number];
	for (int i = 0; i < G->vexsnumber; i++) {
		connected[i] = i;
	}
	Edge* edge = InitEdge(G);
	sortEdge(edge, G);
	for (int i = 0; i < G->arcsnumber; i++) {
		int start = connected[edge[i].start];
		int end = connected[edge[i].end];
		if (start != end) {
			cout << G->vexs[edge[i].start] << "--->" << G->vexs[edge[i].end] << "-----" << edge[i].weight << endl;
			for (int j = 0; j < G->vexsnumber; j++) {
				if (connected[j] == end) {
					connected[j] = start;
				}
			}
		}
	}
}
int main() {
	Graph* APP = CreateGraph();
	kruskal(APP);
	delete APP;
	return 0;
}

4、最短路径的算法实现

(1) 利用狄克斯特拉(Dijkstra)算法求上图中任意结点 v 到其它结点 w 的最短路径， 算法实现代码必须有注释；
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
#include<iostream>
using namespace std;

#define max_vexs 100
#define max_number 9999

// 全局设计三个数组用来存储顶点是否被访问过,以及这个这个点距离源点的距离大小是多少,最后一个就是用来存储这个顶点的前驱是哪一个顶点,后面可以通过前驱来找到这个最短的路径
bool visted[max_number];// 用来记录是否被访问到
int path[max_number]; // 用来记录这个顶点的前驱是哪一个数组的下标
int power[max_number];// 用来存储这个源点到这个点的距离大小是多少

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 Dijkstra(Graph* G, int index) { // DJ算法,index是指从哪一个源点出发
	// 首先是初始化这三个数组
	for (int i = 0;i < G->vexsnumber;i++) {
		visted[i] = false;
		power[i] = G->arcs[index][i];
		if (power[i] < max_number) {
			path[i] = index;
		}
		else {
			path[i] = -1;
		}
	}
	visted[index] = true;
	power[index] = 0;
	// 初始化结束,开始循环找最短距离,更新这三个数组的值
	for (int k = 1;k < G->vexsnumber;k++) {
		int minnumber = max_number;
		int vexs;
		for (int i = 0;i < G->vexsnumber;i++) {// 寻找最小值,在这个没有被遍历过的顶点当中
			if (!visted[i] && power[i] < minnumber) {
				minnumber = power[i];
				vexs = i;
			}
		}
		visted[vexs] = true;
		// 接下来就是对最短路径的更新处理
		for (int j = 0;j < G->vexsnumber;j++) {
			if (!visted[j] && (power[vexs] + G->arcs[vexs][j] < power[j])) {// 如果从一个点出发到他四周的点的权值比之前的还要小,那就更新这个新的点到这个权值中来
				power[j] = power[vexs] + G->arcs[vexs][j];// 更新新的权值
				path[j] = vexs;// 更新前驱
			}
		}
	}
	//最后打印出来这个最短路径
	for (int d = 0;d < G->vexsnumber;d++) {
		cout << G->vexs[d] << "      " << "path[" << path[d] << "]" << "      " << "power:" << power[d] << endl;
	}
}
int main() {
	Graph* APP = CreateGraph();
	Dijkstra(APP, 0);
	delete APP;
	return 0;
}
(2) 利用弗洛伊德(Floyd)算法求上图中的多源最短路径，算法实现代码必须有注释
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
#include<iostream>
using namespace std;

#define max_vexs 100
#define max_number 9999

int D[max_vexs][max_vexs];// 定义一个二维数组用来存储权值大小,也就是距离大小
int Path[max_vexs][max_vexs];// 定义一个二维数组用来存储这个路径的前驱,如果中间没有前驱的话就是直接-1,有前驱的话就是复制为那个顶点的下标

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 Floyd(Graph* app) {
	// 首先先初始化这两个二维数组
	for (int i = 0;i < app->vexsnumber;i++) {
		for (int j = 0;j < app->vexsnumber;j++) {
			D[i][j] = app->arcs[i][j];
			if (app->arcs[i][j] < max_number) {// 如果这个点的值不是max_vexs的话就是要设置这个顶点的前驱
				Path[i][j] = i;
			}
		}
	}
	// 接下来就是对这两个二维数组进行赋值
	for (int k = 0;k < app->vexsnumber;k++) {
		for (int g = 0;g < app->vexsnumber;g++) {
			for (int t = 0;t < app->vexsnumber;t++) {
				if (D[g][k] + D[k][t] < D[g][t]) {// 如果中间增加了节点之后的权值比之前的权值好药小的话就直接更新这个权值
					D[g][t] = D[g][k] + D[k][t];// 更新新的权值大小
					Path[g][t] = Path[k][t];// 更新新的前驱
				}
			}
		}
	}
	// 输出这个Floyd的两个二维数组
	cout << "权值大小:" << endl;
	for (int s = 0;s < app->vexsnumber;s++) {
		for (int e = 0;e < app->vexsnumber;e++) {
			cout << D[s][e] << "    ";
		}
		cout << endl;
	}
	cout << "前驱大小:" << endl;
	for (int s = 0;s < app->vexsnumber;s++) {
		for (int e = 0;e < app->vexsnumber;e++) {
			cout << Path[s][e] << "    ";
		}
		cout << endl;
	}
}
int main() {
	Graph* APP = CreateGraph();
	Floyd(APP);
	delete APP;
	return 0;
}

5、求解无权图的单源最短路径问题（结合迷宫的最短路径问题）

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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

#define max_size 10

int px[4] = { 0, 0, -1, 1 };
int py[4] = { 1, -1, 0, 0 };

struct postion {
    int x, y;
    int ans = 0;
};
struct path {
    int x, y;
};
path pre[max_size][max_size];
struct map {
    int m, n;
    int app[max_size][max_size];
    bool visited[max_size][max_size] = { false };
    int x1, y1;
    int x2, y2;
};
struct node {
    postion data;
    struct node* next;
};
class queue {
private:
    node* root;
public:
    queue() {
        root = new node;
        root->next = NULL;
    }
    void push(postion data) {
        node* node1 = root;
        while (node1->next) {
            node1 = node1->next;
        }
        node* node2 = new node;
        node2->data = data;
        node2->next = nullptr;
        node1->next = node2;
    }
    postion front() {
        if (root->next == NULL) {
            return { -1,-1 };
        }
        else {
            postion number = root->next->data;
            return number;
        }
    };
    bool empty() {
        return root->next == NULL;
    }
    void pop() {
        if (root->next == NULL) return;
        node* node1 = root->next;
        root->next = node1->next;
        free(node1);
    }
    void printnode() {
        node* node1 = root->next;
        printf("队列:");
        while (node1) {
            printf("-->(%d,%d)", node1->data.x, node1->data.y);
            node1 = node1->next;
        }
        printf("\n");
    }
    ~queue() {
        while (root) {
            node* temp = root;
            root = root->next;
            delete temp;
        }
    }
};
void bfs(map& site) {
    postion currentsite;
    postion nextsite;
    currentsite.x = site.x1;
    currentsite.y = site.y1;
    currentsite.ans = 0;
    site.visited[currentsite.x][currentsite.y] = true;
    queue app;
    app.push(currentsite);
    while (!app.empty()) {
        currentsite = app.front();
        app.pop();
        if (currentsite.x == site.x2 && currentsite.y == site.y2) {
            cout << "走出了迷宫!" << endl;
            cout << "共走了: " << currentsite.ans << " 步" << endl;
            path truepath[max_size * max_size];
            cout << "走过的路径为:";
            truepath[0].x = site.x2;
            truepath[0].y = site.y2;
            int number = 1;
            bool istrue = true;
            truepath[number] = pre[site.x2][site.y2];
            while (istrue) {
                if (truepath[number].x == site.x1 && truepath[number].y == site.y1) {
                    istrue = false;
                    break;
                }
                else {
                    number++;
                    truepath[number] = pre[truepath[number - 1].x][truepath[number - 1].y];
                }
            }
            cout << "这个的走过的路径为:";
            for (int i = currentsite.ans;i >= 0;i--) {
                cout << "(" << truepath[i].x << "," << truepath[i].y << ")" << "-->";
            }
            cout << "endl" << endl;
            return;
        }
        for (int i = 0; i < 4; i++) {
            nextsite.x = currentsite.x + px[i];
            nextsite.y = currentsite.y + py[i];
            if (nextsite.x >= 1 && nextsite.y >= 1 && !site.visited[nextsite.x][nextsite.y] && site.app[nextsite.x][nextsite.y] && nextsite.x <= site.m && nextsite.y <= site.n) {
                pre[nextsite.x][nextsite.y].x = currentsite.x;
                pre[nextsite.x][nextsite.y].y = currentsite.y;
                nextsite.ans = currentsite.ans + 1;
                site.visited[nextsite.x][nextsite.y] = true;
                app.push(nextsite);
            }
        }
    }
    cout << "没有走出迷宫" << endl;
}
int main() {
    cout << "请输入这个迷宫的长和宽 m 与 n：" << endl;
    map total;
    scanf_s("%d", &total.m);
    scanf_s("%d", &total.n);
    cout << "请输入这个迷宫的值，1代表可以通过的，0代表不可以通过的：" << endl;
    for (int i = 1; i <= total.m; i++) {
        for (int j = 1; j <= total.n; j++) {
            scanf_s("%d", &total.app[i][j]);
        }
    }
    cout << "请输入起点的值 (x1, y1): ";
    cin >> total.x1 >> total.y1;
    cout << "请输入终点的值 (x2, y2): ";
    cin >> total.x2 >> total.y2;
    if (total.x1 < 1 || total.x1 > total.m || total.y1 < 1 || total.y1 > total.n || total.app[total.x1][total.y1] == 0) {
        cout << "起点不合法!" << endl;
        return 0;
    }
    if (total.x2 < 1 || total.x2 > total.m || total.y2 < 1 || total.y2 > total.n || total.app[total.x2][total.y2] == 0) {
        cout << "终点不合法!" << endl;
        return 0;
    }
    bfs(total);
    return 0;
}

参考数据:

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

参考结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
请输入这个迷宫的长和宽 m 与 n：
10 10
请输入这个迷宫的值，1代表可以通过的，0代表不可以通过的：
1 1 1 1 1 0 1 1 1 1
0 0 0 1 0 0 0 0 1 1
1 1 1 1 1 1 1 0 1 0
1 0 0 0 0 0 1 0 1 0
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 1 1 1 1 1 1 0 1
1 0 1 0 0 0 0 1 0 1
1 1 1 1 1 1 0 1 1 1
0 0 0 0 0 1 1 1 1 1
请输入起点的值 (x1, y1): 1 1
请输入终点的值 (x2, y2): 10 10
走出了迷宫!
共走了: 18 步
走过的路径为:这个的走过的路径为:(1,1)-->(1,2)-->(1,3)-->(1,4)-->(2,4)-->(3,4)-->(3,5)-->(3,6)-->(3,7)-->(4,7)-->(5,7)-->(5,8)-->(5,9)-->(5,10)-->(6,10)-->(7,10)-->(8,10)-->(9,10)-->(10,10)-->endl

参考数据:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
15 15
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 1 1 1 1 1 1 1 1 1 1 1 0 1
1 0 1 0 0 0 0 0 0 0 0 0 1 0 1
1 0 1 0 1 1 1 1 1 1 1 0 1 0 1
1 0 1 0 1 0 0 0 0 0 1 0 1 0 1
1 0 1 0 1 0 1 1 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 1 1 0 1 0 1 0 1
1 0 1 0 0 0 0 0 0 0 1 0 1 0 1
1 0 1 1 1 1 1 1 1 1 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1
15 15

参考结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
请输入这个迷宫的长和宽 m 与 n：
15 15
请输入这个迷宫的值，1代表可以通过的，0代表不可以通过的：
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 1 1 1 1 1 1 1 1 1 1 1 0 1
1 0 1 0 0 0 0 0 0 0 0 0 1 0 1
1 0 1 0 1 1 1 1 1 1 1 0 1 0 1
1 0 1 0 1 0 0 0 0 0 1 0 1 0 1
1 0 1 0 1 0 1 1 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 1 1 0 1 0 1 0 1
1 0 1 0 0 0 0 0 0 0 1 0 1 0 1
1 0 1 1 1 1 1 1 1 1 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
请输入起点的值 (x1, y1): 1 1
请输入终点的值 (x2, y2): 15 15
走出了迷宫!
共走了: 28 步
走过的路径为:这个的走过的路径为:(1,1)-->(1,2)-->(1,3)-->(1,4)-->(1,5)-->(1,6)-->(1,7)-->(1,8)-->(1,9)-->(1,10)-->(1,11)-->(1,12)-->(1,13)-->(1,14)-->(1,15)-->(2,15)-->(3,15)-->(4,15)-->(5,15)-->(6,15)-->(7,15)-->(8,15)-->(9,15)-->(10,15)-->(11,15)-->(12,15)-->(13,15)-->(14,15)-->(15,15)-->endl

参考不通过数据:

1
2
3
4
5
6
7
8
9
10
7 7
1 1 1 1 0 0 0
1 0 0 1 0 1 1
1 0 1 1 1 1 0
1 0 0 0 0 1 0
1 1 1 1 0 1 0
0 0 0 0 0 0 0
0 0 0 1 1 1 1
1 1
7 7

参考结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
请输入这个迷宫的长和宽 m 与 n：
7 7
请输入这个迷宫的值，1代表可以通过的，0代表不可以通过的：
1 1 1 1 0 0 0
1 0 0 1 0 1 1
1 0 1 1 1 1 0
1 0 0 0 0 1 0
1 1 1 1 0 1 0
0 0 0 0 0 0 0
0 0 0 1 1 1 1
请输入起点的值 (x1, y1): 1 1
请输入终点的值 (x2, y2): 7 7
没有走出迷宫