数据结构实验六(C语言):图的应用（二）

实验六 图的应用（二）

[实验类别]

验证型实验。

[实验目的]

1．进一步功固图常用的存储结构。 2．熟练掌握在图的邻接矩阵中实现图的基本操作。 3．理解掌握AOV网、AOE网在邻接矩阵上的实现以及解决简单的应用问题。

[实验学时]

4小时

[实验组人数]

1人。

[实验设备环境]

计算机。

[实验内容]

拓扑排序及关键路径 [功能一]：从键盘上输入AOV网的顶点和有向边的信息,建立其邻接矩阵的存储结构,然后对该图拓扑排序,并输出拓扑序列及拓扑逆序列. 测试数据：教材图6.26 [功能二]：从键盘上输入AOE网的顶点和有向边的信息,建立其邻接矩阵存储结构,输出其关键路径和关键路径长度。 测试数据：教材图6.28

源代码

//SDTBU //计科181 //L #include<stdio.h> #include<string.h> #include<malloc.h> #include<iostream> #include<algorithm> #include<queue> using namespace std; #define Max_Vertex_Num 100 ///最大顶点数 typedef struct { char vex; char start; char endx; int w; } Node; typedef struct { char vexs[Max_Vertex_Num];///顶点集 int arcs[Max_Vertex_Num][Max_Vertex_Num]; int vexnum, arcnum; } Mgraph; typedef struct { int *base; int *top; int stacsize; } SeqStack; ///构建邻接矩阵 int LocateVex1(Mgraph &G, char u) { int i; for(i = 0; i < G.vexnum; i++) { if(G.vexs[i] == u) return i; } return -1; } ///AOV网的邻接矩阵建立 void CreateMGraph(Mgraph &G, int n, int m, Node *q) { int i, j, k; ///顶点数 G.vexnum = n; ///边数 G.arcnum = m; ///顶点信息 for(i = 0; i < G.vexnum; i++) { G.vexs[i] = q[i].vex; } ///初始化邻接矩阵 for(i = 0; i < G.vexnum; i++) { for(j = 0; j < G.vexnum; j++) { G.arcs[i][j] = 0; } } for(k = 0; k < G.arcnum; k++) { char v1 = q[k].start; char v2 = q[k].endx; i = LocateVex1(G, v1); j = LocateVex1(G, v2); G.arcs[i][j] = 1; } } ///AOE网的邻接矩阵建立 void CreateMGraph1(Mgraph &G, int n, int m, Node *q) { int i, j, k; ///顶点数 G.vexnum = n; ///边数 G.arcnum = m; ///顶点信息 for(i = 0; i < G.vexnum; i++) { G.vexs[i] = q[i].vex; } ///初始化邻接矩阵 for(i = 0; i < G.vexnum; i++) { for(j = 0; j < G.vexnum; j++) { G.arcs[i][j] = 0; } } for(k = 0; k < G.arcnum; k++) { char v1 = q[k].start; char v2 = q[k].endx; i = LocateVex1(G, v1); j = LocateVex1(G, v2); G.arcs[i][j] = q[k].w; } } ///输出邻接矩阵 void DispMatrix(Mgraph G) { int i, j; for(i = 0; i < G.vexnum; i++) { for(j = 0; j < G.vexnum; j++) printf("%d ", G.arcs[i][j]); printf("\n"); } } ///栈的初始化 void InitStack(SeqStack &S) { S.base = (int*)malloc(100 * sizeof(int)); if(!S.base) printf("空间已满\n"); else { S.top = S.base; S.stacsize = 100; } } ///判断栈是否为空 int IsEmpty(SeqStack &S) { if(S.top == S.base) return 1; else return 0; } ///入栈 void Push(SeqStack &S, int x) { if((S.top) - (S.base) == S.stacsize) { S.base = (int*)realloc(S.base, (S.stacsize + 10) * sizeof(int)); if(S.base == NULL) return ; S.top = S.base + S.stacsize; S.stacsize = S.stacsize + 10; } *S.top = x; S.top++; } ///出栈 void Pop(SeqStack &S, int *x) { if(S.top == S.base) return ; else { S.top--; *x = *S.top; } } ///拓扑排序 void FindInDegree(Mgraph G, int indegree[]) //计算图中各节点的入度 { int i, j; for(i = 0; i < G.vexnum; i ++) { indegree[i] = 0; } for(i = 0; i < G.vexnum; i ++) { for(j = 0; j < G.vexnum; j ++) if(G.arcs[i][j])//当两顶点之间存在边时，入度自加 indegree[j] ++; } } void TopologicalSort(Mgraph G, char *p) { int indegree[100]; FindInDegree(G, indegree); SeqStack S; int i, j, cnt = 0, l = 0; InitStack(S); for(i = 0; i < G.vexnum; i ++) { if(!indegree[i]) Push(S, i); //把入度为零的节点压栈 } printf("拓扑序列如下:\n"); while(!IsEmpty(S)) { Pop(S, &i); printf("%c ", G.vexs[i]); p[l++] = G.vexs[i]; cnt ++; for(j = 0; j < G.vexnum; j ++) { if(G.arcs[i][j]) { if(!(-- indegree[j]))//删除相对应得边 Push(S, j); } } } if(cnt < G.vexnum) printf("此图有环存在!\n"); printf("\n"); printf("拓扑逆序列如下:\n"); for(i=l-1; i>=0; i--) printf("%c ", p[i]); } ///构建AOV网的邻接矩阵 void AOV(Node *q, int &n, int &m) { int i; printf("输入顶点数和边数:\n"); scanf("%d %d", &n, &m); printf("输入每个顶点:\n"); for(i = 0; i < n; i++) { getchar(); scanf("%c", &q[i].vex); } printf("输入每条边:\n"); for(i = 0; i < m; i++) { getchar(); scanf("%c", &q[i].start); getchar(); scanf("%c", &q[i].endx); } } ///构建AOE网的邻接矩阵 void AOE(Node *q1, int &n1, int &m1) { int i; printf("输入顶点数和边数:\n"); scanf("%d %d", &n1, &m1); printf("输入每个顶点:\n"); for(i = 0; i < n1; i++) { getchar(); scanf("%c", &q1[i].vex); } printf("输入每条边和每条边的权值:\n"); for(i = 0; i < m1; i++) { getchar(); scanf("%c", &q1[i].start); getchar(); scanf("%c", &q1[i].endx); scanf("%d", &q1[i].w); } } ///关键路径 void CriticalPath(Mgraph G) { int indegree[100], outdegree[100]; ///存放顶点入度,出度 int i, j, k, cnt = 0,maxn=0; int ve[100], vl[100]; SeqStack S; FindInDegree(G, indegree); for(i = 0; i < G.vexnum; i++) ve[i] = 0; InitStack(S); for(i = 0; i < G.vexnum; i ++) { if(!indegree[i]) Push(S, i); ///把入度为零的节点压栈 } printf("拓扑序列如下:\n"); while(!IsEmpty(S)) { Pop(S, &i); printf("%c ", G.vexs[i]); cnt ++; for(j = 0; j < G.vexnum; j ++) { if(G.arcs[i][j]) { if(ve[j] < G.arcs[i][j] + ve[i]) ve[j] = G.arcs[i][j] + ve[i]; if(!(-- indegree[j]))///删除相对应得边 Push(S, j); } } } for(i = 0; i < G.vexnum; i++) { k = 0; for(j = 0; j < G.vexnum; j++) { if(G.arcs[i][j] != 0) k++; } outdegree[i] = k; } for(i = 0; i < G.vexnum; i++) vl[i] = ve[G.vexnum - 1]; for(i = G.arcnum - 1; i >= 0; i--) { if(outdegree[i] == 0) { for(j = 0; j < G.vexnum; j++) { if(G.arcs[j][i]) { if(vl[j] > vl[i] - G.arcs[j][i]) vl[j] = vl[i] - G.arcs[j][i]; outdegree[j]--; } } } } cout << "\n****************************\n"; cout << "Ve数组:"; for(i = 0; i < G.vexnum; i++) { cout << ve[i] << " "; } cout << endl; cout << "Vl数组:"; for(i = 0; i < G.vexnum; i++) { cout << vl[i] << " "; } cout << "\n****************************\n"; cout << "关键路径:"; for(i = 0; i < G.vexnum-1; i++) { if(ve[i] == vl[i]) { cout << G.vexs[i] << "->"; } } cout<<G.vexs[G.vexnum-1]<<endl; cout << "关键路径长度:"; for(i = 0; i < G.vexnum; i++) { maxn=max(maxn,ve[i]); } cout << maxn<<endl; } void menu() { printf("--------------------------------------------\n"); printf("\t1.建立AOV网的邻接矩阵\n"); printf("\t2.AOV网的拓扑序列和拓扑逆序列\n"); printf("\t3.建立AOE网的邻接矩阵\n"); printf("\t4.AOE网的关键路径和关键路径长度\n"); printf("\t5.退出\n"); printf("---------------------------------------------\n"); } int main() { Mgraph G1, G4; Node q[100], q1[100]; char a[100]; int n, m,n1, m1, T; menu(); while(1) { printf("请输入选项:\n"); scanf("%d", &T); if(T == 1) { printf("AOV网:\n\n"); AOV(q, n, m); CreateMGraph(G1, n, m, q); printf("输出图G1邻接矩阵:\n"); DispMatrix(G1); } else if(T == 2) { printf("AOV网的拓扑序列和拓扑逆序列:\n"); TopologicalSort(G1, a); printf("\n"); } else if(T == 3) { printf("AOE网:\n\n"); AOE(q1, n1, m1); printf("输出图G4邻接矩阵:\n"); CreateMGraph1(G4, n1, m1, q1); DispMatrix(G4); } else if(T == 4) { printf("AOE网的关键路径和关键路径长度:\n"); CriticalPath(G4); printf("\n"); } else break; } return 0; }