数据结构-图及最小生成树
好久没更了 其实摸鱼摸太久了，当然也是最近太多事，一直没有时间去打理博客，趁着周末有空，来整理下图部分的内容
这里来总结下无向图、最小生成树(prim和Dijkstra)算法
无向图
结构
const int maxSize = 100;
int visited[maxSize] = {0}; // 到后面发现，visited在无向图中设计的是真的巧妙
template <class DataType>
class MGraph {
public:
MGraph(DataType a[], int n, int e); // 构造函数，构造有n个顶点e条边的图
~MGraph() {}
void DFS(int); // 深搜
void BFS(int); // 广搜
private:
DataType vertex[maxSize]; // 存放图中顶点的数组
int edge[maxSize][maxSize]; // 存放图中边的数组
int vertexNum, edgeNum; // 图中的顶点数和变数
};构造函数
template <class DataType>
MGraph<DataType>::MGraph(DataType a[], int n, int e) {
int i, j, k;
vertexNum = n;
edgeNum = e;
for (i = 0; i < vertexNum; i++) {
vertex[i] = a[i]; // 储存顶点
}
for (i = 0; i < vertexNum; i++) {
for (j = 0; j < vertexNum; j++) {
edge[i][j] = 0; // 初始化邻接矩阵
}
}
for (k = 0; k < edgeNum; k++) {
cin >> i >> j; // 以此输入每条边依附的两个顶点的编号
edge[i][j] = 1; // 对输入的边做标记(无向图，双向标记)
edge[j][i] = 1;
}
}广搜和深搜
template <class DataType>
void MGraph<DataType>::DFS(int v) {
cout << vertex[v];
visited[v] = 1;
for (int j = 0; j < vertexNum; j++) {
if (edge[v][j] == 1 && visited[j] == 0)
DFS(j);
// 递归的妙处会在后面讲到
}
}
template <class DataType>
void MGraph<DataType>::BFS(int v) {
int w, j, queue[maxSize] = {0}; // queue数组记录的是访问矩阵第几行的顺序
for (int i = 0; i < vertexNum; i++) {
visited[i] = 0;
}
int front = -1, rear = -1;
cout << vertex[v];
visited[v] = 1;
queue[++rear] = v;
while (front != rear) {
v = queue[++front];
for (j = 0; j < vertexNum; j++) {
if (edge[v][j] == 1 && visited[j] == 0) {
cout << vertex[j];
visited[j] = 1;
queue[++rear] = j;
}
}
}
}主函数
int main() {
char ch[] = {'a', 'b', 'c', 'd', 'e', 'f'};
MGraph<char> MG(ch, 6, 6);
for (int i = 0; i < maxSize; i++) {
visited[i] = 0;
}
cout << "DFS order: \n";
MG.DFS(0);
cout << "\n================\n";
cout << "BFS order: \n";
MG.BFS(0);
}测试用例及其邻接矩阵
测试数据
0 1
0 2
0 5
1 2
1 4
3 4邻接矩阵
0 1 2 3 4 5
0' 1 1 1 '
1' 1 1 1 '
2' 1 1 '
3' 1 '
4' 1 1 '
5' 1 '
// 以横轴为x，竖轴为y 借用这个样例来说一下深搜和广搜
深搜
已知无向图的邻接矩阵是关于对角线对称的，深搜从第一行开始搜索，搜索到(1,0)时进入递归，进入递归后，首先对visited[v]进行标记，通过观察可以知道，上一轮DFS传入的j和下一轮DFS的v在矩阵中关于对角线对称 好像是个无用信息，每一轮DFS的visited[v]=1就是为了避免重复访问vertex[v]，再加上那条if语句的配合，即可无重复遍历完整个图
广搜
广搜的话其实还是要自己画出一个无向图来并且在debug模式运行一遍才知道大概是怎么个流程。对上面的测试用例来说，在第一轮搜索时，访问的都是和0号这个点有通路的点，第二轮是1号，第三轮是2号，依此类推。如果把最开始输入的0号放在中间，后面输入的数据一圈圈和0号联通，产生关联，那么广搜可以理解为，从搜寻点一圈圈向外扩散找
完整代码
#include <bits/stdc++.h>
using namespace std;
const int maxSize = 100;
int visited[maxSize] = {0};
template <class DataType>
class MGraph {
public:
MGraph(DataType a[], int n, int e);
~MGraph() {}
void DFS(int);
void BFS(int);
private:
int vertex[maxSize];
int edge[maxSize][maxSize];
int vertexNum, edgeNum;
};
template <class DataType>
MGraph<DataType>::MGraph(DataType a[], int n, int e) {
int i, j, k;
vertexNum = n;
edgeNum = e;
for (i = 0; i < vertexNum; i++) {
vertex[i] = a[i];
}
for (i = 0; i < vertexNum; i++) {
for (j = 0; j < vertexNum; j++) {
edge[i][j] = 0;
}
}
for (k = 0; k < edgeNum; k++) {
cin >> i >> j;
edge[i][j] = 1;
edge[j][i] = 1;
}
}
template <class DataType>
void MGraph<DataType>::DFS(int v) {
cout << vertex[v];
visited[v] = 1;
for (int j = 0; j < vertexNum; j++) {
if (edge[v][j] == 1 && visited[j] == 0)
DFS(j);
}
}
template <class DateType>
void MGraph<DataType>::BFS(int v) {
int w, j, queue[maxSize] = {0};
for (int i = 0; i < vertexNum; i++) {
visited[i] = 0;
}
int front = -1, rear = -1;
cout << vertex[v];
queue[++rear] = v;
while (front != rear) {
v = queue[++front];
for (j = 0; j < vertexNum; j++) {
if (edge[v][j] == 1 && visited[j] == 0) {
cout << vertex[j];
visited[j] = 1;
queue[++rear] = j;
}
}
}
}
int main() {
char ch[] = {'a', 'b', 'c', 'd', 'e', 'f'};
int i;
MGraph<char> MG(ch, 6, 6);
for (i = 0; i < maxSize; i++) {
visited[i] = 0;
}
cout << "DFS order: \n";
MG.DFS(0);
cout << "\n================\n";
cout << "BFS order: \n";
MG.BFS(0);
}prim
结构
const int maxSize = 100;
int visited[maxSize] = {0};
template <class DataType>
class MGraph {
public:
MGraph(DataType a[], int n, int e);
~MGraph() {}
void DFS(int);
void BFS(int);
void Prim(int);
int minEdge(int[], int);
private:
DataType vertex[maxSize];
int edge[maxSize][maxSize];
int vertexNum, edgeNum;
};构造函数
template <class DataType>
MGraph<DataType>::MGraph(DataType a[], int n, int e) {
int i, j, w = 0;
vertexNum = n;
edgeNum = e;
for (i = 0; i < vertexNum; i++) {
vertex[i] = a[i];
}
for (i = 0; i < vertexNum; i++) {
for (j = 0; j < vertexNum; j++) {
if (i == j)
edge[i][j] = 0; // 这里忽略自环
else
edge[i][j] = 100;
// 这里初始化权值，赋比较大的数即可
}
}
for (int k = 0; k < edgeNum; k++) {
cout << "input two points of the edge: ";
cin >> i >> j;
cout << "input the weight of the edge: " ;
cin >> w;
edge[i][j] = w;
edge[j][i] = w;
}
}prim代码实现
将图中顶点（V）分两部分，最小生成树的点集为U，其余顶点在集合（V-U）
- 首先任取一个点作为起点
- 在V-U中找和起点之间权值最小的边
- adjVex记录上一轮找最小值的位置，cost记录到各顶点的距离
- 然后上一轮找到的权值最小的边的另一个点作为起点，不断重复步骤2，3
找到最小值位置
template <class DataType>
int MGraph<DataType>::minEdge(int r[], int n) {
int index;
int min = 100; // 图中all权值最大不超过100
for (int i = 0; i < n; i++) {
if (r[i] != 0 && r[i] < min) {
min = r[i];
index = i;
}
}
return index; // 返回最小值在数组中的位置
}prim核心代码
template <class DataType>
void MGraph<DataType>::Prim(int v) {
int adjVex[maxSize], cost[maxSize];
int i, j, k;
for (i = 0; i < vertexNum; i++) {
// 通过起点对adjVex，cost数组初始化
cost[i] = edge[v][i];
adjVex[i] = v;
// 将起点所有有联通的点都录入cost中，找权值最小的边(类似BFS)
}
cost[v] = 0; // 将顶点加入u中
for (k = 1; k < vertexNum; k++) {
j = minEdge(cost, vertexNum); // 在cost数组找最小值
// cout << '(' << adjVex[j] << ',' << j << ')' << cost[j] << endl; // 输出的是点的序号
cout << '(' << vertex[j] << ',' << vertex[adjVex[j]] << ')' << cost[j] << endl; // 输出的是字符
// 输出生成最小生成树的过程(都是输出上一轮查找结果)
cost[j] = 0; // 将最小值的点加入U中(清零当前最小值的权值，防止后面重复遍历)
for (int p = 0; p < vertexNum; p++) {
// 这一步，是以第j号为起点，不断寻找和j号联通的最小权值的路线
if (edge[p][j] < cost[p]) {
// 从所有与当前最小值临界点出发找到最小值点权值最小的
cost[p] = edge[p][j];
adjVex[p] = j; // 记录新加入顶点上一轮迭代的最小值的位置
}
}
}
}测试用例及邻接矩阵
0 1
34
0 2
46
0 5
19
1 4
12
2 3
17
2 5
25
3 4
38
3 5
25
4 5
26 0 1 2 3 4 5
0' 34 46 19 '
1' 34 12 '
2' 46 17 25 '
3' 17 38 '
4' 12 38 26 '
5' 19 25 26 '
// 以横轴为x，竖轴为y Dijkstra
结构
const int maxSize = 100;
int visited[maxSize] = {0}; // 到后面发现，visited在无向图中设计的是真的巧妙
template <class DataType>
class MGraph {
public:
MGraph(DataType a[], int n, int e); // 构造函数，构造有n个顶点e条边的图
~MGraph() {}
void DFS(int); // 深搜
void BFS(int); // 广搜
private:
DataType vertex[maxSize]; // 存放图中顶点的数组
int edge[maxSize][maxSize]; // 存放图中边的数组
int vertexNum, edgeNum; // 图中的顶点数和变数
};构造函数
template <class DataType>
MGraph<DataType>::MGraph(DataType a[], int n, int e) {
vertexNum = e, edgeNum = n;
int i, j, w = 0;
for (i = 0; i < vertexNum; i++) {
vertex[i] = a[i];
}
for (i = 0; i < vertexNum; i++) {
for (j = 0; j < vertexNum; j++) {
if (i == j)
edge[i][j] = 0;
else
edge[i][j] = 100;
}
for (int k = 0; k < edgeNum; k++) {
cout << "input two vertexes of the edge: ";
cin >> i >> j;
cout << "input the weight of the edge: ";
cin >> w;
edge[i][j] = w;
}
}
}
深搜和广搜
template <class DataType>
void MGraph<DataType>::DFS(int v) {
cout << vertex[v];
visited[v] = 1;
for (int i = 0; i < vertexNum; i++) {
if (edge[v][i] < 100 && visited[i] == 0)
DFS(i);
}
}
template <class DataType>
void MGraph<DataType>::BFS(int v) {
int queue[maxSize];
int front = -1, rear = -1;
cout << vertex[v];
visited[v] = 1;
queue[++rear] = v;
while (front != rear) {
v = queue[++front];
for (int j = 0; j < vertexNum; j++) {
if (edge[v][j] < 100 && visited[j] == 0) {
cout << vertex[v];
visited[j] = 1;
queue[++rear] = 1;
}
}
}
}Dijkstra
template <class DataType>
void MGraph<DataType>::Dijkstra(MGraph<DataType> mg, int v) {
int dist[maxSize];
// dist为起点到各个点的距离，具有临时性
string path[maxSize];
string vertex(mg.vertex);
for (int i = 0; i < mg.vertexNum; i++) {
dist[i] = mg.edge[v][i];
// 初始化dist数组，0号顶点到其余各顶点的初始路程
if (dist[i] != 100) {
path[i] += vertex[v];
path[i] += vertex[i];
// 这里是记录起点可以直达的路径
} else {
path[i] = "";
}
}
dist[v] = 0;
int num = 1;
while (num < mg.vertexNum) {
int min = 255, k = 0; // 每一轮重置最小值
for (int i = 0; i < mg.vertexNum; i++) {
if (dist[i] != 0 && dist[i] < min) {
min = dist[i];
k = i;
// 找最小值
}
}
// cout << path[k] << ',' << dist[k] << ";\n";
num++; // 标记这是第几个被访问的点
for (int i = 0; i < mg.vertexNum; i++) {
if (dist[i] > dist[k] + mg.edge[k][i]) {
dist[i] = dist[k] + mg.edge[k][i];
path[i] = ""; // 重置路径
path[i] += path[k]; // 加上之前走过的路
path[i] += vertex[i];
}
}
cout << path[k] << ',' << dist[k] << ";\n";
dist[k] = 0;
}
}测试用例及邻接矩阵
0 1
10
0 3
30
0 4
100
1 2
50
2 4
10
3 2
20
3 4
60 0 1 2 3 4
0
1' 10 '
2' 50 20 '
3' 30 '
4' 100 10 60 '
// 横轴为x，竖轴为y 完整代码
#include <bits/stdc++.h>
using namespace std;
const int maxSize = 100;
int visited[maxSize] = {0};
template <class DataType>
struct MGraph {
public:
MGraph(DataType a[], int n, int e);
~MGraph() {}
void DFS(int);
void BFS(int);
void Dijkstra(MGraph<DataType>, int);
private:
DataType vertex[maxSize];
int edge[maxSize][maxSize];
int vertexNum, edgeNum;
};
template <class DataType>
MGraph<DataType>::MGraph(DataType a[], int n, int e) {
int i, j, w = 0;
vertexNum = n, edgeNum = e;
for (i = 0; i < vertexNum; i++) {
vertex[i] = a[i];
}
for (i = 0; i < vertexNum; i++) {
for (j = 0; j < vertexNum; j++) {
if (i == j)
edge[i][j] = 0;
else
edge[i][j] = 100;
}
}
for (int k = 0; k < edgeNum; k++) {
cout << "input two vertexes of the edge: ";
cin >> i >> j;
cout << "input the weight of the edge: ";
cin >> w;
edge[i][j] = w;
}
}
template <class DataType>
void MGraph<DataType>::DFS(int v) {
cout << vertex[v];
visited[v] = 1;
for (int i = 0; i < vertexNum; i++) {
if (edge[v][i] < 100 && visited[i] == 0)
DFS(i);
}
}
template <class DataType>
void MGraph<DataType>::BFS(int v) {
int queue[maxSize];
int front = -1, rear = -1;
cout << vertex[v];
visited[v] = 1;
queue[++rear] = v;
while (front != rear) {
v = queue[++front];
for (int j = 0; j < vertexNum; j++) {
if (edge[v][j] < 100 && visited[j] == 0) {
cout << vertex[j];
visited[j] = 1;
queue[++rear] = j;
}
}
}
}
template <class DataType>
void MGraph<DataType>::Dijkstra(MGraph<DataType> mg, int v) {
int distance[maxSize];
string path[maxSize];
string vertex(mg.vertex);
for (int i = 0; i < mg.vertexNum; i++) {
distance[i] = mg.edge[v][i];
if (dist[i] != 100) {
path[i] += vertex[v];
path[i] += vertex[i];
} else {
path[i] = "";
}
}
distance[v] = 0;
int num = 1;
while (num < mg.vertexNum) {
int min = 100, k = 0;
for (int i = 0; i < mg.vertexNum; i++) {
if (distance[i] != 0 && distance[i] < min) {
min = distance[i];
k = i;
}
}
num++;
for (int i = 0; i < mg.vertexNum; i++) {
if (distance[i] > distance[k] + mg.edge[v][i]) {
distance[i] = distance[i] + mg.edge[k][i];
path[i] = "";
path[i] += path[k];
path[i] += vertex[i];
}
}
cout << path[k] << ',' << distance[k] << ";\n";
distance[k] = 0;
}
}
int main() {
char ch[] = {'a', 'b', 'c', 'd', 'e'};
MGraph<char> mg(ch, 5, 7);
for (int i = 0; i < maxSize; i++) {
visited[i] = 0;
}
cout << "DFS: ";
mg.DFS(0);
cout << endl;
for (int i = 0; i < maxSize; i++) {
visited[i] = 0;
}
cout << "BFS: ";
mg.BFS(0);
cout << "the short path: \n";
mg.Dijkstra(mg, 0);
}