精华内容
下载资源
问答
  • key ...标识数组:有向标识矩阵 public class Graph { public static void main(String[] args) { int[][] graph = { {0, 2, 0, 0}, {0, 0, 3, 0}, {1, 0, 0, 4}, {2, 2, 0, 0} }; new Grap

    key

    • 临接矩阵
    • dfs递归遍历
    • 回溯
    • 标识数组:有向标识矩阵
    public class Graph {
        public static void main(String[] args) {
            int[][] graph = {
                {0, 2, 0, 0},
                {0, 0, 3, 0},
                {1, 0, 0, 4},
                {2, 2, 0, 0}
            };
            new Graph().dfs(graph, 3);
        }
    
        public void dfs(int[][] graph, int node) {
            boolean[][] flag = new boolean[graph.length][graph.length];
            int cnt = dfs(graph, flag, node, node);
            System.out.println(cnt);
        }
    
        private int dfs(int[][] graph, boolean[][] flag, int start, int end) {
            int cnt = 0;
    
            int[] row = graph[start];
            for (int i = 0; i < row.length; i++) {
                if (row[i] != 0 && !flag[start][i]) {
                    if (i == end) {
                        cnt++;
                    } else {
                        flag[start][i] = true;
                        cnt += dfs(graph, flag, i, end);
                        flag[start][i] = false;
                    }
                }
            }
    
            return cnt;
        }
    }
    
    
    展开全文
  • [C++]C++ STL 环检测 带权有向图 DFS

    千次阅读 2017-01-02 18:36:20
    环检测完整源码#include #include <vector> #include #include #include using namespace std;int V, E;//带权有向图 map, vector, int , double>>> EWD;bool marked[100]; /

    环检测

    完整源码

    #include <iostream>
    #include <vector> 
    #include <tuple>
    #include <stack>
    #include <map>
    using namespace std;
    
    int V, E;
    
    //带权有向图
    map<int, vector<tuple<int , int , double>>> EWD;
    
    bool marked[100];   // v 是否已经被访问过?
    bool onStack[100];  // v 是否在栈里?
    tuple<int , int , double> edgeTo[100]; // 到达顶点 v 的最后一条边
    stack<tuple<int , int , double>> cycle; // 有向环
    
    
    void dfs(int v) {
        onStack[v] = true;
        marked[v] = true;
    
        for(vector<tuple<int, int, double>>::iterator ii = EWD[v].begin(); ii != EWD[v].end(); ii++)
        {
    
            int w = get<1>(*ii);
    
            if(!cycle.empty()) {    // 已经找到了一个有向环
                return;
            }
            else if(!marked[w]) {   // 遇见没访问过的顶点继续dfs递归
                edgeTo[w] = *ii;
                dfs(w);
            }
            else if(onStack[w]) {   // 遇见一个访问过的顶点,并且该顶点在栈里说明发现了一个新环
                tuple<int, int, double> f = *ii;
                while(get<0>(f) != w) {
                    cycle.push(f);
                    f = edgeTo[get<0>(f)];
                }
    
                cycle.push(f);
                return ;
    
            }
        }
    
        onStack[v] = false;
    }
    
    void findCycle() {
        for(int v = 0 ; v < V; v++)
            if(!marked[v]) dfs(v);
    }
    
    void showCycle() {
        cout << "Cycle : " << endl;
        while(!cycle.empty()) {
            tuple<int, int, double> f = cycle.top(); 
            cout << get<0>(f) << "->" << get<1>(f) << " " << get<2>(f) << endl;
            cycle.pop();
        }
        cout << endl;
    }
    
    
    void readData() {
        cin >> V >> E;
        for(int i = 0 ; i < E ;i++)
        {
            int v, w;
            double weight;
            cin >> v >> w >> weight;
            EWD[v].push_back(make_tuple(v, w, weight));
        }
    }
    
    void showData() {
        cout << "EdgeWeightedDigraph : " << endl;
        for(int v = 0; v < V; v++) 
        {
            cout << v << " : ";
            for(vector<tuple<int, int, double>>::iterator ii = EWD[v].begin(); ii != EWD[v].end(); ii++)
                cout << get<0>(*ii) << "->" << get<1>(*ii) << " " << get<2>(*ii) << "  ";
            cout << endl;
        }
    
        system("pause");
    }
    
    int main()
    {
        readData();
        showData();
    
        findCycle();
        showCycle();
    
    }
    

    测试运行

    模拟数据

    模拟数据有向图带环

    运行结果

    环检测运行结果

    4
    4
    0 1 0.1
    0 2 0.2
    2 3 0.3
    3 0 0.4
    EdgeWeightedDigraph :
    0 : 0->1 0.1  0->2 0.2
    1 :
    2 : 2->3 0.3
    3 : 3->0 0.4
    
    请按任意键继续. . .
    Cycle :
    0->2 0.2
    2->3 0.3
    3->0 0.4
    
    --------------------------------

    简单地说

    1. 0出发,往左边走,先遇到1,到头了,回不到0,这不是环;
    2. 0出发,往右边走,先遇到2,继续往深处走,遇到3,再往深处走,遇到00不仅访问过还在栈上面,这是环;

    代码说明

    数据类型

    tuple<int , int , double> edgeTo[100]; // 到达顶点 v 的最后一条边
    
    stack<tuple<int , int , double>> cycle; // 有向环
    1. 有向边,顶点、顶点、权重,其实本文重点是 检测,带不带权重都不重要,算法都一样;
    2. stack来存这条被找出来的有向边;

    主程序

    int main()
    {
        readData();  // 数据输入
        showData();  // 显示有向图
    
        findCycle(); // 找到一个环
        showCycle(); // 显示找到的环
    
    }

    环检测

    void findCycle() {
        for(int v = 0 ; v < V; v++)
            if(!marked[v]) dfs(v);
    }
    
    
    void dfs(int v) {
        onStack[v] = true;
    
        marked[v] = true;
        for()
        {
            if(!cycle.empty()) { 
                return; 
            }
            else if(!marked[w]) {   
                edgeTo[w] = *ii;
                dfs(w);
            }
            else if(onStack[w]) {
            }   
        }
    
        onStack[v] = false;
    }
    1. 本质就是DFS搜索,增加了onStack数组来表示出现在 本次递归 之中的顶点;
    2. onStack[]数组就是显式地把内存栈的调用过程摆出来;
    3. 两个else if 等价于 if(marked[w] && onStack[w]),被访问过也要在 本次递归 之中;

    继续DFS

     else if(!marked[w]) {   // 遇见没访问过的顶点继续dfs递归
                edgeTo[w] = *ii;
                dfs(w);
            }
    • marked[] 数组和DFS“打包”使用的,不要多想;

    把环存起来

     else if(onStack[w]) {   
                tuple<int, int, double> f = *ii;
                while(get<0>(f) != w) {
                    cycle.push(f);
                    f = edgeTo[get<0>(f)];
                }
    
                cycle.push(f);
                return ;
    
            }
    • 因为存的是有向边,顺着边,从tofrom,往回爬,爬到环的起点(就是那个被发现被访问的并且在本次递归中的点)就行了;

    显示环

    void showCycle() {
        cout << "Cycle : " << endl;
        while(!cycle.empty()) {
            tuple<int, int, double> f = cycle.top(); 
            cout << get<0>(f) << "->" << get<1>(f) << " " << get<2>(f) << endl;
            cycle.pop();
        }
        cout << endl;
    }
    • 就是把栈的内容拿出来;

    思考体会

    1. 递归写代码还是很不熟练,这个代码完全是照着algs4的代码写的,只不过是一种C++ STL的实现;
    2. C++ STL其实也还不熟练,比如我觉得我应该是可以把tuple<int, int, double> 用个什么typedef还是struct打包一下,不用每次都copy这一串,但是我觉得我要写个环检测,也没必要先穷尽C++ STL 再写吧,嗯,可以以后改进这里;
    3. 其实一开始我在showCycle() 直接写了个cout << f ;,我一开始写C++的输出语句还是用的Cprintf,后来发现cout是个好东西,什么都可以装,就直接用cout了,这里还是要分开写的;
    4. 代码里还是有把功能和具体实现没有分开的问题,比如tuple<int, int, double> ,用get<0>取出来的是from,以此类推,但是现在感觉这里似乎不要把细节暴露出来比较好。

    参考引用

    [1] C++ STL stack
    http://www.cplusplus.com/reference/stack/stack/
    [2] algs4 Finds a directed cycle in an edge-weighted digraph.
    http://algs4.cs.princeton.edu/44sp/EdgeWeightedDirectedCycle.java.html

    展开全文
  • DFS判断有向图是否存在 对一个节点有三种情况,还未访问,正在访问,访问结束 我们用0,1,-1,正在访问表示还在递归中未出来,如果相连节点都正在访问 说明在DFS过程中一条道路上访问了两次同一个节点,这说明有...

    DFS判断有向图是否存在环

    对一个节点有三种情况,还未访问,正在访问,访问结束
    我们用0,1,-1,正在访问表示还在递归中未出来,如果相连节点都正在访问
    说明在DFS过程中一条道路上访问了两次同一个节点,这说明有环
    下面用代码实现

    class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
                if(findOrder(numCourses,prerequisites))
                {
                    return false;
                }
                else
                {
                    return true;
                }
        }
        int[] state ;
        Map<Integer,List<Integer>> map =new HashMap<Integer,List<Integer>>();
        void init(int numCourses, int[][] prerequisites)//初始化操作
        {
            state = new int[numCourses];//存放状态
            for(int i=0;i<numCourses;i++)
            {
                map.put(i,new ArrayList<Integer>());
            }
            for(int i=0;i<prerequisites.length;i++)
            {
                map.get(prerequisites[i][1]).add(prerequisites[i][0]);//建立领接列表存储节点
            }
        }
        public boolean findOrder(int numCourses, int[][] prerequisites) {
            init(numCourses,prerequisites);
            for(int i=0;i<numCourses;i++)
                {
                    if(DFS(i))
                        return true;
                    for(int k=0;k<numCourses;k++)
                    {
                        state[k]=0;
                    }
                }
                return false;
        }
         boolean DFS(int start)
      {
          if(state[start]==-1)//防止出现死循环
          {
                return  false;
          }
         if(state[start]==1)//正在访问
         {
             return true;
         }
         else
         {
             state[start]=1;
             for(int i=0;i<map.get(start).size();i++)
             {
                 if(DFS(map.get(start).get(i)))//发现有环,一直往上回退直到退出
                     return true;
            }
             state[start]=-1;
         }
         return  false;
      }
    }
    
    
    展开全文
  • 1:判断无向图是否有环: 如果图g有环,用dfs遍历图g,会访问到已经访问过的顶点。 2:判断无向图是否为二分图:利用gfs遍历图给图上色(2种颜色),然后判断上色顶点间是否冲突。若冲突,则为非二分图。 package...
    1:判断无向图是否有环: 如果图g有环,用dfs遍历图g, 会访问到已经访问过的顶点。
    2:判断无向图是否为二分图: 利用gfs遍历图给图上色(2种颜色),然后判断上色顶点间是否冲突。若冲突,则为非二分图。


    package Graph;
     
    import java.util.ArrayList;
    import java.util.LinkedList;
     
    public class Graph {
        private ArrayList<LinkedList<Element>> tableGrap;
        private int v;//顶点数
        private int e;//边数
         
        private boolean[] isVisited;//顶点的访问状态
        private boolean hasCycle;//是否有环
         
        private boolean[] color;//给图上色(两种颜色),用以判断是否二分图
        private boolean isTwoColorable = true;//是否二分图
         
        public Graph(int v,LinkedList<Element> list){
            this.v = v;
            isVisited = new boolean[v];
             
            tableGrap = new ArrayList<>();
            for(int i=0;i<v;i++)
                tableGrap.add(new LinkedList<Element>());
             
            create(list);
        }
     
        private void create(LinkedList<Element> list) {
            // TODO Auto-generated method stub
            for (Element ele : list) {
                tableGrap.get(ele.u).add(ele);
                tableGrap.get(ele.v).add(new Element(ele.v,ele.u));
                e++;
            }
        }
         
        //判断是否二分图
        public void isTwoGraph(){
            isVisited = new boolean[v];
            color = new boolean[v];
             
            for(int s=0;s<v;s++){
                if(!isVisited[s])
                    dfs(s);
            }
        }
        //用dfs给顶点上色判断是否二分图
        private void dfs(int u){
            isVisited[u] =  true;
            for(Element ele : tableGrap.get(u)){
                if(!isVisited[ele.v]){
                    color[ele.v] = !color[u];
                    dfs(ele.v);
                }
                else if(color[ele.v] == color[v]) {
                    System.out.println("非二分图")
                    isTwoColorable = false;
                }
            }
        }
         
        //是否有环
        public void isCycle(){
            isVisited = new boolean[v];
            for(int s=0;s<v;s++){
                if(!isVisited[s])
                    dfs(this,s,s);
            }
        }
         
        //dfs判断是否有环
        private void dfs(Graph graph, int v, int u) {
            // TODO Auto-generated method stub
            isVisited[v] = true;
            for(Element ele : tableGrap.get(v)){
                if(!isVisited[ele.v]){
                    dfs(this,ele.v,v);
                }else{
                    if(ele.v != u) {
                        hasCycle = true;
                        System.out.println("有环");//访问已经访问过的顶点,说明有环
                    }
                }
            }
        }
     
        public static void main(String[] args){
            LinkedList<Element> list = new LinkedList<>();
            list.add(new Element(0,2));
            list.add(new Element(0, 1));
            list.add(new Element(0, 5));
            list.add(new Element(2,1));
            list.add(new Element(2,3));
            list.add(new Element(2,4));
            list.add(new Element(3,4));
            list.add(new Element(5,3));
             
            Graph graph = new Graph(6, list);
            graph.isCycle();
            graph.isTwoGraph();
        }
         
    }
     
    //
    class Element{
        int u;
        int v;
        int weight;
         
        public Element(int u,int v){
            this.u = u;
            this.v = v;
    //      this.weight = we
        }
    }


    展开全文
  • #include <iostream> #include <vector> using namespace std; vector<int> in[1200]; int color[1200]; bool flag = false;...void dfs(int x) { if (flag) { return; } color...
  • 【0】README0.1) 本文总结于 数据结构与算法分析, 源代码均为原创, 旨在 理解 “DFS应用——遍历有向图+判断有向图是否有圈” 的idea 并用源代码加以实现 ; 0.2) 判断有向图是否有圈的rule—— 一个有向图是无...
  • 有向图中有向环检测

    千次阅读 2018-01-02 10:55:08
    寻找有向图中是否存在有向是判定一个任务优先级问题的前提边的类型从某个点开始的深度搜索过程中遇到了后向边,可作为找到有向的标志代码实现private boolean[] onStack = new boolean[V];public void dfs(int s...
  • 有向图是否存在 LeetCode题目:207. Course Schedule 题目链接:https://leetcode.com/problems/course-schedule/ 题目大意:         现在你总共有 n 门课需要选,记为 ...
  • dfs判断一个有向图是否有

    万次阅读 2018-01-18 20:23:34
    解决这个问题的算法的思路是对一个节点u进行dfs,判断是否能从u回到...如果一个状态为“0”的结点,与他相连的结点状态也为“0”的话就代表有环,这个可以用dfs实现 #include <iostream> #include <vect...
  • 图论中用后检测环,算法导论中介绍,这里是一个实现
  • 利用DFS判断一个有向图是否有的思路是:对一个节点v进行深度遍历,判断是否能从v到达自己这个节点,即是否存在从v到v的环路。 在图的深度遍历中,我们将图中每个节点设置为三个状态:-1,0,1,分别表示还没发现的...
  • #include <iostream> #include <cstdio> #include <vector> #include <cstring> #include <string> #include <algorithm>... // 分别是时间撮,是否有环 int f..
  • 采用深度优先算法(DFS)遍历有向环图寻找最优路径,经过优化的深度优先算法,在遍历有向环图的时候保存路径,并计算路径权值,最总返回最优路径及最有路径的权值
  • BFS DFS 判断DAG(有向环图)

    千次阅读 2020-03-26 20:06:25
    title: BFS DFS 判断DAG(有向环图) date: 2020-03-26 18:56:47 tags: Algorithm BFS DFS 判断DAG(有向环图) 前几天美团笔试 ,笔试里有一个单源最短路问题(直接弃了,完全没想到会考图论的问题,Dijkstra算法...
  • 采用深度优先算法(DFS)遍历有向环图寻找最优路径,经过优化的深度优先算法,在遍历有向环图的时候保存路径,并计算路径权值,最总返回最优路径及最有路径的权值
  • 有向图和无向图的环检测 1.无向图 可以用DFS检测,思想是,DFS过程,记录当前结点的父结点,如果某结点以及访问过且不是该结点的父结点,则存在环
  • 图论算法——dfs有向图和无向图两点间所有路径

    千次阅读 多人点赞 2019-06-12 09:28:24
    DFS作为搜索算法,最常用于,对图的遍历,探寻路径,甚至是求一些情况下的最短路。我在这里就介绍一下dfs求两点的的所有路径,这个算法最开始在数据结构大作业里面用到了,当时费了一番劲写出来后,就想oj题里面...
  • 判断无向图/有向图中是否存在

    千次阅读 2019-02-03 11:54:50
    利用DFS判断有向图是否存在,是最为常用的一种方法,虽然这种方法很常用,但可参考的代码的实现比较少,下面对这种方法及其实现进行详细的阐述。 首先,利用DFS判断无向图中是否换的原理是:若在深度优先搜索的...
  • 带权有向图找到全部的完整源码#include #include <vector> #include #include #include using namespace std;int V, E; int n;//带权有向图 map, vector, int , double>>> EWD;bool m

空空如也

空空如也

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

dfs有向图环检测