图上的深度优先搜索 java

Question

我在 java 中实现 DFS 遍历时遇到了一些问题。我认为我的问题是我编码的 Graph.java 中的 'dfs' 方法。它没有返回给它特定输入的所需输出。下面是我的代码及其输入和所需的输出。有人可以帮我解决我的代码中的这个问题。谢谢

Graph.java

public class Graph {
ArrayList<Vertex> Vertices=new ArrayList<Vertex>();
Stack<Integer> stack=new Stack<Integer>();
public Graph(){
    Scanner in=new Scanner(System.in);
    String sz=in.nextLine();
    int size=Integer.parseInt(sz);
    for(int i=0; i<size; i++) addVertex();
    String s=in.nextLine();
    while(!s.equals("-1")){
        String[] arr=s.split(",");
        int v1=Integer.parseInt(arr[0]);
        int v2=Integer.parseInt(arr[1]);
        addEdge(v1,v2);
        s=in.nextLine();
    }

    //Vertex v=Vertices.get(2);
    //System.out.println(dfs(v));
}

public static void main(String[] args){
    new Graph();
}
public void addVertex(){
    Vertex v=new Vertex(Vertices.size());
    Vertices.add(v);
}
public Vertex getVertex(int n){
    return Vertices.get(n);
}
public void addEdge(int n, int m){
    Vertex v1=Vertices.get(n);
    Vertex v2=Vertices.get(m);
    v1.addAdjacency(v2);
    v2.addAdjacency(v1);
}
public void dfs(Vertex obj){
    obj.marked=true;
    int k=0;
    for(Vertex v:obj.Vertices){
        Vertex d=v;
        if(!d.marked){
            d.parent=obj;
            k=d.parent.vertexNumber;
            stack.push(k);
            dfs(d);
        }
    }
}
}

Vertex.java

public class Vertex {
int vertexNumber;
Vertex parent = null;
boolean marked = false;
LinkedList<Vertex> Vertices = new LinkedList<Vertex>();

public Vertex(int num) {
    vertexNumber = num;
}

public void addAdjacency(Vertex object) {
    Vertices.add(object);
}

public boolean isAdjacent(Vertex object) {
    if (Vertices.contains(object))
        return true;
    else
        return false;
}

public int getDegree() {
    return Vertices.size();
}

}

Answer 1

你几乎成功了。你不需要 dfs 中的堆栈。像这样简化它：

public void dfs(Vertex obj) {
    obj.marked = true;
    for (Vertex v : obj.Vertices) {
        if (!v.marked) {
            v.parent = obj;
            dfs(v);
        }
    }
}

只需在您的 main 中打印结果：

public static void main(String[] args) {
    Graph g = new Graph();
    Vertex source = g.Vertices.get(0);
    g.dfs(source);

    for(Vertex v:g.Vertices){
        if (v!= source && v.marked){
            System.out.println(v.vertexNumber+":"+v.parent.vertexNumber);
        }
    }
}

您只是简单地调用 dfs，标记您可以访问的任何内容并更新父级。完成后，只需遍历所有顶点并打印可到达的顶点（源本身除外）。

这是我得到的输出：

我还建议您重构代码并将命令行读取移至主构造函数而不是 Graph 构造函数。只需阅读数字并调用 g.addEdge 即可构建您的图表。

图上的深度优先搜索 java

Depth First Search on graph java

java

graph

depth-first-search