给定一个无向图,在此无向图中增加一个新顶点。
#include<iostream>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MVNum 100 //最大顶点数
using namespace std;
typedef struct
{//图的邻接矩阵存储表示
int vexs[MVNum]; //顶点表
int arcs[MVNum][MVNum]; //邻接矩阵
int vexnum,arcnum; //图的当前点数和边数
}AMGragh;
int CreateUDN(AMGragh &G,int vexnum,int arcnum)
{//采用邻接矩阵表示法,创建无向网G
G.vexnum=vexnum; //输入总顶点数
G.arcnum=arcnum; //输入总边数
if(G.vexnum>MVNum) return ERROR; //超出最大顶点数则结束函数
int i,j;
for(i=0;i<=G.vexnum;i++) //依次输入顶点信息
G.vexs[i]=i;
for(i=0;i<=G.vexnum;i++) //初始化邻接矩阵,边的权值均置为0
{
for(j=0;j<=G.vexnum;j++)
G.arcs[i][j]=0;
}
int h,k; //一条边依附的两个顶点h和k
for(i=0;i<G.arcnum;i++) //构造邻接矩阵
{
cin>>h>>k;
G.arcs[h-1][k-1]=1; //边的权值置为1
G.arcs[k-1][h-1]=1; //对称边的权值也置为1
}
return OK;
}
int InsertVex(AMGragh &G)
{//在以邻接矩阵形式存储的无向图G上插入顶点
/**************begin************/
/**************end************/
}
int OutputUDN(AMGragh G)
{//输出图G
int i,j;
for(i=0;i<=G.vexnum;i++) //输出第一行顶点表
{
if(i!=G.vexnum)
cout<<G.vexs[i]<<" ";
else
cout<<G.vexs[i]<<endl;
}
for(i=0;i<G.vexnum;i++) //输出其余各行
{
cout<<G.vexs[i+1]<<" "; //先输出顶点
for(j=0;j<G.vexnum;j++)
{
if(j!=G.vexnum-1)
cout<<G.arcs[i][j]<<" ";
else
cout<<G.arcs[i][j]<<endl;
}
}
return OK;
}
int main()
{
int n,m; //n个顶点和m条边
while(cin>>n>>m)
{
if(n==0&&m==0) break; //输入结束标志
AMGragh G;
CreateUDN(G,n,m); //采用邻接矩阵表示法,创建无向网G
InsertVex(G); //在以邻接矩阵形式存储的无向图G上插入顶点
OutputUDN(G); //输出图G
}
return 0;
}