DepthFirstSearch java implementation

Question

I am trying to learn how to implement graphs (Depth First Search) into java. And here is a piece of code that I do not understand what a character means in here. It is about this piece of code:

    private void dfs(Graph G, int v) {
    count++;
    marked[v] = true;
    for (int w : G.adj(v)) {
        if (!marked[w]) {
            dfs(G, w);
        }
    }
}

I do not understand what "w" is about?!

Thanks.

EDIT: Here is the full code, maybe it will help you more to know excatly what is going on here:

package edu.princeton.cs.algs4;

public class DepthFirstSearch {
    private boolean[] marked;    // marked[v] = is there an s-v path?
    private int count;           // number of vertices connected to s


    public DepthFirstSearch(Graph G, int s) {
        marked = new boolean[G.V()];
        validateVertex(s);
        dfs(G, s);
    }


    private void dfs(Graph G, int v) {
        count++;
        marked[v] = true;
        for (int w : G.adj(v)) {
            if (!marked[w]) {
                dfs(G, w);
            }
        }
    }


    public boolean marked(int v) {
        validateVertex(v);
        return marked[v];
    }


    public int count() {
        return count;
    }


    private void validateVertex(int v) {
        int V = marked.length;
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
    }


    public static void main(String[] args) {
        In in = new In(args[0]);
        Graph G = new Graph(in);
        int s = Integer.parseInt(args[1]);
        DepthFirstSearch search = new DepthFirstSearch(G, s);
        for (int v = 0; v < G.V(); v++) {
            if (search.marked(v))
                StdOut.print(v + " ");
        }

        StdOut.println();
        if (search.count() != G.V()) StdOut.println("NOT connected");
        else                         StdOut.println("connected");
    }

}

Possible duplicate of [How does the Java 'for each' loop work?](https://stackoverflow.com/questions/85190/how-does-the-java-for-each-loop-work) — AxelH, Dec 07 '18 at 13:28

score 1 · Answer 1 · answered Dec 07 '18 at 13:26

1

The for loop in your example is a foreach loop. G.adj(v) most likely returns some collection. W represents each single element in the collection. For every element W in that collection do something.

answered Dec 07 '18 at 13:26

Amongalen

3,101
14
20

ZhaoGang · Accepted Answer · 2018-12-07T14:58:14.013

1

Although you just posted part of your code, I beleive that w stands for each node that is adjacent to the current node v. Or we can say that w stands for each element in G.adj(v),which should be an arrayList or something like that.

See foreach loop grammar here:How does the Java 'for each' loop work?

Updates:

Read the detailed code, though lack of the defination of Graph, still sure that what has been answered should be reasonable.

edited Dec 07 '18 at 14:58

answered Dec 07 '18 at 13:31

ZhaoGang

4,491
1
27
39

I just edited the code, I posted the full code maybe this will help you to clarify what that excatly is. Thanks for the link you sent, I'll look into it for more details. – Jay Dee Dec 07 '18 at 13:43

DepthFirstSearch java implementation

2 Answers2