算法_图论_广度优先遍历(Java)

图的广度优先遍历的实现步骤

1. 使用队列，依次记住被访问的顶点。
2. 算法开始时，起始点v0，将其入队。
3. 每次出队时，即访问，然后将正在被访问的顶点的邻接点入队。
4. 当while循环结束时，表明访问完毕，算法结束。

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

/**
 * @author tsh
 */
public class Bfs {
    //初始化邻接矩阵
    static int[][] graph = {
             {0,1,1,0,0,0,0,0},
             {1,0,0,1,1,0,0,0},
             {1,0,0,0,0,1,1,0},
             {0,1,0,0,0,0,0,1},
             {0,1,0,0,0,0,0,1},
             {0,0,1,0,0,0,1,0},
             {0,0,1,0,0,1,0,0},
             {0,0,0,1,1,0,0,0},
    };
    
    //是否访问
    static boolean[] isVisited = new boolean[8];
    
    //队列
    static Queue<Integer> queue = new LinkedList();
    
    //主方法：利用队列来完成广度优先遍历
    public static void main(String[] args) {
        BfsOfQueue();
    }
    
    // 广度优先遍历（入队前判断是否已入过队列）
    public static void BfsOfQueue() {
        queue.add(0); // 遍历起始点0
        int index = 0; // 存储出队的下标
        isVisited[0] = true;
        while(queue.size() != 0) { // 如果队列为空则遍历结束
            index = queue.poll(); // 出栈操作
            System.out.println("v" + index);
            for(int i = 0; i<isVisited.length; i++) {//遍历每个顶点
                if(graph[index][i] == 1 && !isVisited[i]) {//==1表示与此顶点有连线，!isVisited[i]表示此顶点还未访问，则入队
                    queue.add(i);
                    isVisited[i] = true; // 入队时将其设为已访问
                }
            }
        }
    }
}

具体图

程序中的无向图.png

下面实现几个有关图论的常用算法