程序中多次使用for循环(程序中顶点数以及边数是确定的)。
最终输出邻接矩阵(两层for循环实现)即为输出二维数组的操作。
设图G有n个顶点,则邻接矩阵是一个n × n的方阵,定义为:
无向图的邻接矩阵,两个顶点有边则为1,否则,为0;因为是无向图arc[i][j] = arc[j][i],所以矩阵为对称矩阵,对角线为自己到自己的边,邻接矩阵中,行之和或者列之和都为各顶点度的总数。
设图G有向网图,有n个顶点,则邻接矩阵是一个n × n的方阵,定义为:
代码实现邻接矩阵存储无向图:
#include<stdio.h> //头
//有函数调用
typedef struct //邻接矩阵定义
{
int vers[20];
int arcs[20][20];
int n,e;
}graph;
void createUDG(graph *G) //创建无向图邻接矩阵
{
int i,j,k;
int a,b;
printf("请输入当前图的顶点数和边数,中间用空格分隔");
scanf("%d %d",&G->n,&G->e);
printf("请输入顶点信息");
for(i=0;i<G->n;i++)
scanf("%d",&(G->vers[i]));
printf("输出顶点信息");
for(i=0;i<G->n;i++)
printf("%d",G->vers[i]);
for(i=0;i<G->n;i++)
{
for(j=0;j<G->n;j++)
G->arcs[i][j]=0;
}
for(k=0;k<G->e;k++)
{
int v1,v2;
printf("请输入第%d条边依附的两个点:",k+1);
scanf("%d %d",&v1,&v2);
if(v1>G->n||v2>G->n)
{
printf("error");
}
for(i=0;v1!=G->vers[i];i++);
for(j=0;v2!=G->vers[j];j++);
G->arcs[i][j]=G->arcs[j][i]=1;
}
}
int main() //主
{
graph g;
int i,j;
createUDG(&g);
for(i=0;i<g.n;i++)
{
for(j=0;j<g.n;j++)
printf(" %2d ",g.arcs[i][j]);
printf("\n");
}
return 0;
}
网友评论