【数据结构】图—图的邻接矩阵存储及度计算
题目描述
假设图用邻接矩阵存储。输入图的顶点信息和边信息，完成邻接矩阵的设置，并计算各顶点的入度、出度和度，并输出图中的孤立点（度为0的顶点）
--程序要求--
若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio
程序中若include多过一个头文件，不看代码，作0分处理
不允许使用第三方对象或函数实现本题的要求
输入
测试次数T，每组测试数据格式如下：
图类型 顶点数 （D—有向图，U—无向图）
顶点信息
边数
每行一条边（顶点1 顶点2）或弧（弧尾 弧头）信息
输出
每组测试数据输出如下信息（具体输出格式见样例）：
图的邻接矩阵
按顶点信息输出各顶点的度（无向图）或各顶点的出度 入度 度（有向图）。孤立点的度信息不输出。
图的孤立点。若没有孤立点，不输出任何信息。
输入样例1
2 D 5 V1 V2 V3 V4 V5 7 V1 V2 V1 V4 V2 V3 V3 V1 V3 V5 V4 V3 V4 V5 U 5 A B C D E 5 A B A C B D D C A D
输出样例1
0 1 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 V1: 2 1 3 V2: 1 1 2 V3: 2 2 4 V4: 2 1 3 V5: 0 2 2 0 1 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 0 A: 3 B: 2 C: 2 D: 3 E
思路分析
不能用别的头文件，但是我可以用string用来存储顶点，因为char型就需要自己写一个strcmp函数，毕竟需要遍历找对应下标不是？
在图建立的时候，数一下出度和入度，这个很简单，看代码就明白了：
matrix[GetIndex(tail)][GetIndex(head)] = 1; outdegree[GetIndex(tail)]++; indegree[GetIndex(head)]++;
然后如果是无向图的话，需要对称建立邻接矩阵：
if (kind == 'U') matrix[GetIndex(head)][GetIndex(tail)] = 1;
无向图的度就是出度和入度相加。
AC代码
#include<iostream>
using namespace std;
const int max_vertex_number = 100;
class Map {
int vertex_number = 0, edge_number = 0;
int matrix[max_vertex_number][max_vertex_number] = {0};
int indegree[max_vertex_number] = {0};
int outdegree[max_vertex_number] = {0};
string vertex[max_vertex_number];
char kind;
public:
Map() {
cin >> kind >> vertex_number;
for (int i = 0; i < vertex_number; i++)
cin >> vertex[i];
cin >> edge_number;
for (int i = 0; i < edge_number; i++) {
string tail, head;
cin >> tail >> head;
matrix[GetIndex(tail)][GetIndex(head)] = 1;
outdegree[GetIndex(tail)]++;
indegree[GetIndex(head)]++;
if (kind == 'U')
matrix[GetIndex(head)][GetIndex(tail)] = 1;
}
}
int GetIndex(string &data) {
for (int i = 0; i < vertex_number; i++)
if (data == vertex[i])
return i;
}
void Traverse() {
for (int i = 0; i < vertex_number; i++) {
for (int j = 0; j < vertex_number - 1; j++)
cout << matrix[i][j] << ' ';
cout << matrix[i][vertex_number - 1] << endl;
}
for (int i = 0; i < vertex_number; i++)
if (outdegree[i] + indegree[i] && kind == 'D')
cout << vertex[i] << ": " << outdegree[i] << ' ' << indegree[i] << ' ' << outdegree[i] + indegree[i]<< endl;
else if (outdegree[i] + indegree[i] && kind == 'U')
cout << vertex[i] << ": " << outdegree[i] + indegree[i]<< endl;
for (int i = 0; i < vertex_number; i++)
if (outdegree[i] + indegree[i] == 0)
cout << vertex[i] << endl;
}
};
int main() {
int t;
cin >> t;
while (t--) {
Map test;
test.Traverse();
}
return 0;
}腾讯云开发者
