内容发布更新时间 : 2024/5/18 11:32:22星期一 下面是文章的全部内容请认真阅读。

实验题目：

图的应用

实验目的：

（1）熟练掌握图的基本存储方法；

（2）熟练掌握图的深度优先和广度优先搜索方法； （3）掌握AOV网和拓扑排序算法； （4）掌握AOE网和关键路径。

实验内容：

拓扑排序。

任意给定一个有向图，设计一个算法，对它进行拓扑排序。拓扑排序算法思想：a.在有向图中任选一个没有前趋的顶点输出；b.从图中删除该顶点和所有以它为尾的弧；c.重复上述a、b，直到全部顶点都已输出，此时，顶点输出序列即为一个拓朴有序序列；或者直到图中没有无前趋的顶点为止，此情形表明有向图中存在环。

设计分析：

为实现对无权值有向图进行拓扑排序，输出拓扑序列，先考虑如何存储这个有向图。拓扑排序的过程中要求找到入度为0的顶点，所以要采用邻接表来存储有向图，而要得到邻接表，则先要定义有向图的邻接矩阵结构，再把邻接矩阵转化成邻接表。

在具体实现拓扑排序的函数中，根据规则，当某个顶点的入度为0（没有前驱顶点）时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1，为了避免重复检测入度为0的顶点，设立一个栈St，以存放入度为0的顶点。

源程序代码：

#include

#include

#define MAXV 10 // 最大顶点个数

typedef struct {

typedef struct ANode { int adjvex; // 该弧的终点位置

int edges[MAXV][MAXV]; // 邻接矩阵的边数组

int n; // 顶点数

}MGraph;

struct ANode * nextarc; // 指向下一条弧的指针

}ArcNode;

typedef struct { int no; // 顶点信息 int count; // 顶点入度 ArcNode * firstarc; // 指向第一条弧 }VNode, AdjList[MAXV];

typedef struct { AdjList adjlist; // 邻接表 int n; // 图的顶点数 }ALGraph;

void MatTolist(MGraph g, ALGraph * &G) { int i, j, n=g.n; }

ArcNode * p;

G = (ALGraph *)malloc(sizeof(ALGraph)); for (i=0; iadjlist[i].firstarc = NULL; for (i=0; i=0; j--)

if (g.edges[i][j]!=0) { }

p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex = j;

p->nextarc = G->adjlist[i].firstarc; G->adjlist[i].firstarc = p;

G->n=n;

void TopSort(ALGraph * G) {

int i,j,flag=0,a[MAXV];

int St[MAXV], top = -1; // 栈St的指针为top ArcNode * p;

for (i=0; in; i++) // 入度置初值为0 G->adjlist[i].count = 0;

for (i=0; in; i++) // 求所有顶点的入度 {

}

}

p=G->adjlist[i].firstarc;

while (p!=NULL) { G->adjlist[p->adjvex].count++; p=p->nextarc; }

for (i=0; in; i++) if (G->adjlist[i].count==0) // 入度为0的顶点进栈

{

top++; St[top] = i; }

while (top>-1) // 栈不为空时循环 { i = St[top]; top--; // 出栈 a[flag++]=i; // 输出顶点

p=G->adjlist[i].firstarc; // 找第一个相邻顶点 while (p!=NULL) { }

j = p->adjvex; G->adjlist[j].count--;

if (G->adjlist[j].count==0) { top++; St[top] = j; // 入度为0的相邻顶点进栈 }

p = p->nextarc; // 找下一个相邻顶点

}

if (flagn) printf(\该图存在回路，不存在拓扑序列!\\n\else { printf(\该图的一个拓扑序列为:\ for(i=0; i

printf(\printf(\

void main() {

int i, j; MGraph g; ALGraph * G;