无向图邻接表.c

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

/*图由一个非空的顶点的集合和一个描述顶点之间关系的集合组成。如果一个
图中任意顶点之间的连线都没有方向性，那么我们称这个图为无向图。邻接表
存储法是一种顺序存储与链式存储相结合的存储方法。顺序存储部分用来保存
图中顶点的信息，链式存储部分用来保存图中边的信息。下面是构造无向图邻
接表的一个程序*/

#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)
{
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)
/*在以v为头结点的链表中，删除相应的边结点*/
{
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;
p=(arcnode*)malloc(sizeof(arcnode));
p->adjvex=i;
p->weight=w;
p->nextarc=g[j].firstarc;
g[j].firstarc=p;
}
print(g,n);
printf("Delete edge v-w:");
scanf("%d%d",&v,&w);
del_arc(g,v,w);
print(g,n);
}