java - 反转图上的 DFS

Question

我必须在图上使用 DFS，然后在反转图上使用 DFS，并且该图是有向的。我很好奇，不是首先将邻接列表反转到另一个邻接列表，然后将其复制回原始邻接列表，然后再次调用 DFS，有没有什么方法可以编写 DFS 函数，知道我必须使用邻接以相反的方式列出。以下是我的Java代码，我用它来判断我的图是否强连接。我将非常有帮助。简而言之，我想避免 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

这个想法是，当你在访问一个节点时遍历图，将访问过的节点放入堆栈中，将所有节点放入堆栈后，然后使用反向遍历方法弹出堆栈，你将得到同一个图的逆序遍历。这很可能会起作用。