图的邻接矩阵存储
程序员文章站
2022-05-21 08:49:15
...
图的邻接矩阵
图的基本存储方法有两种:邻接矩阵和邻接表
这里简单对邻接矩阵做一个描述(带权有向图)
首先要定义一个图和顶点的结构体
typedef struct//定义顶点的结构体
{
int no; //顶点的编号
char info[20]; //顶点的一些信息,看应用而定
}Acme;
typedef struct //图的定义
{
int edges[Max][Max]; //定义一个矩阵
int n,e;//边长数和顶点数
Acme acme[Max];//存放顶点信息
}Graph;
建立一个图的邻接矩阵
void CreateGraph(Graph *G)
{
int i,j,k,m;
printf("请输入顶点数和边数:\n");
scanf("%d %d",&G->n,&G->e);
printf("请输入顶点的编号及信息:\n");
for(i=0;i<G->n;i++)
{
scanf("%d %s",&G->acme[i].no,&G->acme[i].info);
}
for(i=0;i<G->n;i++)
{
for(j=0;j<G->n;j++)
{
if(i==j)
G->edges[i][j]=0;
else
G->edges[i][j]=LIMIT;
}
}
printf("请输入每条边的顶点及其权值\n");
for(k=0;k<G->e;k++)
{
scanf("%d %d %d",&i,&j,&m);
G->edges[i][j]=m;//若为无权图G->edges[i][j]=1;
}
}
输出邻接矩阵
void PrintGraph(Graph *G)
{
int i,j;
printf("输出顶点数及边数:\n");
printf("%d %d",G->n,G->e);
printf("输出各顶点信息:\n");
for(i=0;i<G->n;i++)
{
printf("%d %s\n",G->acme[i].no,G->acme[i].info);
}
printf("输出邻接矩阵\n");
printf("\t");
for(j=0;j<G->n;j++)
printf("[%d]\t",j);
printf("\n");
for(i=0;i<G->n;i++)
{
printf("[%d]\t",i);
for(j=0;j<G->n;j++)
{
if(G->edges[i][j]==LIMIT)
printf("∞\t");
else
printf("%d\t",G->edges[i][j]);
}
printf("\n");
}
}
main函数
int main()
{
Graph *h;
h=(Graph*)malloc(sizeof(Graph));
CreateGraph(h);
PrintGraph(h);
return 0;
}
上一篇: 利用PHP获取汉字首字母并且分组排序详解
下一篇: DS图—图的邻接矩阵存储及度计算