邻接表存储结构建立无向图

《邻接表存储结构建立无向图》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、//算法功能：采用邻接表存储结构建立无向图#include#include#defineOK1#defineNULL0#defineMAX_VERTEX_NUM20//最大顶点数typedefintStatus;//函数的类型，其值是函数结果状态代码typedefcharVertexType;typedefintVRType;typedefintInforType;typedefstructArcNode{intadjvex;//该边所指的顶点的位置structArcNode

2、*nextarc;//指向下一条边的指针intweight;//边的权}ArcNode;//表的结点typedefstructVNode{VertexTypedata;//顶点信息（如数据等）ArcNode*firstarc;//指向第一条依附该顶点的边的弧指针}VNode,AdjList[MAX_VERTEX_NUM];//头结点typedefstructALGraph{AdjListvertices;intvexnum,arcnum;//图的当前顶点数和弧数}ALGraph;//返回顶点v在顶点向量中的位置i

3、ntLocateVex(ALGraphG,charv){inti;for(i=0;v!=G.vertices[i].data&&i=G.vexnum)return-1;returni;}//构造邻接链表StatusCreateUDN(ALGraph&G){intj;ArcNode*s,*t;printf("输入无向图顶点数:");scanf("%d",&G.vexnum);printf("输入无向图边数:");scanf("%d",&G.arcnum);getchar();

4、for(inti=0;i

5、f("%c",&v2);getchar();inti=LocateVex(G,v1);intj=LocateVex(G,v2);//确定v1,v2在G中的位置s=(ArcNode*)malloc(sizeof(ArcNode));t=(ArcNode*)malloc(sizeof(ArcNode));s->adjvex=j;//该边所指向的顶点的位置为js->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=s;t->adjvex=i;//该边所指向的顶点

6、的位置为jt->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=t;}returnOK;}StatusPrintAdjList(ALGraph&G){ArcNode*p;printf("%4s%6s%12s","编号","顶点","相邻边编号");for(inti=0;ine

7、xtarc)printf("%4d",p->adjvex);printf("");}returnOK;}intmain(){ALGraphG;CreateUDN(G);rintAdjList(G);return0;}