精华内容
下载资源
问答
  • 最近想写一个识别线程死锁的算法,在网上找了半天没有合适的代码,自己写了个查找有向图中的代码(可以将死锁的资源依赖建模成含有向图)。本代码经过充分测试,内部有详细说明,可以放心下载。
  • 有向图中所有环--深度遍历暴力求解

    万次阅读 多人点赞 2020-04-02 14:00:33
    每个点都进行深度遍历,找到以这个点为起点的。。。数据再大一点应该就不行了。。。 代码写得烂,仅供参考。。 #include "bits/stdc++.h" using namespace std; void dfs(const vector<vector<int&...

    华为软件精英挑战赛2020题目

    为了方便理解题目,暴力求解了一下。。。

    每个点都进行深度遍历,找到以这个点为起点的环。。。数据再大一点应该就不行了。。。

    代码写得烂,仅供参考。。

     

    更新,用邻接表来实现速度快了100倍。。。

     

    更新,根据大佬的Java代码写了两个小的数据集。。。

    https://github.com/izhangrui/HWcode2020-TestData/tree/master/C%2B%2B

     

    更新,数据连通性太强了,拓扑排序只能去除一两个点,看情况使用。。。。

    同一份代码,为什么用vs跑要比g++快?

    100w的数据排序用太长时间了。。。是不是可以考虑排序用多线程。。。

     

    更新,g++慢是因为编译的时候没加优化选项-O3。。。

     

    试了一下鲲鹏服务器,感觉和笔记本差不多。。。

    看这个100w和300w的结果,这用时和环数呈正比?

    另外排序慢很有可能是因为生成的数据高度有序?快排貌似对有序的数据很慢。。。

     

    更新,貌似可以省去对结果排序。。。

     

    提交了答案,垫底。。。输出还是用的ofstream,没弄权限什么的,就是要注意输入输出路径。。

     

    同一份代码在鲲鹏服务器上测试的100w数据,多线程。。。

     

     

    分享一个大佬在线2s的代码,太强了。。

    https://zhuanlan.zhihu.com/p/125764650

     

    优化了一下,线下测试100w数据2s。。线上31.9s。。好想知道线上是什么数据。。。

     

    更新:C++中在循环中创建向量感觉很费时间,代码功底太差了啊!优化不动了。。。

    分享一个剪枝思路,剪掉3邻域外的点。。

    一个python实现:

    https://github.com/izhangrui/CodeCraft2020

     

     

    更新:

    dfs+3邻域剪枝+向量改数组线上能到2.1s,再加上6+1的来优化可以到1.7s。

    还有就是感觉官方56环那个数据线下测评也很重要,优化代码后最好测一测56环那个数据再提交。。保证大图优化的同时,小图不要负优化(比如一开始开个300w的向量,大图不是很影响,小图影响就很大。针对小图优化内存、输入输出,针对大图优化算法?)

    如果线下大图小图都提升,或者其中一个提升一个不变应该线上就会有提升吧,明天用多线程来再验证一下。。。

    突然想起可以用以前提交过的代码来验证这个猜想。。。不知道大家有没有进行过相关测试。。

     

    更新:6+1的python实现,线上29分。

    https://github.com/izhangrui/CodeCraft2020/blob/master/CodeCraft2020_v3.py

     

     

    更新:为了测试算法部分到底用了多少时间,在程序里增加了了一次找环的操作,发现线上成绩只增加了0.14,由1.78变成了1.92....也就是说找环部分只花了0.14s?所以算法的优化意义以及不大了?不知道这么分析对不对。。。

     

    更新:把dfs之外的向量也都改数组了,提升了0.6s,这时间都够好几次dfs找环了。。。虽然线上提升这么多,但线下几乎没变。。。之前也试过3+4的,线下大图非常友好,提升好几倍。。。但线上就是不行。。猜测大概就是线上dfs花的时间非常少,提升好几倍也没啥提升,反而要是为了优化使用了stl的话估计还会更慢。。。

    现在就只剩下一个map和两个向量,还不知道怎么优化。。。

    还有就是映射id的时候改map为unordered_map快了0.2s。。

     

    更新:测试了一下fscanf读数据,在程序里把数据读了两遍,线上慢了大概0.06s,也就是说对于目前数据,即使使用mmap读最多也就提升0.06s?另外,读和dfs都不怎么费时,下次再测一下写。

     

     

    更新:优化了一下,fscanf+fwrite+单线程

    不知道用mmap还会有多大提升。。。要开学了,暂时不弄了,大家加油!

     

    更新:最终成绩0.2094...除了多线程和mmap读,算法没有什么特别的操作...实测最终dfs部分多线程不超过0.03s,单线程不超过0.09s...

    看了ddd大佬的数据分析就明白了为什么之前,线下100w数据2s线上31s...对于这数据感觉很多操作都是多余的...真是服了这数据了...

    https://github.com/justarandomstring/2020-Huawei-Code-Craft/tree/master/First%20Round

    最后ddd真是太强了!很想赛后看看大佬们都是怎么写的代码

     

    下面C++代码是之前比赛开始的时候,为了理解题意写随便写的一份代码,现在感觉已经没什么参考价值了。。。

    #include "bits/stdc++.h"
    
    using namespace std;
    
    void dfs(const vector<vector<int>> &g, vector<vector<int>> &res, vector<int> &visit, vector<int> &path, int k, int p_o)
    {
        for (int i = 0; i < g.size(); i++)
        {
            if (g[k][i] == 0)
                continue;
            if (i == p_o)
            {
                res.push_back(path); //保存找到的环
                continue;
            }
            if (visit[i] == 1)
                continue;
            visit[i] = 1;
            path.push_back(i);
            dfs(g, res, visit, path, i, p_o);
            path.pop_back();
            visit[i] = 0;
        }
    }
    
    bool cmp(vector<int> a, vector<int> b)
    {
        //输出排序比较
        if (a.size() == b.size())
        {
            for (int i = 0; i < a.size(); i++)
            {
                if (a[i] == b[i])
                    continue;
                return a[i] < b[i];
            }
        }
        else
            return a.size() < b.size();
        return false;
    }
    bool isSame(vector<int> &a, vector<int> &b)
    {
        //比较两个矩阵是否一样
        if (a.size() != b.size())
            return false;
        for (int i = 0; i < a.size(); i++)
        {
            if (a[i] != b[i])
                return false;
        }
        return true;
    }
    void rot_vector(vector<int> &nums)
    {
        //统一环的起点,最小id为起点
        int min_num = nums[0];
        int min_idx = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            if (min_num > nums[i])
            {
                min_num = nums[i];
                min_idx = i;
            }
        }
        vector<int> temp(nums);
        for (int i = 0; i < nums.size(); i++)
        {
            nums[i] = temp[(i + min_idx) % nums.size()];
        }
    }
    
    int main()
    {
        clock_t start_time, end_time;
        start_time = clock();
        //--------------------------数据读入-----------------------------
        ifstream infile("test_data.txt");
        vector<int> ids1;
        vector<int> ids2;
        vector<int> vals;
        int id1, id2, val;
        char c;
        while (infile >> id1 >> c >> id2 >> c >> val)
        {
            ids1.push_back(id1);
            ids2.push_back(id2);
            vals.push_back(val);
        }
        //-----------------------创建有向图-----------------------------------
        int max_id = 0;
        for (int i = 0; i < ids1.size(); i++)
        {
            if (i == 0 || max_id < ids1[i])
            {
                max_id = ids1[i];
            }
            if (max_id < ids2[i])
            {
                max_id = ids2[i];
            }
        }
        cout << max_id << endl;
        max_id += 1;
        vector<int> temp(max_id, 0);
        vector<vector<int>> g(max_id, temp);
        vector<int> visit(max_id, -1);
        for (int i = 0; i < ids1.size(); i++)
        {
            visit[ids1[i]] = 0;
            visit[ids2[i]] = 0;
        }
        for (int i = 0; i < ids1.size(); i++)
        {
            g[ids1[i]][ids2[i]] = vals[i];
        }
        //-------------------深度遍历找环------------------------------------
        vector<vector<int>> res;
        vector<int> path;
        for (int i = 0; i < visit.size(); i++)
        {
            if (visit[i] == -1)
                continue;
            visit[i] = 1;
            path.push_back(i);
            dfs(g, res, visit, path, i, i);
            visit[i] = 0;
            path.pop_back();
        }
        //-----------------将环排序去重----------------------------------------
        cout << res.size() << endl;
        vector<vector<int>> res1;
        vector<vector<int>> res2;
        for (int i = 0; i < res.size(); i++)
        {
            if (res[i].size() < 3 || res[i].size() > 7)
                continue;
            rot_vector(res[i]);
            res1.push_back(res[i]);
        }
        sort(res1.begin(), res1.end(), cmp);
        res2.push_back(res1[0]);
        for (int i = 1; i < res1.size(); i++)
        {
            if (isSame(res1[i], res1[i - 1]))
                continue;
            res2.push_back(res1[i]);
        }
        //------------------输出结果--------------------------------------------
        ofstream outfile("result.txt");
        outfile << res2.size() << endl;
        for (int i = 0; i < res2.size(); i++)
        {
            for (int j = 0; j < res2[i].size(); j++)
                outfile << res2[i][j] << ",";
            outfile << endl;
        }
        end_time = clock();
        cout << " time : " << double(end_time - start_time) / CLOCKS_PER_SEC << "s" << endl;
    }

     

    展开全文
  • NULL 博文链接:https://128kj.iteye.com/blog/1717469
  • 借鉴:... 由图中可以看出,"4"号点已经没有子节点,所以DFS以该点为起点的话,没有办法遍历整个,所以没有办法找出。 这也是为什么程序的运行结果与起始点有关。

    借鉴:https://blog.csdn.net/iteye_8466/article/details/82440433

    child_graph = {"0": "1#2", "1": "3", "2": "5", "3": "4",
                    "4": "2", "5": "4#6", "6": "0#2"}
    
    visited = []
    trace = []
    has_circle = False
    
    
    def dfs(node_index):
        global has_circle
        if (node_index in visited):
            if (node_index in trace):
                has_circle = True
                trace_index = trace.index(node_index)
                for i in range(trace_index, len(trace)):
                    print(trace[i] + ' ', end='')
                print('\n', end='')
                return
            return
    
        visited.append(node_index)
        trace.append(node_index)
    
        if(node_index != ''):
            children = child_graph[node_index].split('#')
            for child in children:
                dfs(child)
        trace.pop()
    
    
    dfs("1")
    if(has_circle == False):
        print("No Cycle.")

    输出结果:

    4 2 5 
    1 3 4 2 5 6 0 
    2 5 6 0 
    2 5 6 

    另外,该算法的结果与深度优先搜索的起始点有关,例如,在上例中,如果起始点为"0",则只能找出3个环。不同起始点可能造成结果不同。

    再看一个例子:

    将上述代码中的child_graph改一下:

    child_graph = {"0": "1#5", "1": "2", "2": "3#4", "3": "0",
                    "4": "", "5": "6", "6": "0"}

    然后起始点为"0":

    dfs("0")

    输出结果为:

    0 1 2 3 
    0 5 6 

    可见,结果正确。

    但如果起始点为"4":

    dfs("4")

    则结果为:

    No Cycle.

    由图中可以看出,"4"号点已经没有子节点,所以DFS以该点为起点的话,没有办法遍历整个图,所以没有办法找出环。

    这也是为什么程序的运行结果与起始点有关。

    展开全文
  • 查找有向图中所有

    千次阅读 2018-06-30 12:30:00
    因为这些点若还构成其它的,那么在递归到该点时会查找出来。 本方法输出的,结点不是按其在环中的先后位置排列的。 1 import java.util.*; 2 3 public class GetAllCyclesForDire...

    在对每个结点进行DFS的基础上进行了一些优化。

    优化原理:在findCycle(v,e) 中访问过的点,不再进行findCycle().  因为这些点若还构成有其它的环,那么在递归到该点时会查找出来。

    本方法中输出的环,结点不是按其在环中的先后位置排列的。

     1 import java.util.*;
     2 
     3 public class GetAllCyclesForDirectedGraph{
     4 static List<Integer> trace;
     5 static Set<Integer> searched=new HashSet<>();
     6 static Set<List<Integer>> allCircles = new HashSet<>();
     7 
     8 public static void main(String[] args) {
     9  int n=7; 
    10 int[][] e={ {0,1,1,0,0,0,0}, {0,0,0,1,0,0,0}, 
    11             {0,0,0,0,0,1,0}, {0,0,0,0,1,0,0}, 
    12             {0,0,1,0,0,0,0}, {0,0,0,0,1,0,1}, 
    13             {1,0,1,0,0,0,0}};
    14 for(int i=0;i<n;i++){
    15 if(searched.contains(i)) 
    16 continue;
    17 trace =new ArrayList<>();
    18 findCycle(i,e); 
    20 }
    21 
    22 for(List<Integer> list:allCircles)
    23 System.out.println("circle: "+list);
    24 }
    25 
    26 
    27 static void findCycle(int v, int[][]e){
    28 int j=trace.indexOf(v); 
    29 if(j!=-1) {

    31 List<Integer> circle=new ArrayList<>(); 32 while(j<trace.size()) {

    35 circle.add(trace.get(j)); 36 j++; 37 } 39 Collections.sort(circle); allCircles.add(circle); 42 return; 43 } 44 45 46 trace.add(v); 47 for(int i=0;i<e.length;i++) { 48 if(e[v][i]==1){
    searched.add(i);
    49 findCycle(i,e); 50 } 51 } 52 trace.remove(trace.size()-1); 53 } 54 55 }
     
      

     

     

     

    转载于:https://www.cnblogs.com/black-fish/p/9246701.html

    展开全文
  • 本文简要介绍Johnson的在有向图中寻找简单化的算法。

    注:本算法和计算图所有结点对最短路径的Johnson算法不同。


    目录

    综述

    代码解析

    实例解析

    引用


    综述

    Johnson算法由B. Johnson发表于1975年,用于在一个有向图中寻找所有简单环。时间复杂度上界为O((n+e)(c+1)),空间复杂度为O(n+e),其中n为顶点数,e为边数,c为存在环数。在算法执行时,每两个连续的环的输出之间的时间不会超过O(n+e)。

    *常用的此类算法的复杂度比较如下:

    1. Tiernan - O(V.const^V)
    2. Tarjan - O(VEC)
    3. Johnson - O(((V+E)C)
    4. Szwarcfiter and Lauer - O(V+EC)

    所谓的简单环,即除了第一个和最后一个顶点,其余所有顶点在路径中只出现一次。这里排除了包括像v->v这样的自循环的边和在两个顶点之间的多条边的情况。本算法沿用Tiernan算法的记号,每个简单环都是由根顶点为s的子图构建的,这个子图由s和“大于”s的顶点构成。因此每个输出都根据路径的最小点s来分类。

    当从s开始遍历路径,把一个顶点v加入这个路径时,会把这个顶点的状态设为“阻塞”(blocked),直到从v到s的所有路径都完成检索,v会一直保持这种状态,这样保证了一个顶点不会被重复添加。另外除非一个顶点是构造简单环路径的最小的点,这个点不会成为路径的根顶点。这样保证不会无意义的搜索。

    算法的输入是一个图结构,图的表示是邻接表形式。假设每个顶点用从1到n的一个数字表示,图表示为AG,则AG(v)是一个数组表示第v个顶点的邻接顶点。算法的过程是这样的:从一个根顶点s开始构建简单环,所经过的路径的顶点保存在一个栈中。算法通过调用CIRCUIT过程添加新顶点,添加时务必将其设置为blocked,并且在过程调用返回时删除这个顶点,但是此时不一定将其阻塞状态去除。

    代码解析

    下面是算法的伪代码:

    algo

    如上所述,整个算法包括CIRCUIT主过程, 位于empty stack;语句以上,它又包含一个子过程UNBLOCK用于对一个blocked顶点进行解锁。下面以C++为例谈一下我对这个算法实现的理解:

    每个点的ID表示为1到n的一个类型为size_t整数。Ak,B两个数组在开始时被初始化,数组的长度都为n,即顶点数目。这两个数组的元素都是list<size_t>,A数组第i个元素的链表记录从点i出发指向的顶点,即图的邻接表。B的作用是记录因为此点阻塞而被迫阻塞的顶点,一旦点i因为调用unblock过程解锁,那么在B[i]链表中记录的顶点也因此解锁。B的效果是将每个点尽可能的保持阻塞状态以防止重复搜索。blocked是一个长度为n的bool数组,表示在搜索时这个点是否是阻塞。s表示目前搜索到的根结点的编号。

    CIRCUIT过程从stack v;语句开始,其输入参数v表示这个CIRCUIT过程所搜索的环都是从v这个顶点开始的。调用开始先将标志量f设为false,f表示这次调用是否发现了一个环。把v放在栈stack中,然后将blocked数组的v设为true,即将此点阻塞。可以看到下方对于CIRCUIT的调用都是将s作为参数,所以stack的栈底一般都是s。下一步遍历Ak中第v个链表,即v出发的边指向的顶点。如果某个顶点与s相等,说明找到了一个环,这时执行输出环并把f设为true。否则如果这个顶点没有阻塞,说明还可以向下走,就递归调用此过程。

    如果能够在v的邻接顶点中找到一条环路,则f就是true的,这时可以把v解锁,即调用unblock过程。反之,则说明从包含从v出发的边的路径都是死路,是不可能的形成环的,所以不能解锁v,同时要把与v邻接的顶点置于B数组的第v个链表中,经过v的路径是死路,但经过v的邻接顶点w的不一定死路,应为w可能有另外的上级顶点,所以如果不搜索v了,即解锁v顶点是要把B[v]中记录的顶点也解锁,以供其他路径搜索使用。

    对v的调用结束时把v出栈。返回f,标志在这次调用中是否发现环。

    下面是如何执行主进程。主进程涉及到寻找强连通分量(scc),这部分可以参考tarjan算法。算法首先清空储存路径节点的栈,将搜寻起点s设为1,注意所有顶点编号从1开始。Ak初始化为在{s, s+1, s+2,...,n}这些顶点构成的子图里面所有强连通分量中,有最小顶点的分量的邻接表。Ak如果为空,说明图已经搜索完,算法结束。否则将s设为上述分量Ak里面最小的顶点,将blocked全置为false,B清空,以s为输入参数调用CIRCUIT。注意此时CIRCUIT只寻找以s开头的环路。调用完成将s加一,再在新的子图中寻找。

    实例解析

    下面是对上述过程的一个实例,来自YouTube一位Tushar Roy的视频主的教程(此君在YouTube上多有图论方面教程,可以学习,这个算法的视频我搬运到了B站,供诸君参考)。

    step1&2

    Step1是一个有向图G,Step2表示分解后的三个强连通分量,所谓强连通分量,就是在一个有向图中,任选两个顶点都可以互相到达。分解scc的tarjan算法在此不再赘述。

    step3

    发现1是最小的顶点,选取1所在的scc开始搜索,第一个调用顶点是1。step3-5是从1开始的3条遍历路径。上图所示,红色边表示搜索的路径,从1开始依次搜索1,2,3,到3的时候,栈里存储了这三个节点,并且blocked数组将这三个元素设为true。3有3个邻接顶点。首先搜索1,发现1是出发的顶点,表明找到了一个环,就将环输出,并把3这里调用的变量f设为true。

    step4

    回到顶点3后搜索下一个邻接顶点4,4没有阻塞说明还没有探索过,4只有一个邻接点5,走到5之后已经无路可走,因为5的唯一邻接顶点2处于blocked状态,所以以f为false返回这次调用,表明没有找到环。调用从2返回到5的时候看到返回值是false,这时把5放到B[2]的链表中。这种做法相当于告诉2节点:兄弟你解锁的时候把我也解锁了,你不解锁我也堵着算了,反正下次再找到我的时候,我的下家都是死路,找也是白找。所以,只有在调用UNBLOCK(2)的时候5才能解锁,这时blocked[5]还是保持blocked状态。返回的4的时候也是如此。需要把4保持阻塞,并把4放到B[5]的链表中。这时调用返回到了3节点。

    step5

    检索3的下一个邻居6,发现6的下家4还是阻塞的,于是这次调用也以失败返回。返回到3,3的邻居已经检索完,发现了一个环,所以f是true的,把3的阻塞解除,调用返回到2。因为3找到了一个环所以2的f也是true的,所以调用UNBLOCK(2),这个过程把blocked[2]设为false之后,检索B[2]发现里面有一个元素5,因此递归调用把5也解锁了。依次调用,B就被清空了。

    这就是一次1->2这个边开头的检索的完整过程。

    本人水平有限,解读如果有失误之处欢迎交流。

    引用

    [1] Donald B. Johnson, Finding all the elementary circuits of a directed graph, SIAM Journal on Computing, 1975.

    [2] BiliBili搬运视频:https://www.bilibili.com/video/BV13Q4y1K7bx

    [3] 一个Github的C++实现:https://github.com/hellogcc/circuit-finding-algorithm(其实现无论方式还是算法都有不少和原算法的出入,大家批判性鉴赏。

    展开全文
  • from copy import deepcopy as dc # 用集合去除重复路径 ans = set() def dfs(graph,trace,start): trace = dc(trace) # 深拷贝,对... # 如果下一个点在trace,则返回 if start in trace: index = trace....
  • 该算法是实现打印出有向图中所有环,图采用邻接表表示,然后用一个栈来遍历,用一个向量来查找是否有……有点不足的是有些情况会出现重复的……我把一个工程直接放在里面,顶点输入时按数字编号,如顶点0,1,...
  • 有向图中有向检测

    千次阅读 2018-01-02 10:55:08
    寻找有向图中是否存在有向是判定一个任务优先级问题的前提边的类型从某个点开始的深度搜索过程遇到了后向边,可作为找到有向的标志代码实现private boolean[] onStack = new boolean[V];public void dfs(int s...
  • 判断无向图/有向图中是否存在

    千次阅读 2019-02-03 11:54:50
    本文主要针对如何判断有向图/无向图是否存在的问题进行简单的论述。 一 无向图 1.利用DFS进行判断 利用DFS判断有向图是否存在,是最为常用的一种方法,虽然这种方法很常用,但可参考的代码的实现比较少,...
  • 有向图中打印所有的环路

    千次阅读 2018-06-10 23:46:24
    这样所有的应用形成一个有向图,那么如果这个有向图中出现了环路,就悲剧了,用户的请求如果进入这个环路,那么他永远也得不到响应。所以就有需要去判断这个应用组成的有向图中是否含有环路,如果有就要打印出所有的...
  • 查找有向图中

    万次阅读 2012-03-06 14:16:51
    有向图: 主要有深度优先和拓扑排序2中方法 1、拓扑排序,如果能够用拓扑排序完成对图中所有节点的排序的话,就说明这个图中没有,而如果不能完成,则说明有。 2、可以用Strongly Connected ...
  • 有向图: : 找出 途中 从 A 到 F 一共有多少走法, 包含的闭环 有哪些 构思: 遍历前 先准备一个 list 用来存放当前路径, 从A开始 先找到B ,B找到D, D 到F, 此时 F为所找目标节点, 此时算是找到一条路径, ...
  • 【三种解法】判断有向图是否有

    千次阅读 2020-07-17 12:03:38
    我们最常用的是topsort来判断是否有环,因为这个方法简单。 我去网上找了很多关于如何用dfs来判断的算法,可谓五花八门且很容易被hack掉。 以上,所以写这篇文章来总结一下我知道的且常用有效的三种判断方法。 ...
  • 0.1.2有向图判断是否存在 0.2无向图判 0.3有向图 1.有向图的拓扑排序 2.关键路径  2.1.邻接链表存储AOE网  2.1.1拓扑排序: bool TopologicalOrder(): 2.1.2关键路径:bool CriticalPath() 求...
  • 说明:我们选择的图是有向图,图的存储方式是邻接矩阵,使用C++语言,基于vs2010平台 算法思想:逐个对图的出度不为0的点进行遍历。假如是先对图A节点进行遍历:首先,将A节点所连接的点存储在数组vect1,然后...
  • 两种方式判断有向图是否有-python实现 1. DFS判断有向图是否有 假设图以邻接矩阵表示,一条深度遍历路线如果有结点被第二次访问到,那么有。我们用一个变量来标记某结点的访问状态(未访问,访问过,其后...
  • 判断有向图中是否存在

    千次阅读 2017-03-18 10:58:10
    步骤1:从0跳(节点自身)开始根据邻接矩阵逐跳添加节点:即如果节点i经过k-1跳可达节点m,且m存在到n的有向边;则i经过k跳可达n(注意处理i到n的其他更短路径),将n添加到nodeset_dst[i][k][ ]数组;并将nodeset_...
  • 简单方法判断邻接矩阵的有向图是否有求解思路实现代码如有不同见解,欢迎讨论 求解思路 1.统计所有节点的出度及其前序节点,初始化一个空的访问集合; 2.将出度为零的节点放入访问集合,并将其前序节点的出度数减1...
  • DFS 查找有向图中

    千次阅读 2018-03-28 10:34:10
    分析:首先那个样例来说 0 1 1 00 0 1 01 0 0 10 0 0 1四个定点(0,1,2,3),1代表xi到xj路.第一步:构造矩阵,也就是二维数组。第二步:选择起点进行深度探索,以0为起点第三步:开始探索: 0进栈或者用数组...
  • 如果学习x课程前必须先学习y课程,学习y课程前必须先学习z课程,学习z课程前必须先学习x课程,那么一定是有问题了...1.1检测有向环的API设计 在API添加onStack[]布尔数组,索引为的顶点,当我们深度搜索的时: ...
  • 判断有向图是否有

    千次阅读 2018-08-28 00:25:48
    要想对一副有向图进行拓扑排序,必须要保证有向图是无的,那么我们如何判断图是否含有呢?我们可以使用深度优先搜索来遍历图,并创建一个数组来标记顶点是否已经在递归栈,这样,当一个顶点指向的顶点已经在...
  • 找出无向图中所有的算法

    万次阅读 多人点赞 2016-07-13 16:25:47
    本文给出了一个找到无向图中所有的递归算法,该算法是基于DFS(深度优先搜索)的,大概的思路是:在深度优先搜索无向图的过程中,当遇到起始点的时候,会认定为出现(在本文中只是找出了无向图中所有的长度...
  • 此题是美团2017春招实习生在线笔试题,题目是“如何判断有向图有没有回路”,这里给出两种解法以供参考。解法一:深度遍历假设图以邻接矩阵表示,一条深度遍历路线如果有结点被第二次访问到,那么有。我们用一个...
  • Python 判断 有向图 是否有

    千次阅读 2017-04-17 20:48:48
    import numpy from numpy import * ...用到 numpy 模块,读取的 txt 文件为 有向图的连边,其中第一行 第一个数字 为 边的数量,第二个数字为 节点数 第二行及以后 前两个数字,第一个为 起点, 第二个为 落点。
  • 判断有向图是否存在

    万次阅读 多人点赞 2018-09-04 22:36:43
    简介  前面讨论的很多文章里,都是...和无向图比起来,有向图更加多了一种出入度的概念。因为方向的有向性,很多以前在无向图里看起来比较简单的问题在这里会变得更加有意思。   有向图定义  一个常用的有向...
  • 带你了解有向环图和拓扑排序

    千次阅读 2020-04-09 19:19:42
    在图论,如果一个有向图无法从某个顶点出发经过若干条边回到该点,则这个图是一个有向无图(DAG图)。而提到DAG,就差不多会联想到拓扑排序,拓扑排序是指由某个集合上的一个偏序得到该集合上的一个全序的操作。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 166,564
精华内容 66,625
关键字:

有向图中所有环