图的简单介绍

1、简介

图的存储方式

• 邻接表
• 邻接矩阵
• 其他自定义结构

对于不同结构的应对方式

掌握一种结构的算法，出现其他结构时，想办法转成自己掌握的结构。

模板结构

——点集 + 边集

//图结构
public class Graph{
    //图中每个点的编号和对应的点结构
    public HashMap<Integer,Node> nodes;
    //图中的边集合
    public HashSet<Edge> edges;
    public Graph(){
        nodes = new HashMap<>();
        edges = new HashSet<>();
    }
}
public 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<>();
    }
}
public 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;
    }
}

2、图的遍历

a、图的宽度优先遍历

思路

1. 利用队列和一个Set集合（避免重复），从源节点开始按照宽度进队列和Set，然后弹出
2. 每弹出一个点，将该节点所有没在Set中的邻接节点放入Set和队列
3. 重复2直至队列为空

实现代码

//从源节点node开始，进行宽度优先遍历
public static void bfs(Node node){
    if(node == null){
        return;
    }
    //准备一个队列和一个Set集合
    Queue<Node> queue = new LinkedList<Node>();
    HashSet<Node> set = new HashSet<Node>();
    //先将源节点加入队列和Set集合
    queue.offer(node);
    set.add(node);
    //开始循环直至队列为空
    while(!queue.isEmpty()){
        //拿到出队节点
        Node cur = queue.poll();
        //处理（可以是打印或其他的处理）
        System.out.print(cur.value);
        //遍历当前节点的邻接节点
        for(Node next : cur.nexts){
            //如果这个节点不在Set集合中，则加入
            if(!set.contains(next)){
                set.add(next);
                queue.offer(next);
            }
        }
    }
}

b、图的广度优先遍历

思路

1. 利用栈和Set集合（避免重复），从源节点开始，将节点按照深度放入栈和Set集合，然后弹出
2. 每弹出一个节点，将该节点的一个没有在Set集合中的邻接点放入Set和栈
3. 重复2直至栈为空

实现代码

//从源节点node开始，进行深度优先遍历
public static void dfs(Node node){
    if(Node == null){
        return;
    }
    //准备一个栈和一个Set集合
    Stack<Node> stack = new Stack<>();
    HashSet<Node> set = new HashSet<>();
    //先将源节点放入栈和Set集合
    stack.add(node);
    set.add(node);
    //处理源节点（可以是打印或其他处理）
    System.out.print(node.value);
    //循环直至栈空
    while(!stack.isEmpty()){
        //拿到当前弹出的节点
        Node cur = stack.pop();
        //遍历当前节点的邻接节点
        for(Node next : cur.nexts){
            //如果当前邻接节点不在Set集合中则加入
            if(!set.contains(next)){
                set.add(next);
                //在将邻接节点加入栈前，先把当前节点入栈
                stack.push(cur);
                stack.push(next);
                //处理当前邻接节点
                System.out.print(next.value);
                //找到一个就直接退出遍历，接着找这个邻接节点的邻接节点
                break;
            }
        }
    }
}