博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
AOV网络拓扑排序
阅读量:6271 次
发布时间:2019-06-22

本文共 3861 字,大约阅读时间需要 12 分钟。

这个算法,主要是为输出一个无环图的拓扑序列

算法思想:

主要依赖一个栈,用来存放没有入度的节点,每次读取栈顶元素,并将栈顶元素的后继节点入度减一,如果再次出现入度为零的节点,就加入到栈中。参考《大话数据结构》,写下下面完整代码,并发现,其中程序的进行,出现错误。v6执行完,应该执行v9,因为此时v9是站顶元素,并不是v0.

算法流程:

int topGraph(graph g){    EdgeNode *e;    int i,k,gettop;    int top = 0 ;    int count = 0;    int *stack;    stack = (int *)malloc(g->numVertexes * sizeof(int));    for(i=0;i
numVertexes;i++){ if(g->headlist[i].in == 0) //把入度为0的,即没有入度的点入栈 stack[++top] = i; } while(top){ gettop = stack[top--]; printf("%d ",gettop); count++; for(e = g->headlist[gettop].fnode; e ; e=e->next){ //一次遍历链表,减少各个子节点的入度 k = e->data; if(!(--g->headlist[k].in)) stack[++top] = k; } } if(count < g->numVertexes) return ERROR; else return OK;}

全部代码:

#include 
#include
#define MAX 14#define ERROR 1#define OK 0typedef struct edgeNode{ int data; struct edgeNode *next;}EdgeNode;typedef struct headNode{ int in; int data; EdgeNode *fnode;}HeadNode,HeadList[MAX];typedef struct{ HeadList headlist; int numEdges,numVertexes;}Graph,*graph;void initGraph(graph g);int inputInfo(graph g,int tar,int in,int data,int first);void printGraph(graph g);int topGraph(graph g);int main(){ Graph *g = (Graph *)malloc(sizeof(Graph)); initGraph(g); printGraph(g); if(topGraph(g) == ERROR) printf("有环路!\n"); else printf("没有环路!\n"); free(g); getchar(); return 0;}int topGraph(graph g){ EdgeNode *e; int i,k,gettop; int top = 0 ; int count = 0; int *stack; stack = (int *)malloc(g->numVertexes * sizeof(int)); for(i=0;i
numVertexes;i++){ if(g->headlist[i].in == 0) //把入度为0的,即没有入度的点入栈 stack[++top] = i; } while(top){ gettop = stack[top--]; printf("%d ",gettop); count++; for(e = g->headlist[gettop].fnode; e ; e=e->next){ //一次遍历链表,减少各个子节点的入度 k = e->data; if(!(--g->headlist[k].in)) stack[++top] = k; } } if(count < g->numVertexes) return ERROR; else return OK;}void printGraph(graph g){ int i; printf("vertex:%d,edges:%d\n",g->numVertexes,g->numEdges); EdgeNode *e = (EdgeNode *)malloc(sizeof(EdgeNode)); for(i=0;i
headlist[i].in,g->headlist[i].data); e = g->headlist[i].fnode; while(e != NULL){ printf("->%d",e->data); e = e->next; } printf("\n"); } free(e);}void initGraph(graph g){ g->numVertexes = MAX; g->numEdges = 0; int i; for(i=0;i
headlist[i].fnode = NULL; } inputInfo(g,0,0,0,4); inputInfo(g,0,0,0,5); inputInfo(g,0,0,0,11); inputInfo(g,1,0,1,2); inputInfo(g,1,0,1,4); inputInfo(g,1,0,1,8); inputInfo(g,2,2,2,5); inputInfo(g,2,2,2,6); inputInfo(g,2,2,2,9); inputInfo(g,3,0,3,2); inputInfo(g,3,0,3,13); inputInfo(g,4,2,4,7); inputInfo(g,5,3,5,8); inputInfo(g,5,3,5,12); inputInfo(g,6,1,6,5); inputInfo(g,7,2,7,-1); inputInfo(g,8,2,8,7); inputInfo(g,9,1,9,10); inputInfo(g,9,1,9,11); inputInfo(g,10,1,10,13); inputInfo(g,11,2,11,-1); inputInfo(g,12,1,12,9); inputInfo(g,13,2,13,-1);}int inputInfo(graph g,int tar,int in,int data,int first){ g->numEdges++; if(first == -1){ //没有后继的边节点 g->headlist[tar].in = in; g->headlist[tar].data = data; return 1; } if(!g->headlist[tar].fnode){ //观察是否已经初始化 g->headlist[tar].in = in; g->headlist[tar].data = data; } EdgeNode *e = (EdgeNode *)malloc(sizeof(EdgeNode)); e->data = first; e->next = g->headlist[tar].fnode; g->headlist[tar].fnode = e; return 0;}

执行示例:

本文转自博客园xingoo的博客,原文链接:,如需转载请自行联系原博主。
你可能感兴趣的文章
[javase学习笔记]-8.3 statickeyword使用的注意细节
查看>>
Spring集成RabbitMQ-使用RabbitMQ更方便
查看>>
Nginx 设置域名转向配置
查看>>
.net core 实现简单爬虫—抓取博客园的博文列表
查看>>
FP-Tree算法的实现
查看>>
Android 用Handler和Message实现计时效果及其中一些疑问
查看>>
Dos命令删除添加新服务
查看>>
C#.NET常见问题(FAQ)-索引器indexer有什么用
查看>>
hadoop YARN配置参数剖析—MapReduce相关参数
查看>>
Java 正则表达式详细使用
查看>>
【ADO.NET】SqlBulkCopy批量添加DataTable
查看>>
SqlServer--bat批处理执行sql语句1-osql
查看>>
Linux系列教程(十八)——Linux文件系统管理之文件系统常用命令
查看>>
laravel安装初体验
查看>>
用yum查询想安装的软件
查看>>
TIJ -- 吐司BlockingQueue
查看>>
数据库分页查询
查看>>
[编程] C语言枚举类型(Enum)
查看>>
[Javascript] Compose multiple functions for new behavior in JavaScript
查看>>
ASP.NET MVC性能优化(实际项目中)
查看>>