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;
            }
        }
    }