【数据结构】图—图的邻接矩阵存储及度计算

目录

题目描述

思路分析

AC代码

题目描述

假设图用邻接矩阵存储。输入图的顶点信息和边信息，完成邻接矩阵的设置，并计算各顶点的入度、出度和度，并输出图中的孤立点（度为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
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;
}