C++实现用邻接矩阵存储的图，求顶点的度，求两顶点是否邻接

2022-09-18 11:59:35


代码：

#include <iostream>
using namespace std;
#define MAXVERTEXNUM 20


typedef enum { DG, UDG, DN, UDN }GraphKind;//图的类型{有向图、无向图、有向网、无向网}

//图的邻接矩阵存储方式
typedef struct MGraph {
	char vex[MAXVERTEXNUM];//定点集
	int edge[MAXVERTEXNUM][MAXVERTEXNUM];//边集
	int vexnum, arcnum;//顶点数量，边数量
	GraphKind kind;//图的类型
}MGraph;

//在图G中查找顶点在顶点集中的下标位置
int LocateVex(MGraph *g, char v) {
	for (int i = 0; i < g->vexnum; i++) {
		if (g->vex[i] == v)
			return i;
	}
	return -1;
}

//打印输出图的邻接矩阵表示
void PrintGraph(MGraph g) {
	switch (g.kind)
	{
	case 0:cout << "打印输出无向图G" << endl; break;
	case 1:cout << "打印输出有向图G" << endl; break;
	case 2:cout << "打印输出无向网G" << endl; break;
	case 3:cout << "打印输出有向网G" << endl; break;

	default:cout << "图的类型错误！" << endl;
		break;
	}

	cout << "图的顶点：";
	for (int i = 0; i < g.vexnum; i++) {
		cout << g.vex[i] << " ";
	}
	cout << endl;

	cout << "图的邻接矩阵："<<endl;
	for (int i = 0; i < g.vexnum; i++) {
		for (int j = 0; j < g.vexnum; j++) {
			cout << g.edge[i][j] << " ";
		}
		cout << endl;	
	}
}

//在图的邻接矩阵中标记给定边xy的值value
void Setarc(MGraph *g,char x,char y,int value) {
	int i, j;
	i = LocateVex(g,x);
	j = LocateVex(g,y);
	g->edge[i][j] = value;
}

//生成邻接矩阵存储的图 （无向图，有向图，无向网，有向网）
void CreateGraph(MGraph *g) {

	int k = NULL;
	cout << "请输入图的类型（0:DG,1:UDG,2:DN,3:UDN）：";
	cin>>k;
	switch (k)
	{
	case 0:g->kind = DG; break;
	case 1:g->kind = UDG; break;
	case 2:g->kind = DN; break;
	case 3:g->kind = UDN; break;

	default:cout << "图的类型输入错误！" << endl;
		break;
	}
	cout << endl;


	cout << "请输入顶点数：";
	cin >> g->vexnum;

	cout << "请输入边数：";
	cin >> g->arcnum;
	cout << endl;

	//输入顶点
	cout << "请输入顶点，以空格分隔（eg：e g h）：";
	for (int i = 0; i < g->vexnum; i++) {
		cin >> g->vex[i];
	}

	//初始化图的邻接矩阵
	for (int i = 0; i < g->vexnum; i++) {
		for (int j = 0; j < g->vexnum; j++) {
			g->edge[i][j] = 0;
		}
	}

	//输入边
	switch (k)
	{
	case 1:cout << "请输入边（eg：ab，bd）"; 
		   for (int i = 0; i < g->arcnum; i++)
		   { 
			char temp[3];  cin >> temp; Setarc(g, temp[0], temp[1], 1);  Setarc(g, temp[1], temp[0], 1);
		   }; 
	break;
	case 0:cout << "请输入边（eg：ab，bd）"; 
		   for (int i = 0; i < g->arcnum; i++)
		   {
			char temp[3];  cin >> temp; Setarc(g, temp[0], temp[1], 1);
			}; 
		   break;
	case 3:cout << "请输入边和边的权值（eg：ab 2，dc 15）";
		for (int i = 0; i < g->arcnum; i++)
		{
			char temp[3]; int v = 2; cin >> temp; fflush(stdin); cin >> v; Setarc(g, temp[0], temp[1], v); Setarc(g, temp[1], temp[0], v);
		};
		break;
	case 2:cout << "请输入边和边的权值（eg：ab 2，dc 15）:";
		for (int i = 0; i < g->arcnum; i++)
		{
			char temp[3]; int v;  cin >> temp; fflush(stdin); cin >> v; Setarc(g, temp[0], temp[1], v);
		};
		break;

	default:cout << "输入错误！" << endl;
	}
	cout << endl;
}

//求任意顶点的度（或出度、入度）
void GetDegree(MGraph *g, char x) {
	int degree = 0;
	int site = LocateVex(g, x);
	for (int i = 0; i < g->vexnum; i++) {
		if (g->edge[site][i] != 0)
			degree++;
	}

	if (g->kind == UDG || g->kind == UDN) {
		cout << "顶点 " << x << " 的度为：" << degree << endl;
	
	}
	else if (g->kind == DG || g->kind == DN) {
		cout << "顶点 " << x << " 的出度为：" << degree << endl;
		degree = 0;
		for (int i = 0; i < g->vexnum; i++) {
			if (g->edge[i][site] != 0)
				degree++;
		}
		cout << "顶点 " << x << " 的入度为：" << degree << endl;
	}

}
//求两个顶点之间的关系
void GetRelation(MGraph *g,char x,char y) {
	
	int i, j;
	i = LocateVex(g,x);
	j = LocateVex(g,y);

	if (g->edge[i][j] != 0) {
		if (g->kind == UDG || g->kind == UDN) {
			cout << "顶点 " << x << " 与顶点 " << y << " 互为邻接点！";
			if (g->kind == UDN)
				cout << "边的权值为：" << g->edge[i][j] << "。";
		}
		else {
			cout << "顶点 " << x << " 邻接到顶点 " << y << " ！";
			if (g->kind == DN) {
				cout << "弧 " << x << y << " 的权值为 " << g->edge[i][j] << " ；";
				if (g->edge[j][i] != 0) {
					cout << "顶点 " << y << " 邻接到顶点 " << x << " ！";
					cout << "弧 " << y << x << " 的权值为 " << g->edge[j][i] << " ；";
				}
				
			}
		}
		cout << endl;
	}
}

int main()
{
	MGraph g;
	CreateGraph(&g);
	PrintGraph(g);
	

	cout << endl;
	char n;
	cout << "请输入顶点：";
	cin >> n;
	GetDegree(&g, n);

	cout << endl;
	char x, y;
	cout << "请输入要求关系的两个顶点：";
	cin >> x;
	cin >> y;
	GetRelation(&g,x,y);
}

在控制台上的输入输出：

（1）无向图

输入：

请输入图的类型（0:DG,1:UDG,2:DN,3:UDN）：0

请输入顶点数：4
请输入边数：5

请输入顶点，以空格分隔（eg：e g h）：a b c d
请输入边（eg：ab，bd）：ab bd ac cd bc

输出：

打印输出无向图G
图的顶点：a b c d
图的邻接矩阵：
0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0

（2）有向图

输入：

请输入图的类型（0:DG,1:UDG,2:DN,3:UDN）：1

请输入顶点数：5
请输入边数：3

请输入顶点，以空格分隔（eg：e g h）：a b c d e
请输入边（eg：ab，bd）ac ce db

输出：

打印输出有向图G
图的顶点：a b c d e
图的邻接矩阵：
0 0 1 0 0
0 0 0 0 0
0 0 0 0 1
0 1 0 0 0
0 0 0 0 0

（3）无向网

输入：

请输入图的类型（0:DG,1:UDG,2:DN,3:UDN）：2

请输入顶点数：3
请输入边数：2

请输入顶点，以空格分隔（eg：e g h）：x y z
请输入边和边的权值（eg：ab 2，dc 15）xy 23 zx 5

输出：

打印输出无向网G
图的顶点：x y z
图的邻接矩阵：
0 23 5
23 0 0
5 0 0

（4）有向网

输入：

请输入图的类型（0:DG,1:UDG,2:DN,3:UDN）：3

请输入顶点数：5
请输入边数：5

请输入顶点，以空格分隔（eg：e g h）：x y z a b
请输入边和边的权值（eg：ab 2，dc 15）ab 5 ba 4 xy 20 yz 3 za 43

输出：

打印输出有向网G
图的顶点：x y z a b
图的邻接矩阵：
0 20 0 0 0
0 0 3 0 0
0 0 0 43 0
0 0 0 0 5
0 0 0 4 0

（5）求顶点的度

输入：

请输入顶点：a

输出：

顶点 a 的出度为：2

顶点 a 的入度为：1

（6）求任意两顶点之间的关系

输入：

请输入要求关系的两个顶点：a b

输出：

顶点 a 邻接到顶点 b ！弧 ab 的权值为 3 ；顶点 b 邻接到顶点 a ！弧 ba 的权值为 65 ；



效果展示：
C++实现用邻接矩阵存储的图，求顶点的度，求两顶点是否邻接


注意事项： 在构造无向网和有向网的过程中，输入边和其上权值的时候，因为连续使用了两个cin，中间需要使用fflush(stdin);来清楚输入缓冲区，使第二个cin可以正确输入；
上一篇：pcanet网络理解


下一篇：Btrace使用入门