note/algorithm/11、图.md

图

1、图的概念

• 由点的集合和边的集合构成
• 虽然存在有向图和无向图的概念，但实际上都可以用有向图来表达
• 边上可能带有权值

  图的表示方法邻接表法、邻接矩阵法等。题目会以各种方式给出图的表达方式，可以将它转化为一种熟悉的表达方式，方便操作。可以将图表示为节点和边的集合，参考下面代码Graph。

public class Graph {
    public Map<Integer, Node> nodes;
    public Set<Edge> edges;

    public Graph() {
        this.nodes = new HashMap<>();
        this.edges = new HashSet<>();
    }
}

public class Node {
    // 节点值
    public int value;
    // 入度
    public int in;
    // 出度
    public int out;
    // 相邻节点
    public List<Node> nexts;
    // 节点的边
    public List<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;
    }
}

### 宽度优先遍历

• 利用队列实现
• 从源节点开始依次按照宽度进队列，然后弹出
• 每弹出一个点，把该节点所有没有进过队列的邻接点放入队列
• 直到队列变空

深度优先遍历

• 利用栈实现
• 从源节点开始把节点按照深度放入栈，然后弹出
• 每弹出一个点，把该节点下一个没有进过栈的邻接点放入栈
• 直到栈变空
  

拓扑排序

  拓扑排序要求有向无环图，拓扑排序结果不唯一，可以用宽度优先遍历和深度优先遍历实现。应用场景有事件安排、编译顺序等

• 在图中找到所有入度为0的点输出
• 把所有入度为0的点在图中删掉，继续找入度为0的点输出，周而复始
• 图的所有点都被删除后，依次输出的顺序就是拓扑排序
  

最小生成树(无向图)

  最小生成树要求无向图，可以使用Kruskal和Prim算法实现，Kruskal和Prim都是贪心算法。

Kruskal算法使用并查集

• 总是从权值最小的边开始考虑，依次考察权值依次变大的边
• 当前的边要么进入最小生成树的集合，要么丢弃
• 如果当前的边进入最小生成树的集合中不会形成环，就要当前边
• 如果当前的边进入最小生成树的集合中会形成环，就不要当前边
• 考察完所有边之后，最小生成树的集合也得到了

Prim算法

• 1）可以从任意节点出发来寻找最小生成树
• 2）某个点加入到被选取的点中后，解锁这个点出发的所有新的边
• 3）在所有解锁的边中选最小的边，然后看看这个边会不会形成环
• 4）如果会，不要当前边，继续考察剩下解锁的边中最小的边，重复3）
• 5）如果不会，要当前边，将该边的指向点加入到被选取的点中，重复2）
• 6）当所有点都被选取，最小生成树就得到了

最短路径算法

  可以使用Dijkstra算法实现最短路径。

迪瑞克斯拉算法(有向、无负权重、可以有环)

1）Dijkstra算法必须指定一个源点 2）生成一个源点到各个点的最小距离表，一开始只有一条记录，即原点到自己的最小距离为0，源点到其他所有点的最小距离都为正无穷大 3）从距离表中拿出没拿过记录里的最小记录，通过这个点发出的边，更新源点到各个点的最小距离表，不断重复这一步 4）源点到所有的点记录如果都被拿过一遍，过程停止，最小距离表得到了

Dijkstral算法优化

  利用加强堆   某个节点最短距离改变时做动态调整