精华内容
下载资源
问答
  • DFS实现逆拓扑排序

    2020-08-06 18:43:53
    //DFS实现逆拓扑排序 bool visited[MaxVertexNum]; void DFSTraverse(Graph G){ for(v=0;v<G.vexnum;v++) visited[v]=FALSE; for(v=0;v<G.vexnum;v++) if(!visited[v]) DFS(G,v); } void DFS(Graph G,int...

    多思考递归的过程! 

    //DFS实现逆拓扑排序
    bool visited[MaxVertexNum];
    void DFSTraverse(Graph G){
        for(v=0;v<G.vexnum;v++)
            visited[v]=FALSE;
        for(v=0;v<G.vexnum;v++)
            if(!visited[v])
                DFS(G,v);
    }
    void DFS(Graph G,int v){
        visit(v);
        visited[v]=TRUE;
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
            if(!visited[w]){
                DFS(G,w);
            }
        cout<<v<<endl;
    }
    

     

    展开全文
  • DFS实现逆拓扑排序 算法思路: 1.只要某结点还有没有访问的邻接节点,就会继续向下递归调用DFS,不断填充递归栈。 2.没有未访问的邻接结点时,退栈,只要退栈时将节点输出即可 编程注意事项: 用DFS实现拓扑...

    DFS实现逆拓扑排序

    DFS实现拓扑排序,以及拓扑排序的环路检测可见笔者的另一篇文章https://mp.csdn.net/editor/html/107450388

    【算法思路】:

    1.只要某结点还有没有访问的邻接节点,就会继续向下递归调用DFS,不断填充递归栈。

    2.没有未访问的邻接结点时,退栈,只要退栈时将节点输出即可

    【题外话】:

    2020年408在数据结构第六题就考察了这个算法,问“在DFS中退出递归栈之前输出,会得到是什么序列?”答案是逆拓扑排序。

    【编程注意事项】:

    用DFS实现逆拓扑排序,是基于DAG图实现的,没有考虑有环的情况。按照这样的方法,在有环的情况下也会输出一个排序,所以更严谨的算法应该增加环路判断,用dfs实现拓扑排序以及如何对有向图进行环路判断可见读者的另一篇文章。(https://blog.csdn.net/qq_39328436/article/details/107450388

    void DFS_again_again(ALGraph G, int v) {
    	visited[v] = true;
    	for (ArcNode* p = G.vertices[v].first; p; p = p->next)
    	{
    		if (!visited[p->adjvex])
    			DFS_again_again(G, p->adjvex);
    	}
    	cout << G.vertices[v].data << " ";//退栈时输出
    }
    
    
    void reverse_topo_based_on_dfs(ALGraph G) {
    	for (int k = 0; k < G.vecnum; k++)  visited[k] = false;//初始化visit数组
    	cout << endl;
    	cout << "逆拓扑排序:";
    	for (int v = 0; v < G.vecnum; v++)
    		if (!visited[v])
    			DFS_again_again(G, v);
    }

    展开全文
  • 具体算法描述如下:1....2.拓扑排序,并求得ve[]。从源点V0出发,令ve[0]=0,按拓扑有序求其余各顶点的最早发生时间ve[i]。如果得到的拓扑有序序列中顶点个数小于网中顶点数n,则说明网中存在环,不能求关键路径...

    https://blog.csdn.net/haskei/article/details/53749380

    具体算法描述如下:
    1. 输入e条弧<j,k>,建立AOE-网的存储结构。
    2. 拓扑排序,并求得ve[]。从源点V0出发,令ve[0]=0,按拓扑有序求其余各顶点的最早发生时间ve[i]。如果得到的拓扑有序序列中顶点个数小于网中顶点数n,则说明网中存在环,不能求关键路径,算法终止;否则执行步骤3。
    3. 拓扑逆序,求得vl[]。从汇点Vn出发,令vl[n-1] = ve[n-1],按逆拓扑有序求其余各顶点的最迟发生时间vl[i]。
    4. 求得关键路径。根据各顶点的ve和vl值,求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足条件e(s) = l(s),则为关键活动。

    为了能按逆序拓扑有序序列的顺序计算各个顶点的vl值,需记下在拓扑排序的过程中求得的拓扑有序序列,这就需要在拓扑排序算法中,增设一个栈,以记录拓扑有序序列,则在计算求得各顶点的ve值之后,从栈顶到栈底便为逆拓扑有序序列。

      1 #include<cstdio>
      2 #include<iostream>
      3 #include<algorithm>
      4 #include<cstring>
      5 #include<string>
      6 #include<cstdlib>
      7 #include<stack> 
      8 
      9 using namespace std;
     10 
     11 typedef long long ll;
     12 const int maxm = 20;
     13 const int maxn = 100;
     14 const int inf = 0x3f3f3f3f;
     15 struct node {
     16     int x, y, w;
     17     int next;
     18 };
     19 node edge[maxm];
     20 int n, m;
     21 int head[maxn];
     22 //e代表活动开始的最早时间, l活动最迟开始的时间, ve[i]事件最早发生的时间, vl[i]事件最迟发生的时间 ,indegree[i]顶点的入度 
     23 //这个地方没必要分别为e,l开数组了,因为最后只是进行赋值,然后比较两个数是否相等而已,没必要开数组了就,不明白可以看下面的代码 
     24 int e, l, ve[maxn], vl[maxn], indegree[maxn];
     25 stack<int> s, t; //s代表逆序的拓扑排序 ,t代表入度为零的栈,里面存放入度为零的点 
     26 
     27 int TopologicalSort() {
     28     int i, cnt = 0;
     29     for(i=1; i<=n; ++i) //入度为零的点入栈 
     30         if(!indegree[i]) {
     31             t.push(i);
     32             ++cnt;
     33             //printf("%d ", i);
     34         }
     35     while(!t.empty()) {
     36         int a = t.top();
     37         s.push(a);
     38         //printf("%d ", a);
     39         t.pop();
     40         //去掉与入度为零的点的相连的边,对应的终点的入度减一 
     41         int k = head[a];
     42         while(k != -1) {
     43             if(!--indegree[edge[k].y]) {//终点的度减一后,如果度为零,入栈 
     44                 t.push(edge[k].y);
     45                 ++cnt;
     46                 //printf("%d ", edge[k].y);
     47             }
     48             if(ve[edge[k].y] < ve[a] + edge[k].w) //正拓扑排序求事件发生的最早时间ve[i],到edge[k].y的最长路径 
     49                 ve[edge[k].y] = ve[a] + edge[k].w;
     50             k = edge[k].next;    
     51         }
     52     }
     53     if(cnt < n) 
     54         return 0;
     55     return 1;
     56 }
     57 
     58 
     59 int main()
     60 {
     61     int i;
     62     memset(head, -1, sizeof(head));
     63     scanf("%d%d", &n, &m);
     64     
     65     //建立邻接表 
     66     for(i=1; i<=m; ++i) {
     67         scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].w);
     68         ++indegree[edge[i].y];  //终点的入度加一 
     69         edge[i].next = head[edge[i].x];
     70         head[edge[i].x] = i;
     71     }
     72     
     73     if(TopologicalSort() == 0) { //在 TopologicalSort()函数里面已经解决了ve的问题 
     74         printf("不存在关键路径,存在环\n");
     75         return 0;
     76     }
     77     
     78     memset(vl, inf, sizeof(vl));
     79     vl[n] = ve[n]; //最后一个事件的最迟发生事件就等于最早发生时间,因为是最后一件事,也就是说这个工程干完了,以后就没有事情做了 
     80     while(!s.empty()) { //逆拓扑排序求vl[i] 
     81         int a = s.top();
     82         s.pop();
     83         int k = head[a];
     84         while(k != -1) {
     85             if(vl[a] > vl[edge[k].y] - edge[k].w) {
     86                 vl[a] = vl[edge[k].y] - edge[k].w;
     87             }
     88             k = edge[k].next;
     89         }
     90     }
     91     printf("\n关键活动(该活动不能推迟开工)有:\n");
     92     for(i=1; i<=n; ++i)  { 
     93         int k = head[i];
     94         while(k != -1) {
     95             e = ve[i]; //该条边的起点代表事情,该条边表示的活动的最早发生时间就等于起点代表的事情的最早发生时间 
     96             //活动的最迟发生时间
     97             l = vl[edge[k].y] - edge[k].w;
     98             if(l == e)
     99                 printf("%d %d %d\n", i, edge[k].y, edge[k].w);
    100             k = edge[k].next;
    101         }
    102     }
    103     return 0;
    104 }
    105 /*
    106 9 11
    107 1 2 6
    108 1 3 4
    109 1 4 5
    110 2 5 1
    111 3 5 1
    112 4 6 2
    113 5 7 9
    114 5 8 7
    115 6 8 4
    116 7 9 2
    117 8 9 4
    118 */

     

    转载于:https://www.cnblogs.com/MekakuCityActor/p/9005461.html

    展开全文
  • 题意:每一个人的基础工资是888。 因为一部分人要显示自己水平比較高,要求发的工资要比其它人中的一个人多。问你能不能满足他们的要求,假设能的话终于一共要发... 二:要逆拓扑排序(就是将++in[b]换成++in[...

    题意:每一个人的基础工资是888。 因为一部分人要显示自己水平比較高,要求发的工资要比其它人中的一个人多。问你能不能满足他们的要求,假设能的话终于一共要发多少钱,假设不能就输出-1.

    策略:拓扑排序。

    这道题有些难点:一:数据大,建二维数组肯定不行,要换其它的数据结构(vector, 或者是链式前向星(本题代码用的是链式前向星)); 二:要逆拓扑排序(就是将++in[b]换成++in[a])。 三要分层次(依据上一个的钱数+1就可以)。

    不懂什么是链式前向星 移步:http://blog.csdn.net/acdreamers/article/details/16902023

    代码:

    #include<stdio.h>
    #include<string.h>
    #include<queue>
    #define MAXN 10005
    int head[MAXN*2];
    struct EdgeNode{
    	int to;
    	int next;
    };
    EdgeNode edges[MAXN*2];
    int in[MAXN], queue[MAXN], money[MAXN];
    int n, ans;
    int toposort()
    {
    	ans = 0;
    	memset(money, 0, sizeof(money));
    	int i, j;
    	int iq = 0;
    	for(i = 1; i <= n; i ++){
    		if(!in[i]){
    			queue[iq++] = i;
    		}
    	}
    	for( i = 0; i < iq; i ++){
    		int temp = queue[i];
    		ans += money[temp];
    		for(j = head[temp]; j != -1; j = edges[j].next){
    			if(!--in[edges[j].to]){
    				queue[iq++] = edges[j].to;
    				money[edges[j].to] = money[temp]+1;//这里是分层次。
    			}
    		}
    	}
    	return iq == n;
    }
    int main()
    {
    	int m, i, a, b;
    	while(scanf("%d%d", &n, &m) == 2){
    		memset(head, -1, sizeof(head));
    		memset(in, 0, sizeof(in));
    		for(i = 0; i < m; i ++){
    			scanf("%d%d", &a, &b);
    				in[a]++;
    				edges[i].to = a;
    				edges[i].next = head[b];
    				head[b] = i;
    		}
    		int sum = 888*n;
    		int flag = toposort();
    		printf("%d\n", flag?sum+ans:-1);
    	}
    	return 0;
    }
     

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2647

    展开全文
  • 我们用逆拓扑排序,先把入度为零的数从大到小存入数组。然后就是一般的拓扑排序。。最后逆序输出 #include #include #include #include #include #include #include using namespace std; int m,n; vector
  • 思路:逆拓扑排序 之前都是谁大谁是头节点,但是这题如果谁大谁为头的话,那么头结点的工资将不停的改变,有点麻烦,但是根节点工资永远不会变,所以可以反过来,谁小谁当根节点,也就是出度变入度,入度变出度,...
  • 逃生(逆拓扑排序

    2019-09-24 11:51:09
    1,2(孤立) ,那么正向拓扑,应该是2 3 1,因为1要比2先出来,所以这种不满足。 逆向: 1->3,2 。此时若优先级从大到小,则2 1 3,逆向输入就是3 1 2 。 #include<iostream> #include<cstdio...
  • 还有就是这个题有那个等级的问题,一级比一级的福利高,所以不能直接拓扑排序,而是反过来,计算出度,找出度为0的顶点,然后更新出度数组,等级更新的时候要判断是否比原来的等级大,具体看代码 1 /*********...
  • DFS进行逆拓扑排序

    千次阅读 2018-01-03 17:51:43
    使用dfs+栈,来逆序求解拓扑序列,然后再把栈中数据逆序放到另外一个栈,实现顺序输出。   过程: 把当前点加入栈 遍历并判断当前点的邻接点 是否遍历过 是否存在栈中 如果都不是,递归及需求。 如果都是,...
  • ★ 一开始看到这题就想到的是...★看了看别人的题解,说是拓扑排序, 然后我就去了解了一波 相关知识: 详细可见 https://blog.csdn.net/qq_35644234/article/details/60578189 拓扑排序的方法 Kahn算法...
  • void DFSTraverse(Graph G) { //对图G进行深度优先遍历 for (v = 0; v < G.vexnum; ++v) visited[v] = FALSE; //初始化已访问标记数据 for (v = 0; v < G.vexnum; ++v) //本代码中是从v=0开始遍历 ...
  • Reward HDU - 2647 题意:每个人的起始金额是888,有些人觉得自己做的比另一个人好所以应该多得一些钱,问最少需要花多少钱,如果不能满足所有员工的要求,输出 -1 样例1: 2 1 1 2 输出1777 ...
  • 目录 背景 实现思路 代码 背景 在学习拓扑排序的时候,老师提出了一个问题:在逆拓扑排序算法中如何识别出回路? 总所周知,拓扑排序必须在DAG(有向无环图)中实现,也就是说如果给定的图带有回路,就无法进行拓扑...
  • 思路:刚开始以为直接拓扑排序就可以,其实不然。题目的意思是:如果有满足拓扑排序 的多种情况的前提下,让1先尽量靠前,满足1尽量靠前之后,让2尽量靠前,而不是直接 的字典序。 比如: 4 2 3 2 4 1 结果应为4 1 3...
  • HDU 2467 Reward(逆拓扑排序

    千次阅读 2014-08-01 16:08:36
    拓扑排序的变形,逆序建图就好了 Reward Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3951 Accepted Submission(s): 1203 Problem Description
  • 逆拓扑排序 #include<cstdio> #include<string.h> #include <queue> #include<algorithm> using namespace std; vector<int>G[30005]; int indegree[30005]; int n,m,a[30005]; void toposort() { ...
  • 如果队列能弹出的不够n那么就是-1,还有就是这里的拓扑应该是按照队列进队的,如果是用的优先队列,后进的反而先出,那么金额数会被影响 一个点连着两个888,如果那个点先出去把以前的888改掉了。。那就gg了,所以用...
  • n个球的重量为1-n,首先考虑的把最重的放在后面,轻的在前面按照编号的字典序输出,也就是逆拓扑排序。   代码: #include #include #include #include #include #include #include #include #...
  • // HDU 4857 拓扑排序 // // Created by 郑喆君 on 8/9/14. // Copyright (c) 2014 itcast. All rights reserved. // #include #include #include #include #include #include #include #include #incl
  • 【HDU】4857 逃生 逆拓扑排序

    千次阅读 2014-07-20 22:06:51
    然后其实本题应该倒过来思考,建立反图并拓扑排序,优先队列用大根堆,这样每次弹出的都是最大的那个点,然后就会使得编号大的能排前面就排前面(因为输出用的倒序,所以越排前面等于输出越靠后)。拓扑完以后逆序...
  • http://acm.hdu.edu.cn/showproblem.php?pid=4857

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 191
精华内容 76
关键字:

逆拓扑排序