- 浏览: 1395995 次
- 性别:
- 来自: 广州
文章分类
最新评论
-
sdgxxtc:
[quo[color=red]te][/color]
C#使用OleDb读取Excel,生成SQL语句 -
zcs302567601:
博主,你好,一直都有个问题没有搞明白,就是 2.x的版本是通过 ...
NGUI所见即所得之UIPanel -
一样的追寻:
感谢楼主!
有向强连通和网络流大讲堂——史无前例求解最大流(最小割)、最小费用最大流 -
cp1993518:
感谢!从你的博客里学到了很多
Unity日志工具——封装,跳转 -
cp1993518:
学习了~,话说现在的版本custom还真的变委托了
NGUI所见即所得之UIGrid & UITable
拓扑排序和关键路径
拓扑排序
拓扑排序最大的用途就是判断一个有向图是否有环,当然判断还有一种方法就是Floyd算法。如果用邻接表的话拓扑排序的时间复杂度是O(N*E),邻接矩阵是O(N^2),N表示顶点数,E表示边数,Floyd时间复杂度是O(N^3)。
拓扑排序方法可分为无前趋的顶点优先的拓扑排序方法和无后继的顶点优先的拓扑排序方法。
基本拓扑排序算法步骤
1.在有向图中任选一个没有前驱的顶点输出
2.从图中删除该顶点和所有以它为起点的边
3.重复1和2,直到全部顶点都以输出
拓扑排序的实现(无前趋的顶点优先的拓扑排序方法)
邻接表实现(使用stack存储)
/********************************** title: 拓扑排序(邻接表实现) author: jay chang date: 2009/07/16 **********************************/ #include<iostream> #define MAXSIZE 99 #define TRUE 1 #define FALSE 0 using namespace std; typedef char VertexData; typedef int AdjType; typedef struct Stack //定义栈 { int data[MAXSIZE+1]; int top; }Stack; typedef struct ArcNode //定义弧结点 { AdjType adj; ArcNode *nextArc; }ArcNode; typedef struct VertexNode //定义顶点 { VertexData vertexData; ArcNode *firstArc; }VertexNode; typedef struct AdjMatrix //定义图 { VertexNode vertexNodes[MAXSIZE+1]; int verNum,arcNum; }AdjMatrix; //全局变量 int indegree[MAXSIZE+1]={0}; int LocateGraph(AdjMatrix *g, VertexData vertexData) { int iIndex; for(iIndex=1;iIndex<=g->verNum;iIndex++) { if(vertexData==g->vertexNodes[iIndex].vertexData) return iIndex; } return FALSE; } void CreateGraph(AdjMatrix *g) { int iCount,arcStart,arcEnd;char start,end; cout<<"*****************************************"<<endl; cout<<"*** 拓扑排序\n"; cout<<"*** Author: Jay Chang\n"; cout<<"*****************************************"<<endl; cout<<"输入有向无环图的顶点,及弧数\n"; cin>>g->verNum>>g->arcNum; cout<<"输入有向无环图的顶点信息\n"; ArcNode *q=NULL; for(iCount=1;iCount<=g->verNum;iCount++) { cout<<"输入第"<<iCount<<"个顶点的信息"<<endl; cin>>g->vertexNodes[iCount].vertexData; g->vertexNodes[iCount].firstArc=NULL; } for(iCount=1;iCount<=g->arcNum;iCount++) { cout<<"输入第"<<iCount<<"条弧的起始与结束的信息"<<endl; cin>>start>>end; arcStart=LocateGraph(g,start); arcEnd =LocateGraph(g,end); //添加弧结点 q=(ArcNode*)malloc(sizeof(ArcNode)); q->adj=arcEnd; q->nextArc=g->vertexNodes[arcStart].firstArc; g->vertexNodes[arcStart].firstArc=q; //对于第arcEnd个顶点的入度值加1 indegree[arcEnd]++; } } //判栈空 int IsEmpty(Stack *stack) { return stack->top==-1?TRUE:FALSE; } //初始化栈 void InitStack(Stack *stack) { stack->top=-1; } //出栈 void Pop(Stack *stack,int *iIndex) { *iIndex=stack->data[stack->top--]; } //进栈 void Push(Stack *stack,int value) { stack->data[++stack->top]=value; } //拓扑排序 int Topological(AdjMatrix *g) { int iCount,count=0; Stack *stack=(Stack*)malloc(sizeof(Stack)); InitStack(stack); ArcNode *p=NULL; //对于入度为0的顶点入栈 for(iCount=1;iCount<=g->verNum;iCount++) { if(indegree[iCount]==0){ Push(stack,iCount); } } cout<<"输出拓扑序列\n"; //输出顶点后,将与该顶点相连的顶点的边删除,将与相连顶点的入度减1,如减后为0,入栈,栈空结束 while(!IsEmpty(stack)) { Pop(stack,&iCount); cout<<g->vertexNodes[iCount].vertexData<<" "; count++; p=g->vertexNodes[iCount].firstArc; while(p!=NULL) { if(--indegree[p->adj]==0) Push(stack,p->adj); p=p->nextArc; } }//end while if(count<g->verNum){ cout<<"有回路"<<endl; return FALSE; } cout<<endl; } int main() { AdjMatrix *g=(AdjMatrix*)malloc(sizeof(AdjMatrix)); CreateGraph(g); Tuopu(g); return 0; }
转自http://jaychang.iteye.com/blog/702073
基于DFS实现(无后继的顶点优先的拓扑排序方法)
#include<iostream> using namespace std; int timef = 0; int n ; int a[1000][1000];// 图的邻接矩阵 int f[1000]; //完成时间 int vis[1000]; //1代表 被发现 2代表 已完成 void DFS(int u) { vis[u] = 1; //记录发现时刻 for(int v=1; v<=n; v++) //adj(u) //O(E) if(a[u][v] && vis[v]==0) DFS(v); vis[u] = 2; //记录完成时刻 timef++; f[u] = timef; } void DFS_main() //O(V+E) { timef = 0; for(int i=1; i<=n; i++) /// O(V) { if(vis[i] == 0) DFS(i); } } void Topological_sort() //O(V+E) { int tp[1000]; ////存放拓扑序列1..V DFS_main(); for(int i=1; i<=n; i++) //按finish的时间倒序存放在tp序列tp中 tp[n-f[i]+1] = i; for(int i=1; i<=n; i++) cout<<tp[i]<<" "; cout<<endl; } int main() { memset(vis,0,sizeof(vis)); cin>>n; for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) cin>>a[i][j]; Topological_sort(); system("pause"); return 0; }
转自http://blog.sina.com.cn/s/blog_6ec5c2d00100szit.html
关键路径
相关量介绍,设源点v0,汇点vn-1:
ve(i)表示事件vi最早发生的时间,vl(i)表示事件vi最晚发生的时间。
ve(0)=0,按拓扑排序计算ve(i)的值,ve(j)=max{ve(i)+w(i,j)|<i,j>∈E}。
vl(n-1)=ve(n-1),vl(i)按逆拓扑排序进行计算,vl(i)=min{vl(j)-w(i,j)|<i,j>∈E}。
活动<i,j>最早开始时间ee(i)=ve(i);活动<i,j>最晚开始时间el(i,j)=vl(j)-w(i,j),如果el(i,j)=ee(i,j),则活动<i,j>是关键活动。
关键路径算法的流程
1.以拓扑排序的次序按ve(j)=max{ve(i)+w(i,j)|<i,j>∈E}计算各个顶点(事件)最早发生的时刻
2.以逆拓扑排序的次序按vl(j)=min{ve(i)+w(i,j)|<i,j>∈E}计算各个顶点(事件)最晚发生的时刻
3.计算每个活动<i,j>发生的最早时间ee(i,j)和最晚时间el(i,j),如果满足ee(i,j)=el(i,j)则是关键路径并输出。
关键路径算法实现
#include <iostream> using namespace std; #define MAX 10000000 #define MAX_VERTEX_NUM 20 int ve[MAX_VERTEX_NUM]; /*顺序栈的定义*/ #define Stack_Size 100 typedef struct sqStack { int *elem; int top; int stackSize;//栈数组长度 }sqStack; /*顺序栈的初始化*/ void initStack_Sq(sqStack &S) { S.elem=new int[Stack_Size]; S.top=-1; S.stackSize=Stack_Size; } /*入栈*/ void push(sqStack &S,int x) { if(S.top==Stack_Size-1) cout<<"Stack Overflow!"; S.elem[++S.top]=x; } /*出栈*/ int pop(sqStack &S) { int x; if(S.top==-1) cout<<"Stack Empty!"; x=S.elem[S.top--]; return x; } typedef struct EdgeNode {//边表结点的定义 int adjvex;//存放邻接点在顶点表中的位置 struct EdgeNode * nextedge;//指向下一个边表结点 int weight; }EdgeNode; typedef struct VexNode {//顶点表结点的定义 char vex;//存放顶点信息 EdgeNode * firstedge;//指向第一个边表结点 int indegree; }VexNode; typedef struct {//顶点表的定义 VexNode vexs[MAX_VERTEX_NUM]; int vexnum,edgenum; }LGraph; /*构造有向图的邻接表*/ void CreateDG_AL(LGraph &G,int n,int e) { int i,j,k,w; G.vexnum=n; G.edgenum=e; for(i=0;i<n;i++) { cin>>G.vexs[i].vex; G.vexs[i].firstedge=NULL;//初始化为空 } for(k=0;k<e;k++) { EdgeNode *p; cin>>i>>j>>w; p=new EdgeNode; p->adjvex=j; p->weight=w; p->nextedge=G.vexs[i].firstedge; G.vexs[i].firstedge=p;//采用头插法 } } //拓扑排序并求各顶点事件的最早发生时间及拓扑逆序列 void TopoSort(LGraph &G,sqStack &T) { sqStack S; initStack_Sq(S); EdgeNode *p; int count=0; int i; for(i=0;i<G.vexnum;i++) G.vexs[i].indegree=0;//初始化为0 for(i=0;i<G.vexnum;i++) {//计算各个顶点的入度 p=G.vexs[i].firstedge; while(p) { G.vexs[p->adjvex].indegree++; p=p->nextedge; } } for(i=0;i<G.vexnum;i++) if(G.vexs[i].indegree==0) push(S,i);//将度为0的顶点入栈,这里进栈的是入度为0的顶点在数组中的位置 for(i=0;i<G.vexnum;i++) ve[i]=0;//初始化顶点事件的最早发生时间为0 while(S.top!=-1) { i=pop(S); cout<<G.vexs[i].vex<<" ";//将栈顶的元素出栈且输出,即将入度为0的顶点输出 push(T,i);//为了求得拓扑序列的逆序列,将元素依次进栈就得到了逆序列 count++;//计数器加1 p=G.vexs[i].firstedge;//让p指向入度为0的顶点的第一个边表结点 while(p) { int k; int dut; dut=p->weight; k=p->adjvex; G.vexs[k].indegree--;//将入度为0的顶点的邻接点的入度减1 if(G.vexs[k].indegree==0) push(S,k);//度减1后的顶点如果其入度为0,则将其入栈 if(ve[i]+dut>ve[k]) ve[k]=ve[i]+dut;//经过while循环,将顶点事件的所有邻接点的最早发生时间算出来, //并且经过外层的while循环,不断地更新为较大的ve[k]值 p=p->nextedge; } } cout<<endl; if(count<G.vexnum) cout<<"Network G has citcuits!"<<endl; } //求关键路径和关键活动 void CriticalPath(LGraph &G) { int i,j,k,dut; int ee,el; int vl[MAX_VERTEX_NUM]; EdgeNode *p; sqStack T; initStack_Sq(T); TopoSort(G,T); for(i=0;i<G.vexnum;i++) vl[i]=ve[G.vexnum-1];//初始化顶点事件的最迟发生时间为汇点的最早发生时间 //因为求最迟发生时间是从汇点向源点开始计算的 while(T.top!=-1) {//经过while循环,按堆栈顺序求出每个顶点的最迟发生时间 for(j=pop(T),p=G.vexs[j].firstedge; p ;p=p->nextedge) {//这里应该注意for循环的机制:每一次循环都要判断一次条件,包括第一次 k=p->adjvex; dut=p->weight; if(vl[k]-dut<vl[j]) vl[j]=vl[k]-dut;//按堆栈T中事件的顺序,将该顶点事件的最迟发生时间经过for循环算出来, //注意:经过for循环算出的是一个顶点的最迟发生时间 } } for(i=0;i<G.vexnum;i++) {//依次遍历每一个活动 for(p=G.vexs[i].firstedge;p;p=p->nextedge) { k=p->adjvex; dut=p->weight; ee=ve[i];//求活动的最早开始时间 el=vl[k]-dut;//求活动的最迟开始时间 if(ee==el) {//若两者相等,说明这这个活动为关键活动 cout<<"("<<G.vexs[i].vex<<","<<G.vexs[k].vex<<")"<<dut<<" "; cout<<"ee="<<ee<<","<<"el="<<el<<endl; } } } } void main() { freopen("in.txt","r",stdin); LGraph G; CreateDG_AL(G,9,11); CriticalPath(G); }
转自http://blog.csdn.net/hackerain/article/details/6054188
小结
这篇文章讲了有关有向无环图的两个应用,最要将能熟悉拓扑排序和关键路径的算法的原理就能加以应用。如果你有任何建议或者批评和补充,请留言指出,不胜感激,更多参考请移步互联网。
发表评论
-
C# 调用Delegate.CreateDelegate方法出现“未处理ArgumentException”错误解决
2013-05-31 12:24 3471在C# 调用Delegate.Create ... -
数组问题集结号
2012-12-06 22:01 0数组是最简单的数据结构,数组问题作为公司招聘的笔试和面试题目 ... -
算法问题分析笔记
2012-12-05 11:59 01.Crash Balloon Zhejiang Univer ... -
Java基础进阶整理
2012-11-26 09:59 2256Java学习笔记整理 ... -
Java学习笔记整理
2012-11-24 23:43 211Java学习笔记整理 本文档是我个人 ... -
《C++必知必会》学习笔记
2012-11-24 23:40 2561《C++必知必会》学 ... -
《C++必知必会》学习笔记
2012-11-24 23:34 1《C++必知必会》学习笔 ... -
基本技术——贪心法、分治法、动态规划三大神兵
2012-11-03 19:30 0基本技术——贪心法、分治法、动态规划三大神兵 -
优先队列三大利器——二项堆、斐波那契堆、Pairing 堆
2012-11-03 13:12 35465优先队列三大利器——二项堆、斐波那契堆、Pairing ... -
优先队列三大利器——二项堆、斐波那契堆、Pairing 堆
2012-11-03 13:01 3优先队列三大利器——二项堆、斐波那契堆、Pairing 堆 ... -
排序算法群星豪华大汇演
2012-10-30 00:09 3027排序算法群星豪华大汇演 排序算法相对简单些,但是由于 ... -
分布排序(distribution sorts)算法大串讲
2012-10-29 15:33 4564分布排序(distribution sorts)算法大串讲 ... -
归并排序(merge sorts)算法大串讲
2012-10-29 10:04 8206归并排序(merge sorts)算法大串讲 ... -
交换排序(exchange sorts)算法大串讲
2012-10-29 00:22 4303交换排序(exchange sorts)算法大串讲 本 ... -
选择排序(selection sorts)算法大串讲
2012-10-28 12:55 3582选择排序(selection sorts)算法大串讲 本文内 ... -
插入排序(insertion sorts)算法大串讲
2012-10-28 11:30 2638插入排序(insertion sorts ... -
伸展树(Splay Tree)尽收眼底
2012-10-27 15:11 5400伸展树(Splay Tree)尽收眼底 本文内容 ... -
红黑树(Red-Black Tree)不在话下
2012-10-26 20:54 2110红黑树(Red-Black Tree) 红黑树定义 红黑树 ... -
平衡二叉树(AVL)原理透析和编码解密
2012-10-26 10:22 2863平衡二叉树(AVL)原理透析和编码解密 本文内容 ... -
Trie三兄弟——标准Trie、压缩Trie、后缀Trie
2012-10-26 01:45 10555Trie三兄弟——标准Trie ...
相关推荐
图的最短路径、拓扑排序和关键路径相关算法描述,有c++code
阅读了《数据结构(C语言)》的经典著作后...本次算法课程设计运用所学的图论的拓扑排序和关键路径,去实现工程中的花费时间和顺利进行问题。拓扑排序主要用于检验工程能否施工,关键路径主要用于看出工程施工时间消耗。
数据结构课程设计——拓扑排序和关键路径的求解
拓扑排序与关键路径,在日常生活中,一项大的工程可以看作是由若干个子工程(这些子工程称为“活动” )组成的集合,这些子工程(活动)之间必定存在一些先后关系,即某些子工程(活动)必须在其它一些子工程(活动...
拓扑排序与关键路径.pptx拓扑排序与关键路径.pptx拓扑排序与关键路径.pptx拓扑排序与关键路径.pptx拓扑排序与关键路径.pptx拓扑排序与关键路径.pptx拓扑排序与关键路径.pptx拓扑排序与关键路径.pptx拓扑排序与关键...
创建一个带权的有向网,求拓扑序列,求关键路径。并输出每个事件的最早发生时间ve及v1最迟发生时间,每个活动的最早开始时间及最迟开始时间,关键活动,给出关键路径。
拓扑排序和关键路径PPT学习教案.pptx
第七章图(4)拓扑排序和关键路径.pdf
数据结构课程设计项目,邻接链表、关键路径以及拓扑排序的图形化显示,主要涉及到的技术有:前端、echarts、electron 给定一个有向图,完成: 建立并显示出它的邻接链表; 对该图进行拓扑排序,显示拓扑排序的结果,...
图的拓扑排序与关键路径的课件,大家可以看一看
拓扑排序关键路径算法C语言完整代码,vs2013下编译运行通过
数据结构课程设计项目,邻接链表、关键路径以及拓扑排序的图形化显示,主要涉及到的技术有:前端、echarts、electron 给定一个有向图,完成: 建立并显示出它的邻接链表; 对该图进行拓扑排序,显示拓扑排序的结果...
第4章 第7节 拓扑排序与关键路径(C++版)
对给定的AOV网判断网中是否存在环,检测的办法是对有向图构造其顶点的拓扑有序序列,若网中所有顶点都在它的拓扑有序序列中,则该AOV网中必定不存在环。在拓扑排序的基础上实现关键路径的的求解。
拓扑排序与关键路径学习教案.pptx
拓扑排序与关键路径PPT学习教案.pptx
拓扑排序、关键路径、最短路、折半查找判定树、二叉排序树、平衡二叉树、Hash表答案.ppt
第4章 第7节 拓扑排序与关键路径(C++版).ppt
C语言实现拓扑排序 数据结构 C语言实现拓扑排序 数据结构
用vc开发的图算法演示系统,包括图的遍历,最小代价生成树,最短路径,拓扑排序等。