/*在一個圖中，如果任意兩頂點構成的偶對（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);
}