精华内容
下载资源
问答
  • 2020-03-05 10:35:02

    图的总结

    图的总结

    拓扑排序精髓就是找点,indegree数组–

    方法一:没有用队列

    int inDegree[maxn] = { 0 };并在初始化时收集好每个点的入度。

    按照:

    • 找indegree=0的点
    • 删该点的边(其他点的入度)
    • 重复操作直到找到不到返回-1
    /*initialize map and degree*/
    void init()
    /*get dot in 0 degree*/
    int getDegree()
    /*delete chosen dot outdegree */
    void updateIndegree(int s)
    
    bool topologicalSort()
    {
    	int s, ans = N;
    	while (true)
    	{
    		s = getDegree();
    		book[s] = true;
    		if (s == -1) break;
    		ans--;
    		updateIndegree(s);
    	}
    	if (ans > 0)return false;
    	return true;
    }
    

    方法具体实现

    
    /*initialize map and degree*/
    void init()
    {
    	int u, v, w;
    	cin >> N >> M;
    	for (int i = 0; i < M; i++)
    	{
    		cin >> u >> v;
    		Adj[u].push_back(Node(v, 0));
    	}
    
    	memset(book, false, sizeof(book));
    	memset(inDegree, 0, sizeof(inDegree));
    	for (int i = 0; i < N; i++)
    	{
    		for (int j = 0; j < Adj[i].size(); j++)
    		{
    			int v = Adj[i][j].vertex;
    			inDegree[v]++;
    		}
    	}
    }
    /*get dot in 0 degree*/
    int getDegree()
    {
    	for (int i = 0; i < N; i++)
    	{
    		if (inDegree[i] == 0 && book[i] == false)
    			return i;
    	}
    	return -1;
    }
    /*delete chosen dot outdegree */
    void updateIndegree(int s)
    {
    	int v;
    	for (int i = 0; i < Adj[s].size(); i++)
    	{
    		v = Adj[s][i].vertex;
    		inDegree[v]--;
    	}
    }
    

    方法二:将入度为0的点加到队列;直到队列为空。

    bool topologicalSort()
    {
    	int ans = N;
    	queue<int> Q;
    	for (int i = 0; i < N; i++)
    	{
    		if (inDegree[i] == 0)
    			Q.push(i);
    	}
    	while (!Q.empty())
    	{
    		int u = Q.front(); Q.pop();
    		ans--;
    		for (int i = 0; i < Adj[u].size(); i++)
    		{
    			int v = Adj[u][i].vertex;
    			inDegree[v]--;
    			if (inDegree[v] == 0) {
    				Q.push(v);
    			}
    		}
    	}
    	if (ans > 0)return false;
    	return true;
    }
    

    可以将queue换成priority_queue或者set(自动去重并升序排序)改变拓扑访问顺序。

    实例:
    4 3
    0 1
    1 3
    0 2
    an:true
    4 5
    0 1
    0 2
    1 2
    2 3
    3 1
    an:false

    关键路径

    关键路径:最长路径长度=最短时间;最早开始时间=最迟开始时间。因为AOE活动开始的前提是前面的活动必须完成。(AOV+各活动所需要的时常=AOE)

    使用拓扑排序,求每个活动最早开始时间。》取到当前活动的最大值(初始值为0)
    不需要ans来记录,添加stack<int> topOrder来存储拓扑排序序列。

    使用逆拓扑排序,求每个活动最晚开始时间。》从后往前取最小值。(初始值都是最后终点的时间)

    #include<vector> 邻接表
    #include<stack>记录每次的拓扑排序序列
    #include<queue> 拓扑排序时的入度为0的点

    const int maxn = 100;
    const int INF = 0x3fffffff;
    struct Node
    {
    	int vertex;
    	int cost;
    	Node(int v,int c):vertex(v),cost(c){}
    };
    int N, M;
    vector<Node> Adj[maxn];
    int inDegree[maxn] = { 0 };
    
    //拓扑排序序列
    stack<int> topOrder;
    //活动最早开始时间,活动最迟开始时间
    int ve[maxn],vl[maxn];
    

    图初始化:

    void init()
    {
    	int u, v, w;
    	cin >> N >> M;
    	memset(inDegree, 0, sizeof(inDegree));
    	for (int i = 0; i < M; i++)
    	{
    		cin >> u >> v >> w;
    	}
    	for (int i = 0; i < N; i++)
    	{
    		for (int j; j < Adj[i].size(); j++) {
    			inDegree[Adj[i][j].vertex]++;
    		}
    	}
    }
    

    拓扑排序,并且得到拓扑序列

    bool topologicalSort() {
    	queue<int> Q;
    	for (int i = 0; i < N; i++)
    	{
    		if (inDegree[i] == 0)
    			Q.push(i);
    	}
    	int u, v;
    	while (!Q.empty())
    	{
    		u = Q.front(); Q.pop();
    		topOrder.push(u);
    		for (int j = 0; j < Adj[u].size(); j++)
    		{
    			v = Adj[u][j].vertex;
    			inDegree[v]--;
    			if (inDegree[v] == 0)
    				Q.push(v);
    
    			if (ve[u] + Adj[u][v].cost > ve[v]) {
    				//时间花费的更多;要选择更多的才能开始后面的
    				ve[v] = ve[u] + Adj[u][v].cost ;
    			}
    		}
    	}
    	if (topOrder.size() == N)return true;
    	return false;
    }
    

    关键路径

    int CriticalPath()
    {
    	memset(ve, 0, sizeof(ve));
    	if (topologicalSort() == false) {
    		return -1;
    	}
    	fill(vl, vl + N, ve[N - 1]);//关键路径长度
    	while (!topOrder.empty())
    	{
    		int u = topOrder.top(); 
    		topOrder.pop();
    		for (int j = 0; j < Adj[u].size(); j++)
    		{
    			int v = Adj[u][j].vertex;
    			if (vl[v] - Adj[u][j].cost < vl[u]) {
    				//选择更小的,松弛时间
    				vl[u] = vl[v] - Adj[u][j].cost;
    			}
    		}
    	}
    
    	//最早开始时间e,最迟开始时间l
    	for (int u = 0; u < N; u++)
    	{
    		for (int i = 0; i < Adj[u].size(); i++)
    		{
    			int v = Adj[u][i].vertex, cost = Adj[u][i].cost;
    			int e = ve[u], l = vl[u] - cost;
    			if (e == l) {
    				cout << u << v;
    			}
    		}
    	}
    	cout << ve[N - 1];
    }
    
    更多相关内容
  • 拓扑排序与关键路径,在日常生活中,一项大的工程可以看作是由若干个子工程(这些子工程称为“活动” )组成的集合,这些子工程(活动)之间必定存在一些先后关系,即某些子工程(活动)必须在其它一些子工程(活动...
  • 第七节 拓扑排序与关键路径 引入 AOV网 在日常生活中一项大的工程可以看作是由若干个子工程这些子工程称为 活动 组成的集合这些子工程活动之间必定存在一些先后关系即某些 子工程活动必须在其它一些子工程活动完成...
  • 超详细讲解实现拓扑排序关键路径

    千次阅读 多人点赞 2022-03-26 11:07:49
    今天,小编带着大家来学习图中非常重要的一环,拓扑排序关键路径! 首先,我们需要知道的是,拓扑排序关键路径的基础,正因如此,当我们知道了关键路径在生活中的应用,相信大家也就明白这两个算法的重要性了!...

    今天,小编带着大家来学习图中非常重要的一环,拓扑排序和关键路径!

    目录

    一. 绪论——实际应用

    二. 拓扑排序

    (一).含义

    (二).实现原理

     (三).代码实现

    三. 关键路径

    (一).含义

    (二).实现原理

     (三).代码实现


    首先,我们需要知道的是,拓扑排序是关键路径的基础,正因如此,当我们知道了关键路径在生活中的应用,相信大家也就明白这两个算法的重要性了!

    一. 绪论——实际应用

    我们以实际生活为例,让大家了解关键路径的应用。

    假设现在有一个工程,分为好多个步骤,每个步骤又需要不同的时间来完成,关键路径的作用就是让我们知道这个工程里有哪些步骤是不可替代的,会影响整个工期进行,而那些步骤即便慢一些也没关系,不会影响整个工期的。

    二. 拓扑排序

    (一).含义

    要了解拓扑排序的含义,我们首先要知道AOV网。AOV网就是不带权值有向不带环的网图。

    什么是不带环?

    上图理解!

    watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCx6KaBIOWuheWcqOWutg==,size_20,color_FFFFFF,t_70,g_se,x_16

     而拓扑排序就是基于AOV网图实现的,大家不要感觉说AOV网图条件太苛刻了,实际上我们的很多工程都是AOV网图,只有实现一个步骤才能进行下一个步骤,例如学习就是就是一个AOV网,我们只有学过c语言后才能学数据结构,才能学数据库以及之后的内容。

    拓扑排序就是把所有AOV网中的顶点都单次输出出来。

    (二).实现原理

    拓扑排序是基于邻接表实现的。

    实现拓扑排序,过程如下:

    首先我们需要创建一个,用来装入度为0的顶点。

    1.计算所有顶点的入度,入度为0的入栈

    2.出栈一个顶点a,a的入度为0,把它保存在一个int类型数组topo里

    3.从a开始走到它的下一个顶点b,把b的入度减1,再找一个入度为0的顶点入栈

    4.重复步骤2和步骤3,直到所有的顶点都走过为止。

    5.topo数组依次输出就是拓扑排序后的结果

    还是那句话,上图理解!

    watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCx6KaBIOWuheWcqOWutg==,size_20,color_FFFFFF,t_70,g_se,x_16

     (三).代码实现

    #define Maxvex 100
    typedef char vextype;
    typedef int undform;
    typedef struct arcnode//边表
    {
    	int arcnode;//此边节点对应顶点的下标
    	struct arcnode* nextarcnode;//下一个此根节点指向的边节点
    	int weight;//边的权值
    }Arcnode;
    
    typedef struct vexnode//节点表
    {
    	vextype val;//节点值
    	Arcnode* Nextarc;//节点指向的第一个边
    }Vexnode[Maxvex], onevexnode;
    
    typedef struct Graph//图
    {
    	Vexnode vexall;//所有的节点作为一个数组
    	int vexnum, arcnum;//节点,边的个数
    }Graph;
    bool ToPosort(Graph* gp, int * Topo)//拓扑排序
    {
    	int* indegree = (int*)new int[gp->vexnum];//建立入度数组
    	memset(indegree, 0, sizeof(int) * gp->vexnum);
    	std::stack<int> st;//建立栈
    	for (int i = 0; i < gp->vexnum; i++)//计算所有顶点的入度
    	{
    		arcnode* node = gp->vexall[i].Nextarc;
    		while (node != NULL)
    		{
    			indegree[node->arcnode]++;
    			node = node->nextarcnode;
    		}
    	}
    	for (int i = 0; i < gp->vexnum; i++)//入度为0入栈
    	{
    		if (indegree[i] == 0)
    		{
    			st.push(i);
    		}
    	}
    	int size = 0;//判断多少个顶点无环
    	int topo_i = 0;
    	while (!st.empty())
    	{
    		int i = st.top();
    		st.pop();
    		Topo[topo_i++] = i;//顶点入拓扑序列
    		size++;
    		arcnode* node = gp->vexall[i].Nextarc;
    		while (node != NULL)
    		{
    			--indegree[node->arcnode];
    			if (indegree[node->arcnode] == 0)
    			{
    				st.push(node->arcnode);
    			}
    			node = node->nextarcnode;
    		}
    	}
    	if (size == gp->vexnum) return true;
    	else return false;
    }

    三. 关键路径

    (一).含义

    小编想了好久,决定还是用实例来给大家解释关键路径到底是个什么东西。相信大家看完就能完全理解了!

    假设现在有一个工程,分为好多个步骤,每个步骤又需要不同的时间来完成,我们可以用一个带权有向无环图——AOE网来表示,顶点代表步骤,边的权值代表步骤1开始执行下一步将要开始所需时间。

    图来表示就是这样:

    watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCx6KaBIOWuheWcqOWutg==,size_20,color_FFFFFF,t_70,g_se,x_16

    例图的意思就是从以顶点1代表的起始步骤到以顶点9代表的终点步骤,该工程可以经过这里头的某些顶点步骤来完成。

    由图可知该工程可以经历的路径共有4条,分别是:

    ①1->2->3->6->8->9   完工时间:1+2+2+4+2=11h

    ②1->4->5->6->7->9   完工时间:1+1+1+3+1=7h

    ③1->2->3->6->7->9   完工时间:1+2+2+3+1=9h

    ④1->4->5->6>8->9    完工时间:1+1+1+4+2=9h

    而但每条路径从开工到完成所需的时间是不同的,该工程最短7h完成,最长11h完成,而关键路径就是用来算我们确保工程一定能完成的情况下,该步骤时间的改变一定会影响总工期的时间。

    什么意思?

    我们以该图为例,最长时间11h就是该工程一定能完成的时间,因为在11h内该工程不管采用那条路径都能完成。

    1->2->3->6->8->9就是这里边的关键路径,因为这里边的每一个步骤都没有余量时间,而没有余量时间的步骤就是改变该步骤时间就一定会影响工期的步骤

    余量时间:我们拿3和5步骤为例,3到6是2h,5到6是1h,这说明5到6与3到6相比有1小时的空余,这就是余量时间。3就是没有余量时间,而5就是有余量时间。

    关键路径就是这些没有余量时间的步骤所连起来的一条通路

    (二).实现原理

    关键路径的实现是基于拓扑排序的

    其次,我们还需要一个int类型数组etv来存放顶点的最早发生时间, int类型数组ltv来存放顶点的最晚发生时间。小编看来看,我们要是想学好关键路径,必须要彻底清楚什么是最早最晚发生时间。

    最早发生时间:该顶点在允许的时间范围内,最早进入下一顶点的时间。

    最晚发生时间:该顶点在允许的时间范围内,最晚进入下一顶点的时间。

    举个例子:

    watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCx6KaBIOWuheWcqOWutg==,size_20,color_FFFFFF,t_70,g_se,x_16

     以该图为例,关键路径是a->c->e->f,所以对于b->d而言有两种选择:

    一是早早完成,歇着,这是最早发生时间,值是1,因为a->b需要1小时;

    二是先歇着,等到能和c->e一起完成时再开始,这是最晚发生时间,值是2,因为是a->b加歇的1小时

    我们用拓扑序列topo数组从头开始依次算每个顶点的最早发生时间,因为topo数组是按从图头开始依次存放直到图尾,刚好符合顶点依次发生,所需时间是之前顶点时间的迭代。

    再从拓扑序列尾开始往前走,依次计算最晚发生时间,以d点为例,最晚发生时间就是f的最晚时间减d->f的时间,即5-1=4。

    所有顶点都算完etv与ltv后,遍历每个顶点,如果一个顶点的最早发生时间etv等于最晚发生ltv时间,那它就是关键路径的顶点。

    最后,打印每个关键路径的顶点到下一个关键路径顶点即可。

     (三).代码实现

    void CriticalPath(Graph* gp)//关键路径
    {
    	cout << "****************CriticalPath*******************\n";
    	int* topo = (int*)new int[gp->vexnum];
    	if (!ToPosort(gp, topo))//判断是否带环
    	{
    		cout << "非AOE图!";
    		return;
    	}
    	int* etv = (int*)new int[gp->vexnum];//顶点最早发生时间 
    	int* ltv = (int*)new int[gp->vexnum];//顶点最晚发生时间
    	for (int i = 0; i < gp->vexnum; i++)//初始化etv
    	{
    		etv[i] = 0;
    	}
    	for (int i = 0; i < gp->vexnum; i++)//建立最早时间etv
    	{
    		arcnode* node = gp->vexall[topo[i]].Nextarc;//拓扑序列中该顶点的第一条边,下标是拓扑序列值,即topo[i]作为下标!
    		while (node != NULL)
    		{
    			if (etv[node->arcnode] < etv[topo[i]] + node->weight)
    				//存最早时间,但是最早时间定义是确保事件一定能发生,要想一定能发生,那么就该取时间最长的路径,这就是最早发生时间
    				etv[node->arcnode] = etv[topo[i]] + node->weight;
    			node = node->nextarcnode;
    		}
    	}
    	for (int i = 0; i < gp->vexnum; i++)//初始化最晚发生时间
    	{
    		ltv[i] = etv[topo[gp->vexnum - 1]];//注意!这里是用topo序列的值来作为下标的,拓扑序列的尾才是图的尾
    	}
    	for (int i = gp->vexnum - 1; i >= 0; i--)//建立最晚时间ltv
    	{
    		arcnode* node = gp->vexall[topo[i]].Nextarc;//从拓扑序列尾端开始,所以用topo[i]来作为下标!
    		while (node != NULL)
    		{
    			if (ltv[topo[i]] > ltv[node->arcnode] - node->weight)
    				// 节点顺序关系:  i -> node
    				ltv[topo[i]] = ltv[node->arcnode] - node->weight;
    			node = node->nextarcnode;
    		}
    	}
    	for (int i = 0; i < gp->vexnum; i++)//判断关键路径并打印
    	{
    		arcnode* node = gp->vexall[i].Nextarc;
    		while (node != NULL)
    		{
    			if (ltv[node->arcnode] == etv[i] + node->weight)//注意要用最早发生时间加权值来与最晚发生时间相比
    				cout << gp->vexall[i].val << "->" << gp->vexall[node->arcnode].val << endl;
    			node = node->nextarcnode;
    		}
    	}
    }

    创作不易,恳求点赞支持😆 如有错误,敬请斧正

    展开全文
  • 第4章 第7节 拓扑排序与关键路径(C++版)
  • 拓扑排序关键路径 - C语言(图的应用)

    千次阅读 多人点赞 2019-11-30 16:29:30
    AOE-网在工程计划和经营管理中通常需要解决以下两个问题: 1)估算完成整项工程至少需要多长时间; 2)判断哪些活动是影响工程进度的关键

    一、 实验目的

    理解有向图的基本概念,掌握有向图的存储结构,实现有向图的拓扑排序关键路径算法.

    二、 实验内容

    通过编写程序,对示例图进行拓扑排序,进而求解示例图的关键路径。
    DAG
    具体步骤如下:

    1. 构造有向带权图;
    2. 定义拓扑排序函数判断图中是否存在回路;
    3. 定义关键路径求解函数;
    4. 主函数实现数据的输入及函数调用。

    三、 实验工具

    Dev - C++

    四、 实验代码

    //Authors:xiaobei
    
    #include<stdio.h>
    #include<stdlib.h>
    #define MVNum 100
    #define OK 1
    #define ERROR 0
    int topo[MVNum];        //定义拓扑排序数组 
    //邻接表结构的相关定义
    typedef struct ArcNode{       //边表 
     int adjvex;//该边所指向的顶点位置 
     struct ArcNode *nextarc;//指向下一条边的指针 
     char info;    //和边相关信息,权值 
    }ArcNode;
    typedef struct VNode{       //表头结点表 
     char data;
     ArcNode *firstarc;
    }VNode,AdjList[MVNum];
    typedef struct{         //邻接表,带权有向图 
     AdjList vertices;
     int vexnum,arcnum;
    }ALGraph;
    //链栈的相关定义
    typedef struct StackLink{
     int data;
     struct StackLink *next;
    }StackLink,*StackNode;
    int InitStack(StackNode &S){
     S = NULL;
     return OK;
    }
    int Push(StackNode &S,int e){
     StackNode p;
     p = (StackLink*)malloc(sizeof(StackLink));
     p->data = e;
     p->next = S;
     S = p;
     return OK;
    }
    int Pop(StackNode &S,int &e){
     StackNode p;
     p = (StackLink*)malloc(sizeof(StackLink));
     if(S==NULL)
      return  ERROR;
     e = S->data;
     p = S;      //用P临时存放栈顶元素,已备释放
     S = S->next; 
     free(p);
     return OK; 
    }
    int GetTop(StackNode S){
     if(S!=NULL)
      return S->data;
    }
    int StackEmpty(StackNode S){
     if(S!=NULL)
      return ERROR;
     else 
      return OK;
    }
    //函数返回顶点所在位置 
    int LocateVex(ALGraph G,char c){
     int i;
     for(i=0;i<G.vexnum;++i){
      if(c==G.vertices[i].data)
       return i;
     }
     return -1;
    }
    //函数用邻接表创建有向无环图 
    int CreateDAG(ALGraph &G){
     int i,j,k,weight;
     char v1,v2;
     ArcNode* p;
     printf("\n[请输入总顶点与总边数]:\n>>>");
     scanf("%d %d",&G.vexnum,&G.arcnum);
     for(i=0;i<G.vexnum;i++){         //输入各点,构造表头结点表 
      printf("\n[请依次输入顶点信息]:\n>>>");
      getchar();
      scanf("%c",&G.vertices[i].data);
      G.vertices[i].firstarc = NULL;
     }
     for(k=0;k<G.arcnum;k++){
      printf("\n[请输入各边及权值构造邻接表]:\n>>>");
      getchar();
      scanf("%c %c %d",&v1,&v2,&weight);
      i = LocateVex(G,v1);
      j = LocateVex(G,v2);
      p = (ArcNode*)malloc(sizeof(ArcNode));
      p->adjvex = j;
      p->info = weight;
      p->nextarc = G.vertices[i].firstarc;
      G.vertices[i].firstarc = p;
     }
     return  OK;
    }
    //函数求出每个顶点入度存入数组 indegree[] 
    void FindInDegree(ALGraph G,int indegree[]){
    //求有向图邻接表顶点入度,两种方法:1、建立逆邻接表,2、遍历整个邻接表 
    //这里采用遍历整个邻接表 
     ArcNode *p;
     int i;
     for(i=0;i<G.vexnum;i++)    //入度初始化为零 
      indegree[i] = 0;
     for(i=0;i<G.vexnum;i++){   //遍历邻接表 
      p = G.vertices[i].firstarc;
      while(p!=NULL){
       indegree[p->adjvex]++;
       p = p->nextarc;
      }
     }
    }
    //函数获得拓扑排序结果数组topo[] 
    int TopologicalSort(ALGraph G,int topo[]){
    //有向图G采用邻接表存储结构
    //若G无回路,则生成G的一个拓扑序列topo[]并返回OK,否则返回ERROR
     int i;
     ArcNode *p; 
     StackNode S;        //定义链栈 
     int indegree[MVNum];
     FindInDegree(G,indegree);     //求出各顶点入度,存入数组indegree中
     printf("各顶点入度:"); 
     printf("\n-----indegree-----\n");
     for(i=0;i<G.vexnum;i++){
      printf("%d",indegree[i]);
     }
     printf("\n-----indegree-----\n");
     InitStack(S);        //栈初始化为空 
     for(i=0;i<G.vexnum;i++){
      if(indegree[i]==0)
       Push(S,i);       //入度为零者入栈 
     }
     int m=0;
     while(!StackEmpty(S)){
      Pop(S,i);        //将栈顶顶点vi出栈 
      topo[m] = i;       //将vi保存在拓扑序列数组topo中 
      m++;         //对输出顶点计数 
      p=G.vertices[i].firstarc;    //p指向第一个邻接点
      while(p!=NULL){
       int k = p->adjvex;     //vk为vi的邻接点 
       indegree[k]--;      //vi的每个邻接点入度减1 
       if(indegree[k]==0)
        Push(S,k);      //若入度为0则入栈 
       p = p->nextarc;      //p指向vi的下一个邻接点 
      }
     }
     if(m<G.vexnum)        //判断有无回路 
      return ERROR;
     else
      return OK;
    }
    int CriticalPath(ALGraph G){
    //G为邻接表存储的有向网,输出G的各项关键活动
     ArcNode *p;
     int ve[MVNum];     //ve[MVNum]记录每个事件最早发生时间 
     int vl[MVNum];     //vl[MVNum]记录每个事件最迟发生时间 
     int i,j,k,e,l;
     if(!TopologicalSort(G,topo))
      return ERROR;    //调用拓扑排序算法,使拓扑序列保存在topo中;若调用失败,则存在有向环,返回ERROR
     int n = G.vexnum;    //n为顶点个数
     
     for(i=0;i<n;i++)
      ve[i] = 0;     //个每个事件的最早发生时间置初值0
     /*-----------------按拓扑次序求每个事件最早发生时间-----------------*/
     for(i=0;i<n;i++){
      k=topo[i];     //取得拓扑排序序列中顶点序号k 
      p = G.vertices[k].firstarc; //p指向k的第一个邻接顶点 
      while(p!=NULL){    //依次更新k的所有邻接顶点的最早发生时间 
       j = p->adjvex;   //j为邻接顶点的序号 
       if(ve[j]<ve[k]+p->info) //更新顶点j的最早发生时间ve[j] 
        ve[j] = ve[k]+p->info;
       p = p->nextarc;   //p指向k的下一个邻接顶点 
      }
     }
     for(i=0;i<n;i++)    //给每个事件的最迟发生时间置初值ve[n-1] 
      vl[i] = ve[n-1];
     /*-----------------按逆拓扑次序求每个事件最迟发生时间-----------------*/
     for(i=n-1;i>=0;i--){
      k = topo[i];    //取得拓扑排序序列中顶点序号k 
      p = G.vertices[k].firstarc; //p指向k的第一个邻接顶点
      while(p!=NULL){    //根据k的邻接点,更新k的最迟发生时间 
       j = p->adjvex;   //j为邻接顶点的序号 
       if(vl[k]>vl[j]-p->info) //更新顶点k的最早发生时间vl[k] 
        vl[k] = vl[j]-p->info;
       p = p->nextarc;   //p指向k的下一个邻接顶点 
      }
     }
     /*-----------------判断每一活动是否为关键活动-----------------*/
     printf("关键路径如下:\n\n");
     for(i=0;i<n;i++){
      p = G.vertices[i].firstarc; //p指向k的第一个邻接顶点
      while(p!=NULL){
       j = p->adjvex;   //j为i的邻接顶点的序号 
       e = ve[i];    //计算活动<vi,vj>的最早开始时间 
       l = vl[j]-p->info;  //计算活动<vi,vj>的最迟开始时间 
       if(e==l)     //若为关键活动则输出<vi,vj> 
        printf("<%c,%c>",G.vertices[i].data,G.vertices[j].data);
       p = p->nextarc;   //p指向i的下一个邻接顶点 
      } 
     }
     printf("  ->end\n");
     return OK;
    }
    //菜单函数
    void Menu(){
     printf("\n---------菜单-------\n");
     printf("\n1、创建图结构\n");
     printf("\n2、拓扑排序\n");
     printf("\n3、计算关键路径\n");
     printf("\n0、退出\n");
     printf("\n--------------------\n");
     printf("\n[请输入你的选择:]\n>>>");
    } 
    //主函数 
    int main(){
     int i,user;
     ALGraph G;
     while(true){
      Menu();
      scanf("%d",&user);
      switch(user){
       case 1:{
       if(CreateDAG(G))
        printf("\n创建成功……\n");
       break;
       }
       case 2:{
      if(TopologicalSort(G,topo)){
       printf("拓扑排序结果如下:\n\n");
       for(i=0;i<G.vexnum;i++)
        printf("%c->",G.vertices[topo[i]].data);
       printf("end\n");
     }
      break;
       }
       case 3:{
        CriticalPath(G);
        break;
       }
       case 0:exit(0);
      }
     }
     return 0;
    }

    五、实验结果

    1. 创建图结构

    1
    2

    2. 拓扑排序

    3

    3.关键路径

    4

    4.退出

    5

    六、总结与思考

    1. 用顶点表示活动,用弧表示顶点间的优先关系的有向图,称为顶点表示活动的网,简称(Activity On Vertex Network)AOV-网;

    2. 所谓拓扑排序,就是将AOV-网中的所有顶点排成一个线性序列,该序列满足:若在AOV-网中由顶点vi到顶点vj有一条路径,则在该线性序列中,顶点vi必在vj之前;

    3. 拓扑排序的过程,重复选择没有直接前驱的顶点;

    4. 与AOV-网相对,AOE-网是以边表示活动的网。AOE-网是一个带权的有向无环图。顶点表示事件,弧表示活动,权表示活动持续时间。

    5. AOE-网在工程计划和经营管理中通常需要解决以下两个问题:

    1)估算完成整项工程至少需要多长时间;
    2)判断哪些活动是影响工程进度的关键;

    6. 源点、汇点、关键活动、关键路径

    7. 一个活动的最迟开始时间l(i)与最早开始时间e(i)的差值l(i)-e(i)是该活动完成的时间余量,它是在不增加完成整个工程所需总时间的情况下,活动ai可以拖延的时间,当一个活动时间余量为零时,说明该活动必须如期完成,否则会拖延整个工程进度。所以称l(i)-e(i)=0,即l(i)=e(i)的活动为关键活动

    展开全文
  • 图的最短路径、拓扑排序关键路径相关算法描述,有c++code
  • 1.拓扑排序(AOV网) const int MAX_VERTEX_NUM = 20; //图的邻接表存储:对图的每个顶点建立一个单链表。需要两种类型的节点。一种是表头节点(数量=图的顶点数),以向量形式存储,以便随机访问任一顶点的链表; //...

    AOV网:顶点表示活动,弧表示活动间的优先关系的有向图。无有向环。

    AOE网:顶点表示事件,弧表示活动,权表示活动持续的时间的有向无环图。

    1.拓扑排序(AOV网)

    const int MAX_VERTEX_NUM = 20;
    //图的邻接表存储:对图的每个顶点建立一个单链表。需要两种类型的节点。一种是表头节点(数量=图的顶点数),以向量形式存储,以便随机访问任一顶点的链表;
    //一种是与表头节点表示的顶点邻接的顶点,链接到相应表头节点后面
    //与表头节点表示的顶点邻接的顶点的节点,包括一个顶点的数据域adjvex和一个指向下一个与表头节点邻接的顶点的指针
    typedef struct adjNode{
    	int adjvex;
    	struct adjNode *nextadj;
    }adjNode;
    //表头节点,包括顶点的数据域和指向第一个与其邻接的顶点的指针
    typedef struct VNode {
    	int data;
    	int indegree = 0;  //入度
    	adjNode *firstadj;
    }VNode,adjList[MAX_VERTEX_NUM]; //数结构体组存储所有表头结点
    //图
    typedef struct {
    	adjList vertices; //表头节点数组
    	int vexnum, arcnum;  //图的顶点数和边数
    }Graph;
    
    //建立有向图
    //时间复杂度:O(n+e)
    void BuildAdjlist(Graph& G,int n,int e) {
    	G.vexnum = n;
    	G.arcnum = e;
    	//先逐个画出图的全部顶点 从1到n编号
    	for (int i = 1; i <= n; ++i) {
    		G.vertices[i].data = i;
    		G.vertices[i].firstadj = NULL;
    	}
    	for (int i = 0; i < e; ++i) {
    		cout << "输入有向边:";
    		int u, v;
    		cin >> u >> v;
    		//表头节点u的邻接表中应加一个顶点v,即插入一个顶点p(插到最前面)
    		adjNode *p = new adjNode;
    		p->adjvex = v;
    		p->nextadj = G.vertices[u].firstadj;
    		G.vertices[u].firstadj = p;
    		G.vertices[v].indegree++;  //v顶点入度加1
    		//delete p;	// 不可delete p!!正在构造链表
    	}
    }
    //拓扑排序
    bool toposort(Graph& G,vector<int>& res) {
    	stack<int> s;
    	for (int i = 1; i <= G.vexnum; ++i) {
    		if (G.vertices[i].indegree == 0) {
    			s.push(i);
    		}
    	}
    	int count = 0;
    	while (!s.empty()) {
    		int j = s.top(); s.pop();
    		count += 1;
    		res.push_back(j);
    		adjNode *p = G.vertices[j].firstadj;
    		while (p != NULL) {
    			int k = p->adjvex;
    			G.vertices[k].indegree--;
    			if (G.vertices[k].indegree == 0) {
    				s.push(k);
    			}
    			p = p->nextadj;
    		}
    	}
    	if (count < G.vexnum)  return false;  //图中存在有向环
    	else return true;
    }
    
    //优化空间:用值为0的入度域存放链栈指针以指示下一个入度为0的顶点
    bool toposort(Graph& G,vector<int>& res) {
    	int top = 0; //指向入度为0的顶点
    	for (int i = 1; i <= G.vexnum; ++i) {
    		if (G.vertices[i].indegree == 0) {
    			G.vertices[i].indegree = top;
    			top = i;
    		}
    	}
    	int count = 0;
    	while (top!=0) {
    		int j = top; 
    		top = G.vertices[top].indegree; //相当于退栈
    		count += 1;
    		res.push_back(j);
    		adjNode *p = G.vertices[j].firstadj;
    		while (p != NULL) {
    			int k = p->adjvex;
    			G.vertices[k].indegree--;
    			if (G.vertices[k].indegree == 0) {
    				G.vertices[k].indegree = top;//新的入度为0的顶点入栈
    				top = k;
    			}
    			p = p->nextadj;
    		}
    	}
    	if (count < G.vexnum)  return false;  //图中存在有向环
    	else return true;
    }
    
    int main() {
    	Graph G;
    	int n, e;
    	cout<< "输入顶点数和边数:";
    	cin >> n >> e;
    	BuildAdjlist(G, n, e);
    	//打印图的邻接表
    	for (int i = 1; i <= n; ++i){
    		cout << G.vertices[i].data << "(" << G.vertices[i].indegree << ")";
    		if (G.vertices[i].firstadj == NULL) {
    			cout << endl;
    			continue;
    		}
    		adjNode* p = G.vertices[i].firstadj;
    		while (p != NULL) {
    			cout << "->" << p->adjvex;
    			p = p->nextadj;
    		}
    		cout << endl;
    	}
    	vector<int> res;
    	if (toposort(G, res) == true) {
    		cout << "拓扑序列为:";
    		for (auto& x : res) {
    			cout << x << ends;
    		}
    	}
    	else {
    		cout << "图中存在有向环!" << endl;
    	}
    }
    

    在这里插入图片描述

    分析算法,对有n个顶点和e条弧的有向图而言,建立邻接表的时间复杂度为0(n+e);搜索入度为0的时间复杂度为O( n);在拓扑排序过程中,若有向图无环,则每个顶点进一次栈, 出一次栈,入度减1的操作在WHILE语句中总共执行e次,所以,总的时间复杂度为O(n + e)。上述拓扑排序的算法亦是下节讨论的求关键路径的基础。
    当有向图中无环时,也可利用深度优先遍历进行拓扑排序,因为图中无环,则由图中某点出发进行深度优先搜索遍历时,最先退出DFS函数的顶点即出度为零的顶点,是拓扑有序序列中最后一个顶点。由此,按退出DFS函数的先后记录下来的顶点序列(如同求强连通分量时finished数组中的顶点序列)即为逆向的拓扑有序序列。
    leetcode课程表

    2.关键路径(AOE网)

    关键路径: 任务计划作业图上的需要时间最长的路径(可有多条)。它决定完成总任务的时间。

    工程的最小时间: 从开始顶点到结束顶点的最长路径的长(该路径上各活动的时间总和)。

    用e(i)表示活动 ai 的最早开始时间;在不推迟整个工程完成的前提下,一个活动可以最晚开始的时间定义为该活动的最迟开始时间,用l(i)表示。

    用e(i)- l(i)表示活动 ai 的时间余量,即 ai 在不影响总工期的前提下,可以延缓的时间。

    e(i)=l(i)的表示活动 ai 称关键活动,显然关键路径上的所有活动都是关键活动,要加快工期只有提速关键活动的速度。

    设活动 ai 用弧<j,k>表示,dut(<j,k>)表示权值。
    e(i):活动 ai 的最早开始时间;
    l(i):活动 ai 的最迟开始时间;
    Ve(j):事件 j 的最早发生时间;
    Vl(j):事件 j 的最迟发生时间;
    则:e(i)=Ve(j) →演变为计算Ve
    l(i)=Vl(k)-dut(<j , k>) →演变为计算求Vl

    const int MAX_VERTEX_NUM = 20;
    typedef struct adjNode{
    	int adjvex;
    	int dut;  //活动持续时间
    	struct adjNode *nextadj;
    }adjNode;
    //表头节点,包括顶点的数据域和指向第一个与其邻接的顶点的指针
    typedef struct VNode {
    	int data;
    	int indegree = 0;  //入度
    	adjNode *firstadj;
    }VNode,adjList[MAX_VERTEX_NUM]; //数结构体组存储所有表头结点
    //图
    typedef struct {
    	adjList vertices; //表头节点数组
    	int vexnum, arcnum;  //图的顶点数和边数
    }Graph;
    
    //建立有向图
    void BuildAdjlist(Graph& G,int n,int e) {
    	G.vexnum = n;
    	G.arcnum = e;
    	//先逐个画出图的全部顶点 从1到n编号
    	for (int i = 1; i <= n; ++i) {
    		G.vertices[i].data = i;
    		G.vertices[i].firstadj = NULL;
    	}
    	for (int i = 0; i < e; ++i) {
    		cout << "输入有向边及权:";  
    		int u, v, w;
    		cin >> u >> v >>w;
    		//表头节点u的邻接表中应加一个顶点v,即插入一个顶点p(插到最前面)
    		adjNode *p = new adjNode;
    		p->adjvex = v;
    		p->dut = w;
    		p->nextadj = G.vertices[u].firstadj;
    		G.vertices[u].firstadj = p;
    		G.vertices[v].indegree++;  //v顶点入度加1
    		//delete p;	// 不可delete p!!正在构造链表
    	}
    }
    
    //在拓扑排序过程中计算各顶点的最早发生时间ve
    //优化空间:用值为0的入度域indegree存放链栈指针以指示下一个入度为0的顶点.入度域初始放入度,运行过程可被拓扑栈和逆拓扑栈占用:拓扑出栈时,逆拓扑入栈
    void critical_path(Graph& G) {
    	vector<int> ve(G.vexnum+1), vl(G.vexnum+1); //事件(顶点)的最早发生时间
    	int ftop = 0; //拓扑栈初始化
    	int btop = 0; //逆拓扑栈初始化
    	//求ve  在拓扑排序过程中计算各顶点的最早发生时间ve
    	for (int i = 1; i <= G.vexnum; ++i) {
    		if (G.vertices[i].indegree == 0) {
    			G.vertices[i].indegree = ftop;
    			ftop = i;
    			ve[i] = 0;//初始化所有事件(顶点)的最早发生时间为0
    		}
    	}
    	int count = 0;
    	while (ftop!=0) {
    		int j = ftop; 
    		ftop = G.vertices[ftop].indegree; //相当于拓扑退栈
    		G.vertices[j].indegree = btop;   btop = j; //逆拓扑入栈
    		count += 1;
    
    		adjNode *p = G.vertices[j].firstadj; //p是j的邻接点
    		while (p != NULL) {
    			int k = p->adjvex; 
    			G.vertices[k].indegree--;
    			if (G.vertices[k].indegree == 0) {
    				G.vertices[k].indegree = ftop; //新的入度为0的顶点入栈
    				ftop = k;
    			}
    			//计算顶点k的ve
    			if (ve[k] < ve[j] + p->dut) {
    				ve[k] = ve[j] + p->dut;
    			}
    			p = p->nextadj;
    		}
    	}
    	if (count < G.vexnum) {
    		cout << "图中存在有向环!" << endl;
    		exit(0);
    	}
    	
    	//求vl
    	int endnode = btop; //逆拓扑序列第一个元素编号
    	vl[endnode] = ve[endnode];  //初始化顶点事件最迟发生时间
    	while (btop != 0) {
    		int j = btop;
    		btop = G.vertices[btop].indegree;
    		vl[j] = ve[endnode];  //vl初始化均为最大值ve(n)
    		adjNode* p = G.vertices[j].firstadj;
    		while (p != NULL) {
    			int k = p->adjvex;
    			if (vl[j] > vl[k] - p->dut) {
    				vl[j] = vl[k] - p->dut;
    			}
    			p = p->nextadj;
    		}
    	}
    	//求e(i),l(i)和关键活动
    	for (int i = 1; i <= G.vexnum; ++i) {
    		adjNode* p = G.vertices[i].firstadj;
    		char flag;
    		while (p != NULL) {
    			int ee = ve[i], el = vl[p->adjvex] - p->dut;
    			if (ee == el) flag = '*';
    			else flag = ' ';
    			cout << "<" << i << "," << p->adjvex << ">" << "," << p->dut << "," << ee <<"="<< el << " " << flag << endl;
    			p = p->nextadj;
    		}
    	}
    }
    
    int main() {
    	Graph G;
    	int n, e;
    	cout<< "输入顶点数和边数:";
    	cin >> n >> e;
    	BuildAdjlist(G, n, e);
    	//打印图的邻接表
    	for (int i = 1; i <= n; ++i){
    		cout << G.vertices[i].data << "(" << G.vertices[i].indegree << ")";
    		if (G.vertices[i].firstadj == NULL) {
    			cout << endl;
    			continue;
    		}
    		adjNode* p = G.vertices[i].firstadj;
    		while (p != NULL) {
    			cout << "->" << p->adjvex;
    			p = p->nextadj;
    		}
    		cout << endl;
    	}
    
    	critical_path(G);
    }
    
    展开全文
  • 完成整个工程所需的最短时间取决于从起点到终点中,具有最长路径长度的路径,这条路径即为关键路径。 求解过程 先求出每个事件(顶点)的最早开始时间(etv)和最晚开始时间(ltv),再根据这个顺序求得每个活动(边...
  • 一:拓扑排序 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列...
  • A - 数据结构实验之图论十:判断给定图是否存在合法拓扑序列 Description 给定一个有向图,判断该有向图是否存在一个合法的拓扑序列。 Input 输入包含多组,每组格式如下。 第一行包含两个整数n,m,分别代表该...
  • 通过邻接表实现图的关键路径,包含是事件最早发生时间ve,事件最迟发生时间vl,活动最早开始时间ee,活动最晚开始时间el
  • 拓扑排序-求关键路径 首先,我们来了解一下,什么是拓扑排序。百度百科这样说:对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若...
  • 拓扑排序&关键路径 数据结构期末抱佛脚,发现没学过关键路径,补上~
  • 拓扑排序关键路径

    2019-11-28 23:40:08
    目录 拓扑排序 ①在邻接矩阵上实现 ②在邻接表上实现 关键路径 拓扑排序 ①在邻接矩阵上实现 、 ②在邻接表上实现 关键路径 ...
  • 本文将介绍活动网络的基础知识,并用C++实现拓扑排序(Topological Sort)和关键路径(Critical Path)。
  • 关键路径 + 拓扑排序

    万次阅读 多人点赞 2016-12-19 21:54:59
    关键路径的算法是建立在拓扑排序的基础之上的,这个算法中用到了拓扑排序,所以在这里先以拓扑排序开篇。 1. 什么是拓扑排序? 举个例子先:一个软件专业的学生学习一系列的课程,其中一些课程必须再学完它的基础
  • 目录 1、定义 1.1、应用 1.2、术语 2、数据结构 2.1、代码 3、有向图的可达性 3.1、代码 3.2、垃圾回收机制---有向图的应用 4、有向图的路径 4.1、深度优先搜索 4.1、有向图最短路径---广度优先搜索 5、拓扑排序 5.1...
  • 1: 18 输入样例 2: 4 5 0 1 1 0 2 2 2 1 3 1 3 4 3 2 5 输出样例 2: Impossible 本题主要考察对图的知识中的“拓扑排序关键路径” 。这是图的知识中较难的一部分。 本题完整代码: #include #include #...
  • 拓扑排序关键应用

    2020-12-12 20:46:08
    文章目录问题 B: 图综合练习--拓扑排序题目描述--程序要求--输入输出样例输入样例输出代码问题 D: 关键路径-STL版题目描述输入输出样例输入代码 问题 B: 图综合练习–拓扑排序 题目描述 已知有向图,顶点从0开始编号...
  • 通信网络的架设问题 【问题描述】 若要在n(≥10)个城市之间建设通信网络,只...(3)将n个城市设计为一个DAG图,求出一组拓扑排序序列和关键路径。 #include<stdio.h> #include<malloc.h> #define
  • 理解关键路径需要掌握拓扑排序和邻接表的相关知识,由于此部分笔者在之前的文章中已经介绍过,此处不再过多赘述,对此部分知识还不熟练的读者,欢迎移步此文章,共同学习!: 数据结构C++——拓扑排序 数据结构C++...
  • 拓扑排序关键路径

    2015-03-26 17:30:00
    拓扑排序  1. AOV网  在工程领域,一个大的工程项目通常被划分为许多较小的子工程(称为活动)。显然,当这些子工程都完成时,整个工程都完成了。在有向图中,若以顶点表示活动,用有向边表示活动之间的优先...
  • 关键路径 AOE 拓扑排序 最短工期 java

    千次阅读 2019-06-22 20:26:07
    拓扑排序关键路径实现的基础 有两种实现方式: 1:dfs https://blog.csdn.net/aiwo1376301646/article/details/93350103 2:queue https://blog.csdn.net/aiwo1376301646/article/details/93353861 关键路径...
  • 拓扑排序&关键路径

    2014-07-24 08:47:25
    /* 功能Function Description: HDOJ-2094 开发环境Environment: DEV C++ 4.9.9.1 技术特点Technique: 版本Version: 作者Author: 可笑痴狂 日期Date:

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,753
精华内容 1,101
关键字:

c++拓扑排序与关键路径

c++ 订阅