参考：
https://blog.csdn.net/a60782885/article/details/72655041
https://blog.csdn.net/yafeichang/article/details/53888866
1. 无向图、有向图、有权图、有向有权图
2. 表示方式：邻接矩阵、边的数组、邻接链表
3. 遍历：dfs——对应stack，先进后出。
bfs——对应queue，先进先出
public class Graph {
private List<Integer>[] adj; // 邻接表
private int V; // 顶点数目
private int E; // 边的数目
}
public void main(){
for(int i=0;i<g.verticles;i++){
if(!mark[i]){
dfs(g,i);
count++;
}
}
}
void dfs(Graph g,int start){
mark[start]=true;
count++;
for(Integer i:adj[start]){
if(!mark[i]){
dfs(g,i);
}
}
}
void bfs(Graph g,int start){
mark[start]=true;
count++;
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(start);
while(queue.size()>0){
int temp = queue.pop();
for(Integer i:adj[start]){
if(!mark[i]){
mark[i]=true;
count++;
queue.add(i);
}
}
}
}
4. 是否是连通图：
- 法1：从一个点开始遍历，遍历记录点的数目，如果最后的数目等于点数，则连通；小于则不连通
- 法2：floyed算法
时间复杂度：O(N3)
算法实现：把相连的两点设为dis[i][j]=true，不相连的两点设为dis[i][j]=flase，用Floyed算法的变形：
floyd算法本来用以求图中任意两点间的最短路径，大体思路是：依次以每个点k作为i--->j的中间节点，求d(i,j) = min(d(i,j),d(i,k)+d(k,j))
如果用floyd算法判断任意两个点的连通性？
可以直接用上面的算法，但是可以将加法和min操作转为位运算。
d(i,j) = d(i,j) | (d(i,k) & d(k,j))
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=dis[i][j]||(dis[i][k]&&dis[k][j]);
最后如果dis[i][j]=true的话，表示两点连通。
有向图和无向图都适用。
5. 两个点是否连通：
- 记录属于哪个连通块【用一个数组记录】。判断两个点的数组id是否相同
- 或者：从指定一个点出发，进行一次遍历，能够从这个点出发到达的点就与起点连通的。这样就可以求出这个顶点和其他顶点的连通情况。所以只要把每个顶点作为出发点都进行一次遍历，就能知道任意两个顶点之间是否有路存在。
6. 图是否有环。
记录前一个节点。如果在dfs过程中，下一个点被遍历过且不是它的前一个节点，则说明有环
if(!marked[w])
dfs(g, w, v);
else if(w != u)
hasCycle = true;
7. 最小环
https://blog.csdn.net/qq_34731703/article/details/54729244
https://blog.csdn.net/Olga_jing/article/details/49928443
https://blog.csdn.net/cax1165/article/details/51811902
floyed算法图解：
https://blog.csdn.net/qq_34374664/article/details/52261672
8. 二分图
https://blog.csdn.net/yafeichang/article/details/53888866
可以被二着色的图
思路：dfs的同时，对访问点的连接点标成不同于当前点的颜色，当访问到之前访问的点，且两个连接的点颜色相同时，说明这不是二分图。
private void dfs(Graph g, int v) {
marked[v] = true;
for(int w : g.adj(v)) {
if(!marked[w]) {
color[w] = !color[v];
dfs(g, w);
} else if(color[w] == color[v])
isTwoColorable = false;
}
}
9.图的m着色问题
- 图的m着色判定
- 图的m着色优化：
若图G是可平面图,则它的色数不超过4色(4色定理).
4色定理的应用:在一个平面或球面上的任何地图能够只用4种颜色来着色可使得相邻的国家在地图上着有不同颜色。
思路1：贪心。
任选一顶点着色1，在图中尽可能多的用颜色1着色；
当不能用颜色1着色时，转用颜色2将未着色的顶点尽可能多的着色···
直到所有顶点都被着色停止。
https://blog.csdn.net/lime1991/article/details/47805881
（有点麻烦。每次都要判断是否还有未着色点）
思路2：如果颜色库中的所有颜色都不能为1个点着色时，就新增一种颜色，然后对下一个点依旧从第一个颜色开始验证
https://www.cnblogs.com/compilers/p/5480640.html
for(i = 0; i < N;++i){ //遍历每一个节点 vi
for(j = 1; j <= cl ;++j){ //对vi 节点尝试使用颜色 j来着色(1<= j <= cl)
if(!isCollsion(a,c,i,j)){ // 若vi 着颜色j ，且与已经着色的节点(v0 - v(i-1))不发生任何着色冲突的话，就将vi着色为j
c[i] = j;
break;
}
if(c[i] == -1){ //若颜色库中所有颜色都不能为vi节点 着色的话，就增加一种颜色,cl++;并将 该颜色赋予节点i
c[i] = ++cl;
}
}
}
