《数据结构》第八章：图.ppt

王钢 主编 清华大学出版社 ;第8章 图;图的基本定义 ;图的基本操作 ;图的基本操作; 邻接矩阵 ;[算法8.1] 建立一个有向图的邻接矩阵存储的算法 void CreateMGraph(Mgraph *G) { // 建立有向图G的邻接矩阵存储 int i, j,k,w; char ch; scanf(%d,%d,G-n,G-e)； // 输入顶点数和边数 for (i=0;iG-n;i++) scanf(%c,G-vexs[i]); // 输入顶点信息，建立顶点表 for (i=0;iG-n;i++) for(j=0;jG-n;j++) G-edges[i][j]=0; // 初始化邻接矩阵 for (k=0;kG-e;k++) // 输入e条边，建立邻接矩阵 { scanf(%d,%d,i,j); G-edges[i][j]=1; // 若加入G-edges[j][i]=1则为无向图邻接矩阵存储建立 } };邻接表 ;[算法8.2] 建立一个有向图的邻接表存储的算法 void CreateALGraph (ALGraph *G) { // 建立有向图的邻接表存储 int i,j,k; EdgeNode *s; scanf(%d,%d,G-n,G-e)； // 输入顶点数和边数 for (i=0;iG-n;i++) // 建立有n个顶点的顶点表 { scanf(%c,G-adjlist[i].vertex); // 输入顶点信息 G-adjlist[i].firstedge=NULL; // 顶点的表表头指针设为空 } for (k=0;kG-e;k++) // 输入e条边，建立邻接矩阵 {scanf(%d,%d,i,j); // 输入边vi,vj的顶点对应序号 s=( EdgeNode *)malloc(sizeof (Node)); // 生成新边表结点s s-adjvex=j; // 邻接点序号为j s-next=G-adjlist[i].firstredge; // 将新边表结点s插入到顶点vi的边表头部 G-adjlist[i].firstedge=s; } };十字链表 ;[算法8.3] 建立有向图的十字链表存储的算法 void CreateDG (OLGraph *G) { //采用十字链表表示，构造有向图G(G.kind=DG) int i,j,k;char v1,v2; ArcBox *p; scanf(%d,%d,(G-vexnum),(G-arcnum),(G-IncInfo)); //IncInfo为0则各 弧不含其他信息 for (i=0;iG-vexnum;++i) //构造表头向量 {scanf(%c,(G-xlist[i].vertex)); //输入顶点值 G-xlist[i].firstin=G-xlist[i].firstout=NULL; //初始化指针 } for (k=0;kG-arcnum;++k) //输入各弧并构造十字链表 { scanf(%c,%c,(v1),(v2)); //输入一条弧的始点和终点 i=LocateVex(G, v1); j=LocateVex(G, v2); //确定v1和v2在G中的位置 p=(ArcBox *)malloc (sizeof(ArcBox)); //假设有足够空间 *p={i,j,G-xlist[j].firstin,G-xlist[i].firstout,NULL} //对弧结点赋值 G-xlist[j].firstin=G-xlist[i].firstout=p;//完成在入弧和出弧链头的插入 if (IncInfo) Scanf((p-info)); //若弧含有相关信息，则输入 } };邻接多重表 ;具体邻接多重表存储表示的形式描述如下： #define MAX_VERTEX_NUM 20 ty