CODEWITHSUNDEEP
javagraphdepth-first-search
amine
amine

Reputation: 53

Depth First Search on graph java

I am having a bit of a problem implementing DFS traversal in java. My problem I think is the 'dfs' method in Graph.java I coded. It is not returning the required output giving it a specific input. My code is below along with its input and desired output. Could someone help me solve this problem in my code. Thanks.

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();
}

} enter image description here

Upvotes: 2

Views: 1287

Answers (1)

Amin J
Amin J

Reputation: 1209

You almost had it. You don't need the stack in your dfs. Simplify it like this: 

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

Just print the results in your 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);
        }
    }
}

You are simply calling dfs, marking anything reachable as you along and updating the parent. Once you are done, just go through all vertices and print the ones that were reachable (except the source itself).

And here is the output I'm getting:

1:0 
2:1 
3:8 
4:5 
5:6 
6:2 
7:10 
8:7 
9:5 
10:5

I also recommend you to refactor your code and move the command line reads to your main instead of Graph constructor. Just read the numbers and call g.addEdge in order to build your graph.

Upvotes: 1

Related Questions