图的深度遍历+广度遍历--java

图的深度遍历:

import java.util.*;

public class Main {
    static int getFirst(int v) {
        for (int i = v + 1; i < n; i++) {
            if (i != v && graph[i][v] > 0) {
                return i;
            }
        }
        return -1;
    }

    static int getNext(int v, int w) {
        for (int i = w + 1; i < n; i++) {
            if (i != v && graph[i][v] > 0) {
                return i;
            }
        }
        return -1;
    }

    static int n = 5;
    static int[][] graph = new int[n][n];

    public static void main(String[] args) throws InterruptedException {


        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    graph[i][j] = 0;
                } else {
                    graph[i][j] = -1;
                }
            }
        }

        graph[0][2] = graph[2][0] = 1;
        graph[2][4] = graph[4][2] = 1;

        //深度遍历
        dfs();
        //广度遍历
        bfs();
    }


    static void dfs() {
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(visited, i);
            }
        }

    }

    static void dfs(boolean[] visited, int v) {
        System.out.print(v + "->");
        visited[v] = true;
        int w = getFirst(v);
        while (w > 0) {
            if (!visited[w]) {
                dfs(visited, w);
            }
            w = getNext(v, w);
        }
    }

    static void bfs() {
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                bfs(visited, i);
            }

        }
    }

    static void bfs(boolean[] visited, int v) {
        Queue<Integer> queue = new LinkedList();
        queue.offer(v);
        while (!queue.isEmpty()) {
            v = queue.poll();
            if (v >= 0 && !visited[v]) {
                System.out.print(v + "->");
                visited[v] = true;
                int w = getFirst(v);
                queue.offer(w);
                w = getNext(v, w);
                while (w > 0) {
                    queue.offer(w);
                    w = getNext(v, w);
                }
            }
        }
    }

}
个人资料
时海
等级:8
文章:272篇
访问:16.0w
排名: 2
上一篇: 归并排序--java实现
下一篇:Guava Graph 深度/广度遍历
标签: 图算法、面试题
隐藏