图论之宽度优先遍历

CSDN

package com.zhang.reflection.面试.算法模版.图.遍历;
import java.util.*;
/**
 * 图的宽度优先遍历
 * 利用队列实现，从源节点开始依次按照宽度进队列，然后弹出，每弹出一个点，
 * 把该节点所有没有进过队列的邻接节点放入队列，直到
 * 队列为空。
 */
public class bfs {
    //图
    static class Graph{
        //点集<编号，实际的点>
        public HashMap<Integer,Node> nodes;
        //边集
        public HashSet<Edge> edges;
        public Graph(){
            nodes=new HashMap<>();
            edges=new HashSet<>();
        }
    }
    //点
    static class Node{
        //点上的值
        public int value;
        //点的入度
        public int in;
        //点的出度
        public int out;
        //相邻节点集,以该节点为起点
        public ArrayList<Node> nexts;
        //相邻边集，以该节点为起点
        public ArrayList<Edge> edges;
        public Node(int value){
            this.value=value;
            in=0;
            out=0;
            nexts=new ArrayList<>();
            edges=new ArrayList<>();
        }
    }
    //边
    static class Edge{
        //边得权值
        public int weight;
        //边的起点
        public Node from;
        //边的终点
        public Node to;
        public Edge(int weight, Node from, Node to){
            this.weight=weight;
            this.from=from;
            this.to=to;
        }
    }
    //根据矩阵创建出图
    //matrix二维矩阵:matrix[i][0]表示起点,matrix[i][1]表示终点,matrix[i][2]表示权值;
    public static Graph createGraph(Integer[][] matrix){
        Graph graph=new Graph();
        for(int i=0;i<matrix.length;i++){
            Integer from=matrix[i][0];
            Integer to=matrix[i][1];
            Integer weight=matrix[i][2];
            if(!graph.nodes.containsKey(from)){
                graph.nodes.put(from,new Node(from));
            }
            if(!graph.nodes.containsKey(to)){
                graph.nodes.put(to,new Node(to));
            }
            Node fromNode=graph.nodes.get(from);
            Node toNode=graph.nodes.get(to);
            Edge newEdge=new Edge(weight,fromNode,toNode);
            fromNode.nexts.add(toNode);
            fromNode.out++;
            toNode.in++;
            fromNode.edges.add(newEdge);
            graph.edges.add(newEdge);
        }
        return graph;
    }
    //bfs宽度优先遍历
    //从一个点出发，使用Node就可以
    public static void bfs(Node node){
        if(node==null){
            return ;
        }
        //将点放入队列
        Deque<Node> queue=new LinkedList<>();
        //记录某个点是否已经放入过队列
        HashSet<Node> set=new HashSet<>();
        queue.offer(node);
        set.add(node);
        //队列不为空就继续
        while(!queue.isEmpty()){
            Node cur=queue.poll();
            //这里可以换为自己的具体处理行为，细节定制
            //广度优先遍历是一个点出来的时候处理
            System.out.println(cur.value);
            for(Node next:cur.nexts){
                //没有放入过队列才放入
                if(!set.contains(next)){
                    set.add(next);
                    queue.offer(next);
                }
            }
        }
    }
}