实验六图的应用及其实现

实验六 图的应用及其实现

一、实验目的

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 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 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<<" 请输入该图的顶点数： "<<" 请输入该图的边数： "<

cin>>G.vexnum>>G.arcnum; for(i=0;i

{

G.vertices[i].data=i;

G.vertices[i].firstarc=NULL;

}

cout<<" 请输入一条边的始点和终点： "<

for(k=0;k

cout<<" 请输入第 "<

cin>>v1>>v2; i=v1; j=v2;

while(i<1||i>G.vexnum||j<1||j>G.vexnum)

{

cout<<" 请输入第 "<

cin>>v1>>v2;

i=v1; j=v2;

}

-- 2 精选文库

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+STAXKIN

CREMENT)*sizeof(SElemType));

if(!S.base) exit (-1);

S.top=S.base+S.stacksize;

S.stacksize+=STAXKINCREMENT;

}

*S.top++=e;

return 0;

}

4. 出栈

-- 3 精选文库

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

indegree[i]=0;

for(i=0;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

if(!indegree[i]) Push(S,i);

-- 4 精选文库

int count=0;

while(!StackEmpty(S))

{

Pop(S,i);

cout<

for(p=G.vertices[i].firstarc; p; p=p->nextarc)

{

k=p->adjvex;

if(!(--indegree[k])) Push(S,k);

}

}

if(count

四、函数的调用

主函数主要设计：

int main()

{

ALGraph G;

CreateDG(G);

TopologicalSort(G);

return 0;

}

五、实验总结

本次试验通过对有向图进行拓扑排序， 我了解了有向图邻接表的存储结构更重要的的是学会了对有向图的拓扑排序算法，其中也将之前学过的栈结合起来，巧妙的找到了一个拓扑序列，可不足的是，该算法只能找到这一条拓扑序列，但是我相信通过完成了这次试验后我会改进算法而能将图的所有的拓扑序列找出

来。

六、程序清单

#include

using namespace std;

typedef int InfoType;

typedef char VertexType;

-- 5 精选文库

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<<" 请输入该图的顶点数： "<<" 请输入该图的边数： "<

cin>>G.vexnum>>G.arcnum; for(i=0;i

{

G.vertices[i].data=i;

G.vertices[i].firstarc=NULL;

}

cout<<" 请输入一条边的始点和终点： "<

for(k=0;k

-- 6