对这个有向图进行拓扑排序
/*
* 拓扑排序(采用邻接矩阵存储)
*/
#include<stdio.h>
#define MAX_VERTEX_NUM 20
//图的定义
typedef struct
{
int vertexNum;
char vertex[MAX_VERTEX_NUM];
int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
}Graph,*PGraph;
//构造有向图
void createdGraph(PGraph g)
{
int i,j;
g->vertexNum=6;
for(i=0;i<g->vertexNum;i++)
g->vertex[i]='A'+i;
for(i=0;i<g->vertexNum;i++)
for(j=0;j<g->vertexNum;j++)
g->arc[i][j]=0;
g->arc[0][1]=1;
g->arc[0][2]=1;
g->arc[0][3]=1;
g->arc[1][4]=1;
g->arc[2][1]=1;
g->arc[2][4]=1;
g->arc[4][3]=1;
g->arc[4][5]=1;
}
//拓扑排序
void TopologicalSort(PGraph g)
{
int i,j,k=0,m;
char vertex[MAX_VERTEX_NUM];
while(k < g->vertexNum){
//1.找没有入度的顶点,存入数组vertex中
for(i=0;i<g->vertexNum;i++){
for(j=0;j<g->vertexNum;j++){
if(g->arc[j][i]!=0)
break;
}
if(j==g->vertexNum){
//检查g->vertex[i]是否已经遍历
for(m=0;m<k;m++)
if(vertex[m]==g->vertex[i])
break;
if(m==k){
vertex[k++]=g->vertex[i];
break;
}
}
}
//2.没有入度为0的顶点
if(i==g->vertexNum){
printf("存在回路!\n");
return ;
}
//3.删除这个顶点的出度
for(j=0;j<g->vertexNum;j++)
g->arc[i][j]=0;
}
//输出排序后的结果
printf("拓扑排序结果:\n");
for(i=0;i<k;i++)
printf("%-3c",vertex[i]);
printf("\n");
}
void main()
{
Graph graph;
createdGraph(&graph);
TopologicalSort(&graph);
}
- 大小: 23.6 KB
分享到:
相关推荐
C语言实现图的拓扑排序
C语言实现拓扑排序 数据结构 C语言实现拓扑排序 数据结构
拓扑排序,拓扑排序C语言代码,文档内包含完整的实现C代码
在C语言下利用C语言创建AOE网,并进行拓扑排序。功能模块包含图的创建,图的输出及拓扑排序。
/*----------------输出拓扑排序-------------*/ int topsort(linkmap *map) { int k=0,i,j,v,tag[100];//tag用来标记是否已访问到 int queue[100];//用队列存储 int front=0,real=0; edgenode *p; for(i=0;i...
C实现的拓扑排序,有详细注释,有问题的我们一起讨论
通过对一个AOV 网实例进行拓扑排序的问题的分析与求解,从程序实现的角度验证拓扑序 列的不唯一性。
c语言实现的AOV网的拓扑排序算法,采用动态创建邻接表的方法实现图的构建,内有输入示意图,含有较多的代码注释,欢迎下载学习!!!
C语言实现课程的拓扑排序,可以对输入的课程进行排序输出。
阅读了《数据结构(C语言)》的经典著作后...本次算法课程设计运用所学的图论的拓扑排序和关键路径,去实现工程中的花费时间和顺利进行问题。拓扑排序主要用于检验工程能否施工,关键路径主要用于看出工程施工时间消耗。
山大 数据结构课程设计,基于拓扑排序的排课程序,已有流传,请勿直接引用,否则后果自负。
求出有向无环图的所有拓扑排序序列的C语言程序实现
包括插入排序、堆排序、归并排序、基数排序、快速排序、冒泡排序、桶排序、拓扑排序、希尔排序、选择排序。
课程要求 1、选择合适的存储结构,建立有向无环图,并输出该图; 2、实现拓扑排序算法; 3、运用拓扑排序实现对教学计划安排的检验。
C语言数据结构拓扑排序 学校每个学期开设的课程是有先后顺序的,如物联网专业:开设《数据结构》课程之前,必须先开设《程序设计基础》和《离散数学》课程,现在需要根据给定的课程信息和课程之间的先后关系,合理...
C语言数据结构的重要部分——图,还有一个工程中常用的排序——拓扑排序,引入了栈的思想,对工程进行关键路径查询,学习数据结构的朋友可以看看噢!内附具体代码
二叉排序树.txt 二叉树.txt 二叉树实例.txt 二进制数.txt 二进制数2.txt 余弦曲线.txt 余弦直线.txt 傻瓜递归.txt 冒泡排序.txt 冒泡法改进.txt 动态计算网络最长最短路线.txt 十五人排序.txt 单循环...
数据结构 广度 深度 拓扑 最短路径 最小生成树 c语言的算法实现
设计一个应用程序(C/C++)...5.图的基本操作及应用①创建(邻接矩阵/邻接表)②遍历(深度/广度)③定位④找第一个邻接点⑤找下一个邻接点⑥插入(点/边)⑦删除(点/边)⑧应用,图的应用,如拓扑排序、关键路径等。