数据结构-图概要.ppt

5.1 图的定义和术语 5.2 图的存储结构 构造无向网 Status CreateUDN(MGraph G) {// 算法 5.2 // 采用数组（邻接矩阵）表示法，构造无向网G。 int i,j,k,w; VertexType v1,v2; printf(G.vexnum : ); scanf(%d,G.vexnum); printf(G.arcnum :); scanf(%d,G.arcnum); getchar(); /*** 加上此句getchar()!!! ***/ // scanf(%d,%d,%d,G.vexnum, G.arcnum, IncInfo); for (i=0; iG.vexnum; i++ ) { printf(G.vexs[%d] : ,i); scanf(%c,G.vexs[i]); getchar(); } // 构造顶点向量 for (i=0; iG.vexnum; ++i ) // 初始化邻接矩阵 for (j=0; jG.vexnum; ++j ) { G.arcs[i][j].adj = INFINITY; //{adj,info} G.arcs[i][j].info= NULL; } 构造无向网 Status CreateUDN(MGraph G) {// 算法 5.2 // 采用数组（邻接矩阵）表示法，构造无向网G。 …… for (k=0; kG.arcnum; ++k ) { // 构造邻接矩阵 printf(v1 (char) : ); scanf(%c, v1);getchar(); printf(v2 (char) : ); scanf(%c, v2);getchar(); printf(w (int) : ); scanf(%d, w); getchar(); // 输入一条边依附的顶点及权值 i = LocateVex(G, v1); j = LocateVex(G, v2); // 确定v1和v2在G中位置 G.arcs[i][j].adj = w; // 弧v1,v2的权值 // if (IncInfo) scanf(G.arcs[i][j].info); // 输入弧含有相关信息 G.arcs[j][i].adj = G.arcs[i][j].adj; // 置v1,v2的对称弧v2,v1 } return OK; } // CreateUDN 5.3 图的遍历 5.4 图的连通性分量 5.4.2 无向图生成树 5.4.3 网的最小生成树 习题 构造最小生成树。 习题 构造最小生成树。 5.5 最短路径 有向无环图及应用 5.7 图的算法C语言程序实现举例 } vexnode1; /*顶点表结点 */ vexnode1 dig1［n］; /*全程量邻接链表 */ void criticalpath(vexnode1 dig［ ］) /*dig是AOE网的带权邻接链表*/ { int front=-1; rear=-1; /*顺序队列的首尾指针置初值为-1*/ int tpord［n］, vl［n］, ve［n］; int l［maxsize］, e［maxsize］; edgenode1 p; for (i=0; in; i++) ve［i］=0; /*各事件vi+1的最早发生时间置初值零 */ for (i=0; in; i++) /*扫描顶点表, 将入度为零的顶点入队 */ if (dig［i］.id==0) tpord［++rear］=i; m=0; /*计数器初始化 */ while (front![KG-*2]=rear) /*队非空 */ { front++; j=tpord［front］; /*vj+1出队, 即删去vj+1 */ m++; /*对出队的顶点个数计数 */