【数据结构】图的连通性应用

Alex_Shen
2020-11-24 / 0 评论 / 0 点赞 / 59 阅读 / 9,001 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-04-06,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

问题 A: DS图—最小生成树

题目描述

根据输入创建无向网。分别用Prim算法和Kruskal算法构建最小生成树。(假设:输入数据的最小生成树唯一。)

输入

顶点数n
n个顶点
边数m
m条边信息,格式为:顶点1 顶点2 权值
Prim算法的起点v

输出

输出最小生成树的权值之和
对两种算法,按树的生长顺序,输出边信息(Kruskal中边顶点按数组序号升序输出)

样例输入

6
v1 v2 v3 v4 v5 v6
10
v1 v2 6
v1 v3 1
v1 v4 5
v2 v3 5
v2 v5 3
v3 v4 5
v3 v5 6
v3 v6 4
v4 v6 2
v5 v6 6
v1

样例输出

15
prim:
v1 v3 1
v3 v6 4
v6 v4 2
v3 v2 5
v2 v5 3
kruskal:
v1 v3 1
v4 v6 2
v2 v5 3
v3 v6 4
v2 v3 5

题解

#include<iostream>
#include<vector>
#include<algorithm>
#define MaxLen 20
#define Infinity 99999 

using namespace std;

class Map {
private:
	bool Visit[MaxLen];
	string node[MaxLen];
	int Matrix[MaxLen][MaxLen];
	int Vexnum;
public:
	void SetMatrix() {
		cin >> Vexnum;
		for (int i = 0; i < Vexnum; i++)
			cin >> node[i];
		for (int i = 0; i < Vexnum; i++)
			for (int j = 0; j < Vexnum; j++)
				Matrix[i][j] = 0;
	}
	void SetWeight(){
		int t;
		cin >> t;
		string node1, node2;
		int weight;
		int i, j;
		while (t--) {
			cin >> node1 >> node2 >> weight;
			i = FindNodeIndex(node1);
			j = FindNodeIndex(node2);
			Matrix[i][j] = weight;
			Matrix[j][i] = weight;
		}
	}
	void setVisit() {
		for (int i = 0; i < Vexnum; i++)
			Visit[i] = false;
	}
	int FindNodeIndex(string str) {
		for (int i = 0; i < Vexnum; i++)
			if (node[i] == str)
				return i;
	}
	void PrintMin(string startNode) {
		vector<string> U;
		int minWeight, minWeightI = 0, minWeightJ = 0, sum = 0, i;
		setVisit();
		U.push_back(startNode);
		Visit[FindNodeIndex(startNode)] = true;
		while (U.size() != Vexnum) {
			minWeight = Infinity;
			for (auto p : U) {
				i = FindNodeIndex(p);
				for (int j = 0; j < Vexnum; j++) {
					if (Matrix[i][j] != 0 && Matrix[i][j] < minWeight && Visit[j] == false) {
						minWeight = Matrix[i][j];
						minWeightJ = j;
						minWeightI = i;
					}
				}
			}
			Visit[minWeightJ] = true;
			U.push_back(node[minWeightJ]);
			sum += minWeight;
		}
		cout << sum << endl;
	}
	void PrimAlgorithm() {
		vector<string> U;
		string startNode;
		int minWeight, minWeightI = 0, minWeightJ = 0 , sum, i;
		setVisit();
		cin >> startNode;
		PrintMin(startNode);
		setVisit();
		cout << "prim:" << endl;
		U.push_back(startNode);
		Visit[FindNodeIndex(startNode)] = true;
		while (U.size() != Vexnum) {
			minWeight = Infinity;
			for (auto p : U) {
				i = FindNodeIndex(p);
				for (int j = 0; j < Vexnum; j++) {
					if (Matrix[i][j] != 0 && Matrix[i][j] < minWeight && Visit[j] == false) {
						minWeight = Matrix[i][j];
						minWeightJ = j;
						minWeightI = i;
					}						
				}
			}
			Visit[minWeightJ] = true;
			U.push_back(node[minWeightJ]);
			cout << node[minWeightI] << " " << node[minWeightJ] << " " << minWeight << endl;
		}		
	}
	void KruskalAlgorithm() {
		setVisit();
		cout << "kruskal:" << endl;
		int* group = new int[Vexnum];
		for (int i = 0; i < Vexnum; i++)
			group[i] = i;
		int minWeight;
		string p1, p2;
		int loc1, loc2;
		for (int i = 0; i < Vexnum - 1; i++)
		{
			minWeight = Infinity;
			for (int j = 0; j < Vexnum; j++)
			{
				for (int k = 0; k < Vexnum; k++)
				{
					if (group[j] == group[k])
						continue;
					else
					{
						if (minWeight > Matrix[j][k] && Matrix[j][k] != 0)
						{
							minWeight = Matrix[j][k];
							loc1 = j;
							loc2 = k;
						}
					}
				}
			}
			Matrix[loc1][loc2] = 0;
			Matrix[loc2][loc1] = 0;
			if (loc1 > loc2)
			{
				cout << node[loc2] << ' ' << node[loc1] << ' ' << minWeight << endl;
				for (int i = 0; i < Vexnum; i++)
				{
					if (group[i] == group[loc1] && i != loc1)
						group[i] = group[loc2];
				}
				group[loc1] = group[loc2];
			}
			else
			{
				cout << node[loc1] << ' ' << node[loc2] << ' ' << minWeight << endl;
				for (int i = 0; i < Vexnum; i++)
				{
					if (group[i] == group[loc2] && i != loc2)
						group[i] = group[loc1];
				}
				group[loc2] = group[loc1];
			}
		}
		delete[]group;

	}
	void print() {
		for (int i = 0; i < Vexnum; i++) {
			for (int j = 0; j < Vexnum; j++)
				cout << Matrix[i][j] << ' ';
			cout << endl;
		}
	}
};

int main() {
	Map map;
	map.SetMatrix();
	map.SetWeight();
	map.PrimAlgorithm();
	map.KruskalAlgorithm();
	return 0;
}

问题 B: 道路建设 (Ver. I)

题目描述

有N个村庄,编号从1到N,你应该建造一些道路,使每个村庄都可以相互连接。
两个村A和B是相连的,当且仅当A和B之间有一条道路,或者存在一个村C使得在A和C之间有一条道路,并且C和B相连。
现在一些村庄之间已经有一些道路,你的任务就是修建一些道路,使所有村庄都连通起来,并且所有道路的长度总和是最小的。

输入

测试数据有多组
第一行是整数N(3 <= N <= 100),代表村庄的数量。 然后是N行,其中第i行包含N个整数,这些N个整数中的第j个是村庄i和村庄j之间的距离(距离是[1,1000]内的整数)。
然后是整数Q(0 <= Q <= N *(N + 1)/ 2),接下来是Q行,每行包含两个整数a和b(1 <= a <b <= N),代表着村庄a和村庄b之间的道路已经建成。

输出

对于每组测试数据
输出一个整数,表示要构建的道路的长度总和最小值

样例输入

3
0 990 692
990 0 179
692 179 0
1
1 2

样例输出

179

题解

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#define MaxLen 20
#define Infinity 99999 

using namespace std;

class Map {
private:
	int Distance[MaxLen][MaxLen];
	bool Visit[MaxLen];
	int Matrix[MaxLen][MaxLen];
	int Vexnum;
public:
	Map(int n) :Vexnum(n) {
		for (int i = 0; i < Vexnum; i++)
			for (int j = 0; j < Vexnum; j++)
				cin >> Distance[i][j];
	};
	void setVisit() {
		for (int i = 0; i < Vexnum; i++)
			Visit[i] = false;
	}
	void PrintMin(int startNode) {
		vector<int> U;
		int minWeight, minWeightI = 0, minWeightJ = 0, sum = 0, i;
		setVisit();
		U.push_back(startNode);
		Visit[startNode] = true;
		while (U.size() != Vexnum) {
			minWeight = Infinity;
			for (auto p : U) {
				i = p;
				for (int j = 0; j < Vexnum; j++) {
					if (Distance[i][j] != 0 && Distance[i][j] < minWeight && Visit[j] == false) {
						minWeight = Distance[i][j];
						minWeightJ = j;
						minWeightI = i;
					}
				}
			}
			Visit[minWeightJ] = true;
			U.push_back(minWeightJ);
			sum += minWeight;
		}
		cout << sum << endl;
	}
	void PrimAlgorithm() {
		vector<int> U;
		int startNode = 0;
		int minWeight, minWeightI = 0, minWeightJ = 0, i;
		setVisit();
		int sum = 0;
		setVisit();
		U.push_back(startNode);
		Visit[startNode] = true;
		while (U.size() != Vexnum) {
			minWeight = Infinity;
			for (auto p : U) {
				i = p;
				for (int j = 0; j < Vexnum; j++) {
					if (Distance[i][j] != 0 && Distance[i][j] < minWeight && Visit[j] == false) {
						minWeight = Distance[i][j];
						minWeightJ = j;
						minWeightI = i;
					}
				}
			}
			Visit[minWeightJ] = true;
			U.push_back(minWeightJ);
			sum += minWeight;
		}
		int n;
		cin >> n;
		while (n--) {
			int i1, i2;
			cin >> i1 >> i2;
			sum -= Distance[i1 - 1][i2 - 1];
		}
		cout << sum << endl;
	}
	void KruskalAlgorithm() {
		setVisit();
		int group[MaxLen];
		for (int i = 0; i < Vexnum; i++)
			group[i] = i;
		int sum = 0;
		int n;
		cin >> n;
		int temp = n;
		while (n--) {
			int i1, i2;
			cin >> i1 >> i2;
			i1--;
			i2--;
			if (i1 > i2)
			{
				for (int i = 0; i < Vexnum; i++)
				{
					if (group[i] == group[i1] && i != i1)
						group[i] = group[i2];
				}
				group[i1] = group[i2];
			}
			else
			{
				for (int i = 0; i < Vexnum; i++)
				{
					if (group[i] == group[i2] && i != i2)
						group[i] = group[i1];
				}
				group[i2] = group[i1];
			}
		}
		int minWeight;
		string p1, p2;
		int loc1, loc2;
		set<int> groupnum;
		for (int i = 0; i < Vexnum; i++)
			groupnum.insert(group[i]);
		for (int i = 0; i < groupnum.size() - 1; i++)
		{
			minWeight = Infinity;
			for (int j = 0; j < Vexnum; j++)
			{
				for (int k = 0; k < Vexnum; k++)
				{
					if (group[j] == group[k])
						continue;
					else
					{
						if (minWeight > Distance[j][k] && Distance[j][k] != 0)
						{
							minWeight = Distance[j][k];
							loc1 = j;
							loc2 = k;
						}
					}
				}
			}
			sum += minWeight;
			Distance[loc1][loc2] = 0;
			Distance[loc2][loc1] = 0;
			if (loc1 > loc2)
			{
				for (int i = 0; i < Vexnum; i++)
				{
					if (group[i] == group[loc1] && i != loc1)
						group[i] = group[loc2];
				}
				group[loc1] = group[loc2];
			}
			else
			{
				for (int i = 0; i < Vexnum; i++)
				{
					if (group[i] == group[loc2] && i != loc2)
						group[i] = group[loc1];
				}
				group[loc2] = group[loc1];
			}
		}
		cout << sum << endl;

	}
	void Print() {
		for (int i = 0; i < Vexnum; i++) {
			for (int j = 0; j < Vexnum; j++)
				cout << Distance[i][j] << ' ';
			cout << endl;
		}
	}
};

int main() {
	int num;
	while (cin >> num) {
		Map map(num);
		map.KruskalAlgorithm();
	}
	return 0;
}

问题 C: 图的顶点可达闭包

题目描述

给定有向图的邻接矩阵A,其元素定义为:若存在顶点i到顶点j的有向边则A[i,j]=1,若没有有向边则A[i,j]= 0。试求A的可达闭包矩阵A*,其元素定义为:若存在顶点i到顶点j的有向路径则A*[i,j]=1,若没有有向路径则A*[i,j]= 0。

输入

第1行顶点个数n
第2行开始的n行有向图的邻接矩阵,元素之间由空格分开

输出

有向图的可达闭包矩阵A*,元素之间由空格分开

样例输入

4
0 1 0 1
0 0 1 0
0 0 0 0
0 0 0 0

样例输出

0 1 1 1
0 0 1 0
0 0 0 0
0 0 0 0

题解

#include<iostream>
#include<vector>
#include<algorithm>
#define MaxLen 20
#define Infinity 99999 

using namespace std;

class Map {
private:
	bool Visit[MaxLen];
	string node[MaxLen];
	int Matrix[MaxLen][MaxLen];
	int Vexnum;
public:
	void SetMatrix() {
		cin >> Vexnum;
		for (int i = 0; i < Vexnum; i++)
			for (int j = 0; j < Vexnum; j++)
				cin >> Matrix[i][j];
	}
	void setVisit() {
		for (int i = 0; i < Vexnum; i++)
			Visit[i] = false;
	}
	void exchange() {
		int flag = 1;
		while (flag) {
			flag = 0;
			for (int i = 0; i < Vexnum; i++) {
				for (int j = 0; j < Vexnum; j++) {
					if (Matrix[i][j] == 1) {
						for (int k = 0; k < Vexnum; k++) {
							if (Matrix[j][k] == 1 && Matrix[i][k] != 1) {
								Matrix[i][k] = 1;
								flag = 1;
							}
						}
					}
				}
			}
		}
	}
	void print() {
		for (int i = 0; i < Vexnum; i++) {
			for (int j = 0; j < Vexnum; j++)
				cout << Matrix[i][j] << ' ';
			cout << endl;
		}
	}
};

int main() {
	Map map;
	map.SetMatrix();
	map.exchange();
	map.print();
	return 0;
}

问题 D: 图的应用之——图的连通

题目描述

给定一个图的邻接矩阵,请判断该图是否是连通图。连通图:任意两个顶点之间都有路径。
--程序要求--
若使用C++只能include一个头文件iostream;若使用C语言只能include一个头文件stdio
程序中若include多过一个头文件,不看代码,作0分处理
不允许使用第三方对象或函数实现本题的要求

输入

第1行输入一个整数k,表示有k个测试数据
第2行输入一个整数n,表示有n个结点
从第3行起到第n+2行输入一个邻接矩阵,其中Matrix[i,j]=1表示第i,j个结点之间有边,否则不存在边。
接下来是第2到第k个测试数据的结点数和邻接矩阵

输出

输出Yes or No表示图是否是强连通图

样例输入

2
4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
7
0 1 0 0 0 0 0
0 0 1 1 0 0 0
1 0 0 0 0 0 0
1 0 1 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 0 0 1 0 1 0

样例输出

Yes
No

题解

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#define MaxLen 20
#define Infinity 99999 

using namespace std;

class Map {
private:
	bool Visit[MaxLen];
	string node[MaxLen];
	int Matrix[MaxLen][MaxLen];
	int Vexnum;
	void DFS(int node) {
		for (int i = 0; i < Vexnum; i++) {
			if (Matrix[node][i] == 1 && Visit[i] == false) {
				Visit[i] = true;
				DFS(i);
			}
		}
	}
public:
	void SetMatrix() {
		cin >> Vexnum;
		for (int i = 0; i < Vexnum; i++)
			for (int j = 0; j < Vexnum; j++)
				cin >> Matrix[i][j];
	}
	void setVisit() {
		for (int i = 0; i < Vexnum; i++)
			Visit[i] = false;
	}
	void Judge() {
		int flag = 0;
		for (int i = 0; i < Vexnum; i++) {
			setVisit();
			Visit[i] = true;
			DFS(i);
			for (int i = 0; i < Vexnum; i++) {
				if (Visit[i] == false) {
					flag = 1;
					break;
				}
			}
			if (flag == 1)
				break;
		}
		if (flag == 1)
			cout << "No" << endl;
		else
			cout << "Yes" << endl;
	}
	void print() {
		for (int i = 0; i < Vexnum; i++) {
			for (int j = 0; j < Vexnum; j++)
				cout << Matrix[i][j] << ' ';
			cout << endl;
		}
	}
};

int main() {
	int n;
	cin >> n;
	while (n--) {
		Map map;
		map.SetMatrix();
		map.Judge();
	}	
	return 0;
}

0

评论区