用邻接表存储n个顶点m条弧的有向图
最后更新于：2022-04-01 16:02:01
例如要存储一下有向图：
当输入6个顶点，8条弧
1 2
1 3
2 4
3 4
3 5
4 1
4 6
5 6
建立的邻接表的流程图为：
实现代码：
~~~
/*
用邻接表存储n个顶点m条弧的有向图
*/
#include<stdio.h>
#include<stdlib.h>
#define MAX 10005
typedef struct ArcNode
{
int adjvex;
struct ArcNode * nextarc;
}ArcNode;
typedef struct VNode
{
int vertex;
ArcNode * firstarc;
}VNode;
int n,m;
VNode V[MAX];
void init()
{
ArcNode * p;
for(int i=1;i<=n;i++)
{
V[i].vertex=i;
V[i].firstarc=NULL;
}
for(int i=0;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=b;
p->nextarc=V[a].firstarc;
V[a].firstarc=p;
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF&&(n||m))
{
init();
ArcNode * p;
ArcNode * q;
for(int i=1;i<=n;i++)
{
printf("%d",V[i].vertex);
p=V[i].firstarc;
while(p!=NULL)
{
printf(" %d",p->adjvex);
q=p;
p=p->nextarc;
free(q);
}
printf("\n");
}
}
return 0;
}
~~~