实验六 图的应用及其实现
- 格式：doc
- 大小：51.00 KB
- 文档页数：17
实验六图的应用及其实现一、实验目的1．进一步功固图常用的存储结构。
2．熟练掌握在图的邻接表实现图的基本操作。
3．理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。
二、实验内容从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,然后对该图拓扑排序,并输出拓扑序列. 试设计程序实现上述AOV网的类型定义和基本操作,完成上述功能。
相关常量及结构定义：typedef int InfoType;typedef char VertexType;typedef int SElemType;#define STACK_INIT_SIZE 100 //存储空间初始分配量#define STAXKINCREMENT 10 //存储空间分配增量#define MAX_VERTEX_NUM 20typedef struct ArcNode{int adjvex;struct ArcNode *nextarc;InfoType *info;}ArcNode;typedef struct VNode{VertexType data;struct ArcNode *firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedef struct ALGraph{AdjList vertices;int vexnum, arcnum;int kind;}ALGraph;typedef struct{SElemType *base;SElemType *top;int stacksize;}SqStack;设计相关函数声明：int CreateDG(ALGraph &G)int InitStack(SqStack &S)int Push(SqStack &S,SElemType e)int Pop(SqStack &S,SElemType &e)int StackEmpty(SqStack S)void FindInDegree(ALGraph G,int *indegree)int TopologicalSort(ALGraph G)三、数据结构与核心算法的设计描述1.创建AOV网int CreateDG(ALGraph &G){int i,j,k,v1,v2;cout<<"请输入该图的顶点数："<<"请输入该图的边数："<<endl;cin>>G.vexnum>>G.arcnum;for(i=0;i<G.vexnum;i++){G.vertices[i].data=i;G.vertices[i].firstarc=NULL;}cout<<"请输入一条边的始点和终点："<<endl;for(k=0;k<G.arcnum;++k){cout<<"请输入第"<<k+1<<"条边的始点和终点: ";cin>>v1>>v2;i=v1; j=v2;while(i<1||i>G.vexnum||j<1||j>G.vexnum){cout<<"请输入第"<<k+1<<"条边的始点和终点: ";cin>>v1>>v2;i=v1; j=v2;}i--;j--;ArcNode *p;p=(ArcNode *)malloc(sizeof(ArcNode));if(!p) return -1;p->adjvex=j;p->nextarc=G.vertices[i].firstarc;p->info=NULL; G.vertices[i].firstarc=p;G.vertices[i];}return 0;}2.初始化栈int InitStack(SqStack &S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base) exit (-1);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return 0;}3.入栈int Push(SqStack &S,SElemType e){if(S.top-S.base>=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+STAXKINCREME NT)*sizeof(SElemType));if(!S.base) exit (-1);S.top=S.base+S.stacksize;S.stacksize+=STAXKINCREMENT; }*S.top++=e;return 0;}4.出栈int Pop(SqStack &S,SElemType &e) {if(S.top==S.base) return -1;e=*--S.top;return 0;}5.判断栈是否为空int StackEmpty(SqStack S){if(S.top==S.base) return -1;else return 0;}6.个顶点入度void FindInDegree(ALGraph G,int *indegree){int i;for(i=0;i<G.vexnum;i++)indegree[i]=0;for(i=0;i<G.vexnum;i++)while(G.vertices[i].firstarc){indegree[G.vertices[i].firstarc->adjvex]++;G.vertices[i].firstarc=G.vertices[i].firstarc->nextarc;}}7.拓扑排序int TopologicalSort(ALGraph G){int i,k,indegree[MAX_VERTEX_NUM];ArcNode *p;SqStack S;FindInDegree(G,indegree);InitStack(S);for(i=0;i<G.vexnum;i++)if(!indegree[i]) Push(S,i);int count=0;while(!StackEmpty(S)){Pop(S,i);cout<<i+1<<'\t'; ++count;for(p=G.vertices[i].firstarc; p; p=p->nextarc){k=p->adjvex;if(!(--indegree[k])) Push(S,k);}}if(count<G.vexnum) return -1;else return 0;}四、函数的调用主函数主要设计：int main(){ALGraph G;CreateDG(G);TopologicalSort(G);return 0;}五、实验总结本次试验通过对有向图进行拓扑排序，我了解了有向图邻接表的存储结构更重要的的是学会了对有向图的拓扑排序算法，其中也将之前学过的栈结合起来，巧妙的找到了一个拓扑序列，可不足的是，该算法只能找到这一条拓扑序列，但是我相信通过完成了这次试验后我会改进算法而能将图的所有的拓扑序列找出来。
六、程序清单#include <iostream>using namespace std;typedef int InfoType;typedef char VertexType;typedef int SElemType;#define STACK_INIT_SIZE 100#define STAXKINCREMENT 10#define MAX_VERTEX_NUM 20 typedef struct ArcNode{int adjvex;struct ArcNode *nextarc; InfoType *info;}ArcNode;typedef struct VNode{VertexType data;struct ArcNode *firstarc;}VNode,AdjList[MAX_VERTEX_NUM]; typedef struct ALGraph{AdjList vertices;int vexnum, arcnum;int kind;}ALGraph;typedef struct{SElemType *base;SElemType *top;int stacksize;}SqStack;int CreateDG(ALGraph &G){int i,j,k,v1,v2;cout<<"请输入该图的顶点数："<<"请输入该图的边数："<<endl; cin>>G.vexnum>>G.arcnum;for(i=0;i<G.vexnum;i++){G.vertices[i].data=i;G.vertices[i].firstarc=NULL;}cout<<"请输入一条边的始点和终点："<<endl;for(k=0;k<G.arcnum;++k){cout<<"请输入第"<<k+1<<"条边的始点和终点: ";cin>>v1>>v2;i=v1; j=v2;while(i<1||i>G.vexnum||j<1||j>G.vexnum){cout<<"请输入第"<<k+1<<"条边的始点和终点: ";cin>>v1>>v2;i=v1; j=v2;}i--;j--;ArcNode *p;p=(ArcNode *)malloc(sizeof(ArcNode));if(!p) return -1;p->adjvex=j;p->nextarc=G.vertices[i].firstarc;p->info=NULL; G.vertices[i].firstarc=p;G.vertices[i];}return 0;}int InitStack(SqStack &S){S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base) exit (-1);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return 0;}int Push(SqStack &S,SElemType e){if(S.top-S.base>=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+STAXKINCREMENT)*size of(SElemType));if(!S.base) exit (-1);S.top=S.base+S.stacksize;S.stacksize+=STAXKINCREMENT;}*S.top++=e;return 0;}int Pop(SqStack &S,SElemType &e){if(S.top==S.base) return -1;e=*--S.top;return 0;}int StackEmpty(SqStack S){if(S.top==S.base) return -1;else return 0;}void FindInDegree(ALGraph G,int *indegree){int i;for(i=0;i<G.vexnum;i++)indegree[i]=0;for(i=0;i<G.vexnum;i++)while(G.vertices[i].firstarc){indegree[G.vertices[i].firstarc->adjvex]++;G.vertices[i].firstarc=G.vertices[i].firstarc->nextarc;}}int TopologicalSort(ALGraph G){int i,k,indegree[MAX_VERTEX_NUM];ArcNode *p;SqStack S;FindInDegree(G,indegree);InitStack(S);for(i=0;i<G.vexnum;i++)if(!indegree[i]) Push(S,i);int count=0;while(!StackEmpty(S)){Pop(S,i);cout<<i+1<<'\t'; ++count;for(p=G.vertices[i].firstarc; p; p=p->nextarc){k=p->adjvex;if(!(--indegree[k])) Push(S,k);}}if(count<G.vexnum) return -1;else return 0;}int main(){ALGraph G;CreateDG(G);TopologicalSort(G); return 0;}。
