数据结构与算法A实验六图论---7-11 邻接表创建无向图

采用邻接表创建无向图G ，依次输出各顶点的度。

输入格式:

输入第一行中给出2个整数i(0<i≤10)，j(j≥0)，分别为图G的顶点数和边数。 输入第二行为顶点的信息，每个顶点只能用一个字符表示。 依次输入j行，每行输入一条边依附的顶点。

输出格式:

依次输出各顶点的度，行末没有最后的空格。

输入样例:

5 7
ABCDE
AB
AD
BC
BE
CD
CE
DE

结尾无空行

输出样例:

2 3 3 3 3

结尾无空行

#include<bits/stdc++.h>
using namespace std;

typedef struct ArcNode { //边结点
	int adjvex; //邻接顶点
	struct ArcNode* nextarc; //指向下一个边结点
}ArcNode;

typedef struct VNode { //顶点
	char data;
	ArcNode* firstarc; //指向第一条依附该顶点的边的指针
}VNode, AdjList[11];

typedef struct { //图
	AdjList vertices;
	int vexnum, arcnum; //顶点数和边数
}ALGraph;

int locate(ALGraph G, char c) { //找下标
	for (int i = 0; i < G.vexnum; i++) {
		if (G.vertices[i].data == c) {
			return i;
		}
	}
	return -1;
}

void Creat(ALGraph& G) { //接收G的地址
	char c[11]; //顶点
	char v1, v2; //边连接的顶点
	ArcNode* p1, * p2;
	cin >> G.vexnum >> G.arcnum;
	cin >> c;
	for (int i = 0; i < G.vexnum; i++) { //建顶点
		G.vertices[i].data = c[i];
		G.vertices[i].firstarc = NULL;
	}
	for (int k = 0; k < G.arcnum; k++) { //建邻接表
		cin >> v1 >> v2;
		int i = locate(G, v1); //找顶点下表
		int j = locate(G, v2);
		p1 = new ArcNode;
		p1->adjvex = j;
		p1->nextarc = G.vertices[i].firstarc;
		G.vertices[i].firstarc = p1;
		//无向图，双向建立
		p2 = new ArcNode;
		p2->adjvex = i;
		p2->nextarc = G.vertices[j].firstarc;
		G.vertices[j].firstarc = p2;
	}
}

void print(ALGraph G) {
	int cut;
	int sum[11] = { 0 };
	ArcNode* p;
	for (int i = 0; i < G.vexnum; i++) {
		cut = 0;
		p = G.vertices[i].firstarc;
		while (p) {
			cut++;
			p = p->nextarc;
		}
		sum[i] = cut;
	}
	for (int i = 0; i < G.vexnum; i++) {
		if (i == 0)
			cout << sum[0];
		else
			cout << " " << sum[i];
	}
}

int main()
{
	ALGraph G;
	Creat(G);
	print(G);
	return 0;
}

数据结构与算法基础（青岛大学-王卓）_哔哩哔哩_bilibili