反转图上的 DFS

Question

我必须在图上使用 DFS，然后在反转图上使用 DFS，并且图是有向的。我很好奇，不是先将邻接列表反转为另一个邻接列表，然后将其复制回原始邻接列表，然后再次调用 DFS，有没有什么方法可以让我知道我必须使用邻接来编写 DFS 函数以相反的方式列出。以下是我的 Java 代码，我用它来判断我的图是否是强连接的，或者 not.I 对 help.In 非常有帮助简而言之，我想避免 rev_graph功能并最小化我的代码。

    import java.util.*;
    class Strongly_conn
    {
     static ArrayList<LinkedList<Integer>> g;
     static ArrayList<LinkedList<Integer>> g1;
     static int []visited;
     public static void create_graph()
     {
      int n,i,k,j;
      Scanner s=new Scanner(System.in);
      System.out.println("enter the value of number of vertices");
      n=s.nextInt();
      visited=new int[n];
      for(i=0;i<n;++i)
       visited[i]=0;
      g=new ArrayList<LinkedList<Integer>>();
      for(i=0;i<n;++i)
      {
       g.add(new LinkedList<Integer>());
       System.out.println("enter the number of vertices adjacent to "+ (i+1)+" and what are they?" );         
       k=s.nextInt();
       for(j=1;j<=k;++j)
       g.get(i).add(s.nextInt());
      }      
     }
     public static void main(String []args)
     {
      int so,i;      
      Scanner s=new Scanner(System.in);
      create_graph();
      System.out.println("enter any vertex");
      so=s.nextInt();
      DFS(so);
      for(i=0;i<g.size();++i)
       if(visited[i]==1)
       continue;
       else {System.out.println("the directed graph is not strongly connected");System.exit(0);}
      for(i=0;i<g.size();++i)
       visited[i]=0;
      rev_graph(); 
      DFS(so);
      for(i=0;i<g.size();++i)
       if(visited[i]==1)
        continue;
       else {System.out.println("the directed graph is not strongly connected");System.exit(0);}
      System.out.println("the directed graph is strongly connected"); 
     }
      public static void DFS(int s)
      {
       visited[s-1]=1;     
       for(int e:g.get(s-1))
        if(visited[e-1]==0)
       DFS(e);
       else continue;
      }
      public static void rev_graph()
      {
       int i;
       g1=new ArrayList<LinkedList<Integer>>();
       for(i=0;i<g.size();++i)
        g1.add(new LinkedList<Integer>());
       for(i=0;i<g.size();++i)
       for(int e:g.get(i))
        g1.get(e-1).add(i+1);
       g=new ArrayList<LinkedList<Integer>>(g1);
      }       
     }

Answer 1

思路是在遍历图的同时访问一个节点，将访问过的节点入栈，将所有节点入栈后，通过逆向遍历的方式出栈，得到同一个图的逆序遍历。这很可能会奏效。

Answer 2

这里的基本思想不是遍历所有集合节点的子节点，而是遍历其父节点。假设您有一个邻接矩阵（正如您所指出的），而不是查找特定行的所有设置的列，而是查看为该节点设置的所有行。

示例：

假设你有一个像

这样的图表

1 -> 2
4 -> 1
3 -> 2
4 -> 3

所以你的矩阵是：

[0 1 0 0]
[0 0 0 0]
[0 1 0 0]
[1 0 1 0]

所以在这里，如您所见，节点 1 有一个子节点 2（从第一行开始）。但是，如果您查看列（第 2 列），2 是 1 和 3 的子项。因此，您可以将 1 和 3 添加到您的堆栈并继续。

反转图上的 DFS

DFS on reversed graph

java

graph

depth-first-search