有向图邻接表.c

数据结构c语言版中关于图部分的所有源码

/*在一个图中，如果任意两顶点构成的偶对（vi，vj）是有序的，即顶点之间
的连线有方向性，那么我们称该图是有向图。下面是构造有向图邻接表的一个
程序*/

#define maxnode 40
#define null 0
#include <stdio.h>
typedef struct st_arc/*定义结构体*/
{
int adjvex;
int weight;
struct st_arc *nextarc;
}arcnode;
typedef struct
{int  vertex;
struct st_arc *firstarc;
}vernode;
typedef vernode adjlist[maxnode];
void del_arc(vernode g[],int v,int w)/*删除有向边v-w*/
{ arcnode *r1,*r2;
r1=g[v].firstarc;
r2=r1;
while(r1!=null&&r1->adjvex!=w)/*寻找边v-w*/
{
r2=r1;
r1=r1->nextarc;
}
if(r1==null)
{
printf("no edge v-w.");
return;
}
else
if(r1==r2)
g[v].firstarc=r1->nextarc;
else
r2->nextarc=r1->nextarc;
r1=g[w].firstarc;
r2=r1;
while(r1!=null&&r1->adjvex!=v)
/*在以w为头结点的链表中，删除相应的边结点*/
{
r2=r1;
r1=r1->nextarc;
}
if(r1==null)
{
printf("no edge v-w.");
return;
}
else
if(r1==r2)
g[w].firstarc=r1->nextarc;
else
r2->nextarc=r1->nextarc;
}
void print(vernode g[],int n)/*输出图的结构*/
{
arcnode *q;
int i;
printf("adjacency list of the graph:\n");
for(i=0;i<n;i++)
{
printf("\t%d\t",i);
printf("%d\t",g[i].vertex);
q=g[i].firstarc;
while(q!=null)
{
printf("%d\t",q->adjvex);
printf("%d\t",q->weight);
q=q->nextarc;
}
printf("\n");
}
}
main()
{
int i,j,n,k,w,v;
arcnode *p,*q;
adjlist g;
printf("Input node:");/*输入图中顶点个数*/
scanf("%d",&n);/*构造有向图的邻接表*/
for (k=0;k<n;k++)
{printf("node%d=",k);
scanf("%d",&g[k].vertex);
g[k].firstarc=null;
}
for(;;)
{
printf("Insert edge i->j,w:");
/*i为起始点，j为终点，w为权值。当输入－1退出录入*/
scanf("%d",&i);
scanf("%d",&j);
scanf("%d",&w);
if(i==-1&&j==-1&&w==-1)
break;
q=(arcnode*)malloc(sizeof(arcnode));
q->adjvex=j;
q->weight=w;
q->nextarc=g[i].firstarc;
g[i].firstarc=q;
}
print(g,n);
printf("Delete edge v-w:");
scanf("%d%d",&v,&w);
del_arc(g,v,w);
print(g,n);
}