DS图—图的邻接矩阵存储及度计算
题目描述
假设图用邻接矩阵存储。输入图的顶点信息和边信息,完成邻接矩阵的设置,并计算各顶点的入度、出度和度,并输出图中的孤立点(度为0的顶点)–程序要求-- 若使用C++只能include一个头文件iostream;若使用C语言只能include一个头文件stdio 程序中若include多过一个头文件,不看代码,作0分处理 不允许使用第三方对象或函数实现本题的要求
输入
测试次数T,每组测试数据格式如下:图类型 顶点数 (D—有向图,U—无向图)
顶点信息
边数
每行一条边(顶点1 顶点2)或弧(弧尾 弧头)信息
输出 每组测试数据输出如下信息(具体输出格式见样例):
图的邻接矩阵
按顶点信息输出各顶点的度(无向图)或各顶点的出度 入度 度(有向图)。孤立点的度信息不输出。
图的孤立点。若没有孤立点,不输出任何信息。
样例输入
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
样例输出
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
这道题的难点是只能用一头文件,输入结点名称的时候,如何找到名称和相应的下标比较麻烦,需要一个一个字符对比
#include<iostream>
using namespace std;
class Graph {
private:
int **mat;
int n;
char **vertex; //顶点名字
int du[20][2]; //当图是有向图时,du[1][0]=顶点1的出度
//du[1][1]= 入度
char type;
public:
Graph(int input_n,char t) {
n = input_n;
du[20][2] = {0};
for(int i = 0; i < 20; i++){
for(int j = 0; j < 2; j++){
du[i][j]=0;
}
}
type = t;
mat = new int *[n];
vertex = new char *[n];
for (int i = 0; i < n; i++) {
vertex[i] = new char[10];
mat[i] = new int[n];
for(int j = 0; j < n; j++) {
mat[i][j] = 0;
}
for(int j = 0; j < 10; j++) {
vertex[i][j] = 0;
}
}
for(int i = 0; i < n; i++) {
cin>>vertex[i];
}
int side; //边数
cin >> side;
while(side--) {
if(type == 'U')
u_insert();
else
d_insert();
}
}
~Graph() {
for (int i = 0; i< n; ++i) {
delete[] mat[i];
delete[] vertex[i];
}
delete[] mat;
delete[] vertex;
}
int find(char *a) {
for(int i = 0; i < n; i++) {
int flag = 1;
for(int j = 0; j < 10; j++) {
if(vertex[i][j] != a[j]) {
flag = 0;
break;
}
}
if(flag == 1) {
return i;
}
}
}
void d_insert() {
char a[10] = {0}, b[10] = {0};
cin>>a>>b;
int x = find(a), y = find(b); //找到目标数组下标
mat[x][y] = 1;
du[x][0]++; //x的出度+1
du[y][1]++; //y的入度+1
}
void u_insert() {
char a[10] = {0}, b[10] = {0};
cin>>a>>b;
int x = find(a), y = find(b); //找到目标数组下标
mat[x][y] = 1;
mat[y][x] = 1;
du[x][0]++;
du[y][0]++;
}
void output() {
for (int i = 0; i < n; ++i) {
for(int j = 0; j < n; j++) {
cout<<mat[i][j]<<" ";
}
cout<<endl;
}
for(int i = 0; i < n; i++) {
cout<<vertex[i];
if(type == 'D') {
if(du[i][0]||du[i][1])
cout<<": "<<du[i][0]<<" "<<du[i][1]<<" "<<du[i][0] + du[i][1];
} else {
if(du[i][0])
cout<<": "<<du[i][0]<<" ";
}
cout<<endl;
}
}
};
int main() {
int t,num;
char type;
cin>>t;
while(t--) {
cin>>type>>num;
Graph g(num,type);
g.output();
}
return 0;
}
上一篇: 粉丝怎样炒不粘在一起?做起来超简单!
下一篇: 红酒和木瓜怎么吃丰胸快