广度优先搜索与深度优先搜索的 java 实现

1.广度优先搜索

---

这个示例来解决某个定点到其他所有顶点的无权最短路径长度，并将每一步的队列变化输出。

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Test {

    static int [] distance;

    //有向图的邻接矩阵表示法
    static int [] [] matrix = {
            {1,1,0,1,0,0,0},
            {0,1,0,1,1,0,0},
            {1,0,1,0,0,1,0},
            {0,0,1,1,1,1,1},
            {0,0,0,0,1,0,1},
            {0,0,0,0,0,1,0},
            {0,0,0,0,0,1,1} };

    static void print( Queue<Integer> queue ) {
        System.out.println(Arrays.toString(queue.toArray()));
    }

    //广度优先搜索
    static void bfs(int s) {
        Queue<Integer> q = new LinkedList<>();

        //起点进队
        q.offer(s);
        distance[s] = 0;

        print(q);

        //只要队列不为空，而且 v 可到 i ，而且 i 点从未访问（很关键，用 distance[i] == -1 表示）
        //distance[i] 就等于 distance[v] + 1
        //并使 i 进队，每一步的队列变化将在输出中显示
        while( !q.isEmpty() ) {
            int v = q.poll();

            for( int i = 0; i < 7; i++) 
                if( matrix[v][i] == 1 && distance[i] == -1 && i != v) {
                    distance[i] = distance[v] + 1;
                    q.offer(i);
                }

            print(q);
        }
    }

    public static void main( String [] args) {
        //初始化距离均为-1
        distance = new int [7];
        for( int i = 0; i < 7; i++) 
            distance[i] = -1;

        //测试点v2
        bfs(2);
        System.out.println("该点到各点最短距离：" + Arrays.toString(distance));
    }
}

输出

[2]
[0, 5]
[5, 1, 3]
[1, 3]
[3, 4]
[4, 6]
[6]
[]
该点到各点最短距离：[1, 2, 0, 2, 3, 1, 3]

---

2.深度优先搜索

深度优先相比广度优先搜索，更容易理解，只需简单递归，这里仅列其伪代码。

void dfs(Vertice v) {
        v.visit = true;
        for each Vertice w adjacent to v
            if ( !w.visit )
                dfs(w);
    }

3.分析

时间复杂度均为O（V+E）。