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>
#include<string>
using namespace std;
struct Node{
string data;
Node *next;
};
struct Arc {
int adjvex;
Node *firstNode;
Node *nextArc;
};
int findIndex (Arc *arc, int n, string v);
void insert (Node* p,string v);
class Graph{
public:
int vertex;
int edge;
char kind;
Arc* arc;
int **g;
Graph(char k,int n){
int i,j;
kind=k;
vertex=n;
string v1,v2;
int i1,i2;
g=new int*[vertex];
for(i=0;i<vertex;i++)
g[i]=new int[vertex];
for(i=0;i<vertex;i++){
for(j=0;j<vertex;j++)
g[i][j]= 0;
}
arc=new Arc[vertex];
for(i=0;i<vertex;i++){
arc[i].adjvex=i;
arc[i].firstNode=new Node;
cin>>arc[i].firstNode->data;
arc[i].firstNode->next=NULL;
}
cin>>edge;
for(i=0;i<edge;i++){
cin>>v1>>v2;
i1=findIndex(arc,vertex,v1);
i2=findIndex(arc,vertex,v2);
if(kind=='U'){
setEdge(i1,i2);
setEdge(i2,i1);
insert(arc[i1].firstNode,v2);
insert(arc[i2].firstNode,v1);
}
else{
setEdge(i1,i2);
insert(arc[i1].firstNode,v2);
}//else
}//for
}
void setEdge(int i,int j){
g[i][j]=1;
}
void printG(){
int i,j;
for(i=0;i<vertex;i++){
for(j=0;j<vertex-1;j++)
cout<<g[i][j]<<" ";
cout<<g[i][j]<<endl;
}
}
void printVertex(){
int i,j;
if(kind=='U'){
int num=0;
for(i=0;i<vertex;i++){
for(j=0;j<vertex;j++){
if(g[i][j]==1)
num++;
}//for
if(num!=0)
cout<<arc[i].firstNode->data<<": "<<num<<endl;
num=0;
}
}
else{
int innum, outnum;
innum=outnum=0;
for(i=0;i<vertex;i++){
for(j=0;j<vertex;j++){
if(g[i][j]==1)
outnum++;
}//for
for(j=0;j<vertex;j++){
if(g[j][i]==1)
innum++;
}
if(outnum+innum!=0)
cout<<arc[i].firstNode->data<<": "<<outnum<<" "<<innum<<" "<<outnum + innum<<endl;
innum=outnum=0;
}
}
}
void printLone(){
int i,j;
if(kind=='U'){
int num=0;
for(i=0;i<vertex;i++){
for(j=0;j<vertex;j++){
if(g[i][j]==1)
num++;
}//for
if(num==0)
cout<<arc[i].firstNode->data<<endl;
num=0;
}//for
}
else {
int innum,outnum;
innum=outnum=0;
for(i=0;i<vertex;i++){
for(j=0;j<vertex;j++){
if(g[i][j]==1)
outnum++;
}//for
for(j=0;j<vertex;j++){
if(g[j][i]==1)
innum++;
}//for
if(outnum+innum==0)
cout<<arc[i].firstNode->data<<endl;
innum=outnum=0;
}//for
}//else
}
};//Graph
int findIndex(Arc *arc,int n,string v){
int i;
for(i=0;i<n;i++){
if(arc[i].firstNode->data==v)
return i;
}
}
void insert(Node* p,string v){
while(p)
p=p->next;
p=new Node;
p->data=v;
p->next=NULL;
}
int main(){
int t;
cin>>t;
char kind;
int vertexNum;
while(t--){
cin>>kind>>vertexNum;
Graph graph(kind,vertexNum);
graph.printG();
graph.printVertex();
graph.printLone();
}
return 0;
}