拓扑排序和关键路径

拓扑排序和关键路径

 

拓扑排序

拓扑排序最大的用途就是判断一个有向图是否有环，当然判断还有一种方法就是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

  

小结

这篇文章讲了有关有向无环图的两个应用，最要将能熟悉拓扑排序和关键路径的算法的原理就能加以应用。如果你有任何建议或者批评和补充，请留言指出，不胜感激，更多参考请移步互联网。