使用迭代器在图上进行深度优先搜索

Question

我正在尝试将其变成深度优先搜索。起初它是广度优先的，现在我正在尝试转换它。我已经为此工作了 DAYS 并尝试了多种不同的方法。

        import java.util.*;


class Graph{
class Edge{
    int v,w;
    public Edge(int v,int w){
        this.v=v; this.w=w;
    }
    @Override
    public String toString(){
        return "("+v+","+w+")";
    }
}
List<Edge> G[];
public Graph(int n){
    G=new LinkedList[n];
    for(int i=0;i<G.length;i++)
        G[i]=new LinkedList<Edge>();
}
boolean isConnected(int u,int v){
    for(Edge i: G[u])
        if(i.v==v) return true;
    return false;
}
void addEdge(int u,int v,int w)
{

    G[u].add(0,new Edge(v,w));
    G[v].add(0,new Edge(u,w));
}
public int getWeight(int u, int v)
{
    for (Edge e : G[u]) 
    {
    if (e.v == v) 
        {
             return e.w ;
        }
    }throw new NoSuchElementException();
}
@Override
public String toString(){
    String result="";
    for(int i=0;i<G.length;i++)
        result+=i+"=>"+G[i]+"\n";
    return result;
}

// 这就是问题所在

   void DFS(int s)
{

    boolean visited[] = new boolean[G.length];

    LinkedList<Integer> stack = new LinkedList<Integer>();


    stack.push(s);

    while (stack.size() != 0)
    {

        s = stack.pop();
        System.out.print(s+" ");



        Iterator<Edge> i = G[s].listIterator();
         if (!visited[s])
            {
                visited[s] = true;

                 while (i.hasNext())
                 {
                    int n = i.next().v;
                    stack.push(n);


                 }

            }

    }
}

}

    public class GraphEx
    {
      public static void main(String[] args) 
   {    
      Graph g=new Graph(10);
      g.addEdge(1,2,38);
      g.addEdge(1,5 ,19);
      g.addEdge(1,3 ,35);
      g.addEdge(1,4 ,11);
      g.addEdge(4,3,27);
      g.addEdge(3,6,13);
      g.addEdge(3,5,28);
      g.addEdge(5,6,26);



    System.out.println(g);

    System.out.println("\nDFS");
    g.DFS(1);

打印出来：数字文件系统 1 2 1 5 1 3 1 4 1 3 6 3 5 5 6 3 4

如果第一部分没有为 2 之后的所有打印数字插入然后在 6 之后结束的那些，那将是完美的。这是最接近我认为我应该得到的输出我已经得到在我编写的所有代码中，我发布了这个。

编辑：这是我要重新转换的原件

        void BFS(int s)
{
    // Mark all the vertices as not visited(By default
    // set as false)
    boolean visited[] = new boolean[G.length];

    // Create a queue for BFS
    LinkedList<Integer> queue = new LinkedList<Integer>();

    // Mark the current node as visited and enqueue it
    visited[s]=true;
    queue.add(s);

    while (queue.size() != 0)
    {
        // Dequeue a vertex from queue and print it
        s = queue.poll();
        System.out.print(s+" ");

        // Get all adjacent vertices of the dequeued vertex s
        // If a adjacent has not been visited, then mark it
        // visited and enqueue it
        Iterator<Edge> i = G[s].listIterator();
        while (i.hasNext())
        {
            int n = i.next().v;
            if (!visited[n])
            {
                visited[n] = true;
                queue.add(n);
            }
        }
    }
}

Answer 1

DFS 是一种算法，通常运行在没有循环或链接回到其 parents 的树上。这会给您的图形实现带来两个非常简单的问题。问题 1 是您拥有的每个顶点都指向它 "parent"。例如，顶点 1 有一条边到顶点 2，顶点 2 有一条边到顶点 1。当边 2 被访问时，它的所有 children 都被放入堆栈。发生这种情况时，您会将已经访问过的顶点 1 放回堆栈。问题 2 是有时您会在访问顶点之前多次将它们压入堆栈。例如，顶点 5 和 3 在访问 6 之前都将 6 添加到堆栈中。快速解决这两个问题的一种方法是：

  while (stack.size() != 0)
    {
        s = stack.pop();
        if(visited[s]) //add these two lines
                continue; 
        System.out.print(s+" ");
        Iterator<Edge> i = G[s].listIterator();
        if (!visited[s])
            {
                visited[s] = true;
                while (i.hasNext())
                {
                   int n = i.next().v;
                   stack.push(n);
                }
            }

    }

如果您检查从堆栈中弹出的元素以查看它是否已被访问过，您将删除两个顶点，即 parents 已经被访问过的顶点，以及已被压入堆栈的节点他们 parents 多次。只需检查一个顶点是否已被访问，以及它是否刚刚继续循环的下一次迭代。

使用迭代器在图上进行深度优先搜索

Depth First Search on graph using Iterator

java

graph

depth-first-search