2023面试高手

这个屌丝很懒，什么也没留下！

热门标签

图的遍历和Prim最小生成树(万字总结)_图的遍历及最小生成树

作者：2023面试高手 | 2024-05-26 16:40:47

踩

图的遍历及最小生成树

图的遍历和Prim最小生成树

文章目录

图的遍历和Prim最小生成树

通常来说图有邻接矩阵(即二维数组)和邻接表(即多重链表)表示，如图：

邻接矩阵：

邻接矩阵

邻接表：

邻接表

一、邻接矩阵表示法

1.1图的深度优先遍历

1.1.1 递归

例如下图：表示出发点从A开始的递归树

DFS

深度优先搜索DFS，在树和图中其实本质是一样的，可以说树是一种特殊的图，在二叉树(链式存储结构)中，每个结点含有两个指针，分别指向左、右孩子，当然如果没有左右孩子结点则将该指针域置空。遍历时仅需考虑两种情况：1.往左走进入左子树 2.往右走进入右子树，知道指针域为空，则回溯。而在图中，一个结点可能会连接巨多结点，而每一个结点的出度又不尽相同，所以需要提前在建图的时候把所有顶点存入，那么在接下来的遍历中，依次判断与其他顶点的关系，如果是相连的，就可以从走到该节点，如此往复。当然，遍历要求要做到每个节点不重不漏的访问，那么则需要标记数组的记录，对于非连通图，需要依次枚举各个顶点以确保不重不漏。

完整代码如下：

从某点开始进行深度优先遍历

#include <bits/stdc++.h>

using namespace std;

const int MVNum = 500;

bool visited[MVNum];//标记数组，初始化为未访问false

typedef struct 
{
    char vexs[MVNum];
    int arcs[MVNum][MVNum];
    int vexnum, arcnum;

}AMGraph;

int Locatevex(AMGraph &G, char ch)
{
	for (int i = 1; i <= G.vexnum; ++ i) {
		if (G.vexs[i] == ch) return i;
	}
	return 0;
}

void CreateUDN(AMGraph &G)
{
    //cout << "请输入点数目和边数：" << endl; 
    cin >> G.vexnum >> G.arcnum;//输入顶点数目和边数，空格隔开
    
    // cout << "请依次输入各个顶点 ：" << endl;
    for (int i = 1; i <= G.vexnum; ++ i) 
        cin >> G.vexs[i];//依次输入各个顶点
    
    for (int i = 1; i <= G.vexnum; ++ i) 
        for (int j = 1; j <= G.vexnum; ++ j) 
            G.arcs[i][j] = 0;//对边初始化 
    //  cout << "请输入两顶点，建立边关系 ：" << endl;   
    for (int i = 1; i <= G.arcnum; ++ i) 
    {
        char v1, v2; 
        cin >> v1 >> v2;//输入两顶点，建立边关系 
        //寻找两个顶点在存入顶点数组中的位置
        int x1 = Locatevex(G, v1);
        int x2 = Locatevex(G, v2);
        G.arcs[x1][x2] = G.arcs[x2][x1] = 1;
    }
    return;
}

void DFS(AMGraph &G, int x)
{   
    //访问输出该顶点，标记为已访问
    cout << G.vexs[x] << ' ';
    visited[x] = true;

    for (int j = 1; j <= G.vexnum; ++ j)
    {   //如果与下一个点有联系且没有访问，则访问下一个点
        if (G.arcs[x][j] && !visited[j]) DFS(G, G.vex[j]);
    }
    return;
}

int main()
{
    AMGraph G;

    CreateUDN(G);

/*  打印建立的二维矩阵 
    for (int i = 1; i <= G.vexnum; ++ i) {
        for (int j = 1; j <= G.vexnum; ++ j) cout << G.arcs[i][j] << ' ';
        cout << endl;
    }
*/ 
    char v; cin >> v;//若为非连通图，则删此行，改DFS为DFS_ALL
    DFS(G, v);
    system("pause");

    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

运行结果如下：

对于非连通图，加上这个函数，主函数直接调用即可

void DFS_ALL(AMGraph &G)
{
    for (int i = 1; i <= G.vexnum; ++ i)
       if (!visited[i]) DFS(G, i);
}
1
2
3
4
5

运行结果如下：

1.1.2 非递归

从某点开始进行深度优先遍历

//直接把上面的DFS函数改了即可，需要引用头文件stack
//#include <stack>或引用万能头文件#include <bits/stdc++.h>
void DFS(AMGraph &G, char v)
{
	stack <char> S;
	S.push(v);
    while (!S.empty())
    {
        char c = S.top(); S.pop();//取出栈顶元素 
        int x = Locatevex(G, c);//对该元素定位 
        if (!visited[x]) {
        	cout << c << " "; visited[x] = true;//输出该元素 
	        for (int j = 1; j <= G.vexnum; ++ j) {
	        	if (G.arcs[x][j] && !visited[j]) {
	        		//将该元素所有相关联的点入栈 
                    S.push(G.vexs[j]);
				}
		    }
		}
        
    }
    return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

运行结果如下：

对于非连通图，DFS_ALL函数完全同上

运行结果如下：

1.2、图的广度优先遍历

例如下图：

BFS

类似于树的层序遍历，在图中也是一层一层地访问。代码方面直接将DFS非递归中栈改成队列即可，BFS函数如下：(从某点开始)

//需要引用头文件#include <queue>
//或引用万能头文件#include <bits/stdc++.h>
void BFS(AMGraph &G, char v)
{
	queue <char> Q;
	Q.push(v);
    while (!Q.empty())
    {
        char c = Q.front(); Q.pop();//取出队头元素 
        int x = Locatevex(G, c);//对该元素定位 
        if (!visited[x]) {
        	cout << c << " "; visited[x] = true;//输出该元素 
	        for (int j = 1; j <= G.vexnum; ++ j) {
	        	if (G.arcs[x][j] && !visited[j]) {
	        		Q.push(G.vexs[j]);
                    //将该元素所有相关联的点入队
				}
			}
		}
    }
    return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

运行结果：

1.3、Prim最小生成树

完整代码如下：

#include <bits/stdc++.h>

using namespace std;

const int MVNum = 500, MaxInt = 0x7fffffff;

typedef struct 
{
    char vexs[MVNum];
    int arcs[MVNum][MVNum];
    int vexnum, arcnum;

}AMGraph;

struct Node 
{
	char adjvex;
	int lowcost;
}closedge[MVNum];

int Locatevex(AMGraph G, char ch)
{
	for (int i = 1; i <= G.vexnum; ++ i) {
		if (G.vexs[i] == ch) return i;
	}
	return 0;
}

void CreatUDN(AMGraph &G)
{
	cout << "请输入点数目和边数：" << endl; 
    cin >> G.vexnum >> G.arcnum;
    char v1, v2; int w;
    cout << "请依次输入各个顶点编号 ：" << endl; 
    for (int i = 1; i <= G.vexnum; ++ i) cin >> G.vexs[i];
    for (int i = 1; i <= G.vexnum; ++ i) 
        for (int j = 1; j <= G.vexnum; ++ j) G.arcs[i][j] = MaxInt;//初始化无穷大 
    cout << "请输入两顶点，建立边关系 ：" << endl;  
    for (int i = 1; i <= G.arcnum; ++ i) {
        cin >> v1 >> v2 >> w;
        int x1 = Locatevex(G, v1);
        int x2 = Locatevex(G, v2);
        G.arcs[x1][x2] = G.arcs[x2][x1] = w;
    }
    return;
}

int Min(AMGraph &G)
{
    int res = MaxInt, x = 0;
    for (int i = 1; i <= G.vexnum; ++ i) {
        if (closedge[i].lowcost) {
            if (closedge[i].lowcost < res) {
                res = closedge[i].lowcost; x = i;
            }    
        }
    }
    return x;
}

void MiniSpanTree_Prim(AMGraph &G)
{
    int t = 0; char v;
    cout << "请输入出发点：" << endl; 
    cin >> v;
    int k = Locatevex(G, v); 
    for (int j = 1; j <= G.vexnum; ++ j) 
        if (j != k) {
        	 closedge[j].adjvex = v;
			 closedge[j].lowcost =  G.arcs[k][j];
		}

    closedge[k].lowcost = 0;

    for (int i = 1; i < G.vexnum; ++ i)
    {
        k = Min(G);

        char u0 = closedge[k].adjvex;
        char v0 = G.vexs[k];
        
        cout << u0 << ' ' << v0 << endl;

        closedge[k].lowcost = 0;
        for (int j = 1; j <= G.vexnum; ++ j) {
            if (G.arcs[k][j] < closedge[j].lowcost) {
            	closedge[j].adjvex = G.vexs[k];
            	closedge[j].lowcost = G.arcs[k][j];
			}
		}
    }
    
    return;
}

int main()
{
    AMGraph G;
    CreatUDN(G);
    
    MiniSpanTree_Prim(G);
    
    system("pause");

    return 0;
}
/*测试用例：
6 10
ABCDEF
A B 6
A D 5
A C 1
B C 5
B E 3
C D 5
C E 6
C F 4
D F 2
E F 6
*/
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

运行结果如下：

二、邻接表表示法

2.1图的深度优先遍历

2.1.1 递归

从某点开始进行深度优先遍历

#include <bits/stdc++.h>

using namespace std;

const int MVNum = 500;
bool visited[MVNum];

typedef struct ArcNode
{
	int adjvex;
	struct ArcNode * nextarc; 
}ArcNode;

typedef struct VNode
{
	char data;
	ArcNode * firstarc;
}VNode, AdjList[MVNum];

typedef struct
{
	AdjList vertices;
	int vexnum, arcnum;
}ALGraph;

int LocateVex(ALGraph G, char v)
{
	for (int i = 1; i <= G.vexnum; ++ i) {
		if (G.vertices[i].data == v) {
			return i;
		}
	}
	return 0;
}

void CreateUDG(ALGraph &G)
{
	cout << "请输入点数目和边数：" << endl; 
    cin >> G.vexnum >> G.arcnum;//输入顶点数目和边数，空格隔开 
    cout << "请依次输入各个顶点 ：" << endl; 
    for (int i = 1; i <= G.vexnum; ++ i) {
	    cin >> G.vertices[i].data;//依次输入各个顶点
	    G.vertices[i].firstarc = NULL;
    }
    char v1, v2;
    for (int k = 0; k < G.arcnum; ++ k) {
    	cin >> v1 >> v2;
    	int i = LocateVex(G, v1);
    	int j = LocateVex(G, v2);
    	ArcNode* p1 = new ArcNode;
    	p1->adjvex = j;
		p1->nextarc = G.vertices[i].firstarc;
		G.vertices[i].firstarc = p1;
		
		ArcNode* p2 = new ArcNode;
    	p2->adjvex = i;
		p2->nextarc = G.vertices[j].firstarc;
		G.vertices[j].firstarc = p2;
	}
	return;
}

void DFS(ALGraph &G, char v)
{
	cout << v << ' ';
	int x = LocateVex(G, v);
	visited[x] = true;
	
	ArcNode* p = G.vertices[x].firstarc;
	while (p)
	{
		int k = p->adjvex;
		if (!visited[k]) DFS(G, G.vertices[k].data);
		p = p->nextarc;
	}
} 

int main()
{
	ALGraph G;
	CreateUDG(G);
	
    char v; cin >> v;//若为非连通图，则删此行，改DFS为DFS_ALL
    DFS(G, v);
	
	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

运行结果如下：

对于非连通图，DFS_ALL函数如下：

void DFS_ALL(ALGraph &G)
{
	for (int i = 1; i <= G.vexnum; ++ i) {
		if (!visited[i]) {
			DFS(G, G.vertices[i].data);
		}
	}
	return;
}
1
2
3
4
5
6
7
8
9

运行结果如下：

2.1.2 非递归

从某点开始进行深度优先遍历

void DFS(ALGraph &G, char v)
{	
    stack <char> S;
	S.push(v);
	while (!S.empty()) 
	{
		char ch = S.top(); S.pop();
		int x = LocateVex(G, ch);
		
		if (!visited[x])
		{
			cout << ch << ' ';
		    visited[x] = true;
			ArcNode* p = G.vertices[x].firstarc;
			while (p)
			{
				int k = p->adjvex;
				if (!visited[k])
                    S.push(G.vertices[k].data);
				p = p->nextarc;
			}
		}
	}	
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

运行结果如下：

对于非连通图，DFS_ALL函数完全同上

运行结果如下：

2.2、图的广度优先遍历

将DFS非递归中栈改成队列即可，BFS函数如下：(从某点开始)

void BFS(ALGraph &G, char v)
{	
    queue <char> Q;
	Q.push(v);
	while (!Q.empty()) 
	{
		char ch = Q.front(); Q.pop();
		int x = LocateVex(G, ch);
		
		if (!visited[x])
		{
			cout << ch << ' ';
		    visited[x] = true;
			ArcNode* p = G.vertices[x].firstarc;
			while (p)
			{
				int k = p->adjvex;
				if (!visited[k])
                    Q.push(G.vertices[k].data);
				p = p->nextarc;
			}
		}
	}	
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2.3、Prim最小生成树

完整代码如下：

#include <bits/stdc++.h>

using namespace std;

const int MVNum = 500, MaxInt = 0x7fffffff;

typedef struct ArcNode
{
	int adjvex, weight;
	struct ArcNode * nextarc; 
}ArcNode;

typedef struct VNode
{
	char data;
	ArcNode * firstarc;
}VNode, AdjList[MVNum];

typedef struct
{
	AdjList vertices;
	int vexnum, arcnum;
}ALGraph;

struct Node 
{
	char adjvex;
	int lowcost;
}closedge[MVNum];

int LocateVex(ALGraph G, char ch)
{
	for (int i = 1; i <= G.vexnum; ++ i) {
		if (G.vertices[i].data == ch) return i;
	}
	return 0;
}

void CreateUDG(ALGraph &G)
{
	cout << "请输入点数目和边数：" << endl; 
    cin >> G.vexnum >> G.arcnum;//输入顶点数目和边数，空格隔开 
    cout << "请依次输入各个顶点 ：" << endl; 
    for (int i = 1; i <= G.vexnum; ++ i) {
	    cin >> G.vertices[i].data;//依次输入各个顶点
	    G.vertices[i].firstarc = NULL;
    }
    char v1, v2; int w;
    for (int k = 0; k < G.arcnum; ++ k) {
    	cin >> v1 >> v2 >> w;
    	int i = LocateVex(G, v1);
    	int j = LocateVex(G, v2);
    	ArcNode* p1 = new ArcNode;
    	p1->adjvex = j; p1->weight = w;
		p1->nextarc = G.vertices[i].firstarc;
		G.vertices[i].firstarc = p1; 
		
		ArcNode* p2 = new ArcNode;
    	p2->adjvex = i; p2->weight = w;
		p2->nextarc = G.vertices[j].firstarc;
		G.vertices[j].firstarc = p2;
	}
	return;
}

int Min(ALGraph &G)
{
    int res = MaxInt, x = 0;
    for (int i = 1; i <= G.vexnum; ++ i) {
        if (closedge[i].lowcost) {
            if (closedge[i].lowcost < res) {
                res = closedge[i].lowcost; x = i;
            }    
        }
    }
    return x;
}

void MiniSpanTree_Prim(ALGraph &G)
{
    int t = 0; char v;
    cout << "请输入出发点：" << endl; 
    cin >> v;
    int k = LocateVex(G, v); 
    for (int i = 1; i <= G.vexnum; ++ i) {
    	closedge[i].lowcost = MaxInt;
	}
    ArcNode *p = G.vertices[k].firstarc;
    while (p) {
    	closedge[p->adjvex].adjvex = v;
    	closedge[p->adjvex].lowcost = p->weight;
    	p = p->nextarc;
	}
    closedge[k].lowcost = 0;
    for (int i = 1; i < G.vexnum; ++ i)
    {
        k = Min(G);

        char u0 = closedge[k].adjvex;
        char v0 = G.vertices[k].data;
        
        cout << u0 << ' ' << v0 << endl;
        closedge[k].lowcost = 0;
        ArcNode *q = G.vertices[k].firstarc;
        while (q) {
        	if (q->weight < closedge[q->adjvex].lowcost)
        	{
        		closedge[q->adjvex].adjvex = G.vertices[k].data;
        		closedge[q->adjvex].lowcost = q->weight;
			}
			q = q->nextarc;
		}
    }
    
    return;
}

int main()
{
    ALGraph G;
    CreateUDG(G);
    
    MiniSpanTree_Prim(G);
    
    system("pause");

    return 0;
}
/*测试用例：
6 10
ABCDEF
A B 6
A D 5
A C 1
B C 5
B E 3
C D 5
C E 6
C F 4
D F 2
E F 6
*/
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

运行结果如下：

THEEND…

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/627491