搜尋此網誌

2012年5月21日 星期一

Directed Graph Traversal using recursive DFS



import java.util.Stack;

public class RecursiveDFS {

    public static int graph[][] = {

            { 1, 2 },// 0

            { 0, 3, 4 },// 1

            { 0, 5, 6 },// 2

            { 1, 7 },// 3

            { 1, 7 },// 4

            { 2, 7 },// 5

            { 2, 7 },// 6

            { 3, 4, 5, 6 } // 7

    };

    static int visited[] = { -1, -1, -1, -1, -1, -1, -1, -1 };// Initialize all
                                                                // unvisited.

    public static int[] findNeighbours(int v) {

        return graph[v];

    }

    public static boolean isVisited(int v) {
        if (visited[v] == 1)
            return true;
        else
            return false;
    }

    public static void recursiveDFS(int vertex) {
        System.out.print(vertex);
        visited[vertex] = 1;
        int neighbours[] = findNeighbours(vertex);
        for (int i = 0; i < neighbours.length; i++) {
            if (!isVisited(neighbours[i])) {
                recursiveDFS(neighbours[i]);
            }
        }

    }

    public static void main(String[] args) throws InterruptedException {
        recursiveDFS(0);
    }

}

沒有留言:

張貼留言