`
128kj
  • 浏览: 604173 次
  • 来自: ...
社区版块
存档分类
最新评论

深度优先搜索输出有向图中的所有环(JAVA)

    博客分类:
阅读更多
如图:求出有向图的所有环。


import java.util.ArrayList;
import java.util.Arrays;
public class TestCycle {
     private int n;
     private int[] visited;//节点状态,值为0的是未访问的
     private int[][] e;//有向图的邻接矩阵
     private ArrayList<Integer> trace=new ArrayList<Integer>();//从出发节点到当前节点的轨迹
     private boolean hasCycle=false;

     public TestCycle(int n,int[][] e){
         this.n=n;
         visited=new int[n];
         Arrays.fill(visited,0);
         this.e=e;
     }
    
     void findCycle(int v)   //递归DFS
    {
        if(visited[v]==1)
        {
            int j;
            if((j=trace.indexOf(v))!=-1)
            {
                hasCycle=true;
                System.out.print("Cycle:");
                while(j<trace.size())
                {
                    System.out.print(trace.get(j)+" ");
                    j++;
                }
                System.out.print("\n");
                return;
            }
            return;
        }
        visited[v]=1;
        trace.add(v);
        
        for(int i=0;i<n;i++)
        {
            if(e[v][i]==1)
                findCycle(i);
        }
        trace.remove(trace.size()-1);
    }
  
  public boolean getHasCycle(){
      return hasCycle;
  }

   public static void main(String[] args) {
        int n=7;
        int[][] e={
                    {0,1,1,0,0,0,0},
                    {0,0,0,1,0,0,0},
                    {0,0,0,0,0,1,0},
                    {0,0,0,0,1,0,0},
                    {0,0,1,0,0,0,0},
                    {0,0,0,0,1,0,1},
                    {1,0,1,0,0,0,0}};//有向图的邻接矩阵,值大家任意改.
        TestCycle tc=new TestCycle(n,e);
        tc.findCycle(1);
        if(!tc.hasCycle) 
            System.out.println("No Cycle.");
    }
}



运行:
C:\java>java   TestCycle
Cycle:4 2 5
Cycle:1 3 4 2 5 6 0
Cycle:2 5 6 0
Cycle:2 5 6

源码:
  • 大小: 4.4 KB
分享到:
评论

相关推荐

    Java版查找并打印有向图中的所有环路径

    在标题中提到的"Java版查找并打印有向图中的所有环路径",这个问题涉及到图论中的一个经典问题——寻找环路。在实际应用中,如线程死锁识别,有向图的环路检测具有重要价值,因为线程间的资源依赖关系可以被抽象为有...

    有向图存储和遍历-java实现.zip

    3. **图的遍历**:在Java中,有向图的遍历通常包括深度优先搜索(DFS)和广度优先搜索(BFS)。 - **深度优先搜索**:DFS从一个起始顶点开始,沿着某一条路径尽可能深地探索图的分支,直到达到叶子节点或者回溯到...

    图的遍历(有向图和无向图)

    在有向图中,DFS可能会形成深度优先生成树;而在无向图中,DFS遍历会形成一棵树,每个节点最多被访问一次。 **非递归DFS** 可以通过栈来实现。初始化一个空栈,将起始节点压入栈中,然后进入一个循环,每次从栈顶...

    图的创立数据结构对其进行深度优先遍历和广度优先遍历

    总结来说,这段代码提供了创建邻接表表示的无向图的方法,以及从任意顶点出发的深度优先遍历和广度优先遍历算法。这些工具对于理解和操作图数据结构,如路径查找、连通性分析等,都是非常有用的。

    已知有向图和图中两个顶点u和v,试编写算法求有向图中从u到v的所有简单路径。

    通过以上分析可以看出,寻找有向图中从顶点u到顶点v的所有简单路径的问题可以通过深度优先搜索(DFS)的方法来解决。在这个过程中,递归和回溯起到了关键的作用。通过对代码的逐行解析,我们可以更深入地理解算法的...

    java 求一个有向图中的环路问题

    总之,解决Java中有向图的环路问题主要涉及深度优先搜索算法的应用。通过DFS遍历图,我们可以有效地检测和打印出所有的环路。在实际编程中,可以依据具体需求进行相应的优化和扩展,例如处理大规模图、优化内存使用...

    蓝桥杯深度优先搜索

    6. **强连通分量**:在有向图中,两个节点互相可达则称它们强连通。DFS可以找出所有的强连通分量,首先从任意一个节点开始DFS,将所有可达的节点加入同一个强连通分量,然后对剩余未访问的节点重复此过程。 7. **...

    数据结构课有向图接口

    - **遍历图(Traversal)**:可以使用深度优先搜索(DFS)或广度优先搜索(BFS)遍历图的所有顶点。 - **获取邻接顶点(GetAdjVertices)**:返回指定顶点的所有邻接顶点列表。 - **获取顶点数(GetVertexCount)**:返回图...

    scc.rar_connected component_scc java_强连通_有向图

    标题中的“scc.rar”可能是一个压缩文件,包含了一个用于计算有向图强连通分量的Java程序。"connected component"和"scc_java"标签表明这个程序或数据集关注的是寻找有向图的强连通分量。"强连通"指的是图中的一种...

    有向图的邻接矩阵.。。

    在图论中,有向图广泛应用于网络分析、数据流建模、计算机科学算法等多个领域。邻接矩阵是表示有向图的一种常用方法,尤其在处理图形数据时非常实用。 邻接矩阵是一个二维数组,用来表示图中节点之间的连接关系。...

    图的深度和广度优先遍历源程序及实验报告还有PPt

    特别是在处理图数据结构时,深度优先搜索(DFS)和广度优先搜索(BFS)这两种遍历算法被广泛运用于路径查找、网络爬虫、社交网络分析等众多实际问题中。 深度优先遍历(DFS)是一种系统地沿着图的分支遍历每个节点...

    邻接矩阵实现图的广搜和深搜(java模板)

    对于无向图,邻接矩阵是对称的,而对于有向图,它可能不对称。 **深度优先搜索(DFS)** 是一种遍历或搜索树或图的算法,它沿着树的深度遍历树的节点,尽可能深地搜索分支。在邻接矩阵中实现DFS,通常使用递归或栈...

    java计算图两点之间的所有路径

    在Java编程中,计算图中两点之间的所有路径是一项常见的任务,尤其在图形算法和网络路径查找等场景。这里我们讨论的是一种基于深度优先搜索(DFS)的算法来解决这一问题。 首先,我们要定义图的数据结构。通常,...

    DFS.rar_dfs_dfs java_图的遍历_无向图 java

    深度优先搜索(Depth First Search, DFS)是一种在图或树数据结构中进行遍历或搜索的算法。在本文中,我们将深入探讨DFS的概念、实现方式以及如何在Java中应用于无向图。 首先,DFS的基本思想是从起始节点出发,...

    Java经典算法(通用搜索算法及实现)

    综上所述,Java经典算法在解决组合问题和优化问题时,通过状态空间树的搜索策略,如深度优先搜索和启发式搜索,可以有效地找到解。N皇后问题和点着色问题的实例展示了这些算法在实际问题中的应用。理解和熟练掌握...

    无向连通图两点间所有路径的算法

    综上所述,无向连通图中两点间所有路径的算法是一个典型的深度优先搜索加回溯的示例。通过递归地探索所有可能的路径组合,同时利用栈数据结构进行状态管理,算法能够高效、准确地找出所有合法路径,为理解和解决类似...

    拓扑排序应用系统java.zip

    拓扑排序是图论中的一个重要概念,主要应用于有向无环图(DAG,Directed Acyclic Graph)。在Java编程中,拓扑排序可以用于解决各种依赖关系的排序问题,例如项目构建顺序、任务调度等。这个名为"拓朴排序应用系统...

    initRecherche:有向图处理java应用

    **标题解析:** "initRecherche:有向图处理java应用" 这个标题表明我们正在探讨一个使用Java编程语言实现的项目,该项目专注于处理有向图(Directed Graph)。"initRecherche"可能是项目中一个特定的初始化搜索功能...

Global site tag (gtag.js) - Google Analytics