1. 基本概念 2. 表示方法 3. 问题类别 联通分量 环 最短路径 A-B的最短路径 走遍前部节点最短路径 无权无向图 广度搜索： 状态（i, mask, dist） 表示 当前节点i，走过的mask，所走过的距离 初始时，每个位置都放入队列 m ...
1. 基本概念 2. 表示方法 3. 问题类别 联通分量 环 最短路径 A-B的最短路径 走遍前部节点最短路径 无权无向图 广度搜索： 状态（i, mask, dist） 表示 当前节点i，走过的mask，所走过的距离 初始时，每个位置都放入队列 m ...
二分图 ` Map> graph = new HashMap();; int [] colors = new int[ ]; for (int i = 1; i <=n ; i++) { if(colors[i]==0 && !canColor(i,1)){ return false; ...
图的表示法 邻接矩阵 邻接列表 > 邻接矩阵比较消耗内存，不适合使用稀疏情况 节点 ` public class Node { public int value; public int in; public int out; public ArrayList edges; } ...
拓扑排序 拓扑排序(Topological Order)是指，将一个有向无环图(Directed Acyclic Graph简称DAG)进行排序进而得到一个有序的线性序列。 通俗的讲就是所有的有向边均从排在前面的元素指向排在后面的元素，从而确定每个顶点的先后顺序。 能进行拓扑排序的前提条件： 有向图 有入度in为0的结点 没有环 ...
最小生成树 假设图中有N个结点，最小生成树，就是在图中找（N-1）条边，把所有的结点连接起来，同时要保证边的权重和最小 kruskal算法 将边按权重排序，并且认为所有的点都是孤立的集合 找到权重最小的边，把边的两个点并为一个集合 找到权重第二小的边，判断边的两个点是否已经是同一个集合 是，忽略这个边 否，将边的两 ...