參考：
https://blog.csdn.net/a60782885/article/details/72655041
https://blog.csdn.net/yafeichang/article/details/53888866
1. 無向圖、有向圖、有權圖、有向有權圖
2. 表示方式：鄰接矩陣、邊的數(shù)組、鄰接鏈表
3. 遍歷：dfs——對應stack，先進后出。
bfs——對應queue，先進先出
public class Graph {
private List<Integer>[] adj; // 鄰接表
private int V; // 頂點數(shù)目
private int E; // 邊的數(shù)目
}
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：從一個點開始遍歷，遍歷記錄點的數(shù)目，如果最后的數(shù)目等于點數(shù)，則連通；小于則不連通
- 法2：floyed算法
時間復雜度：O(N3)
算法實現(xiàn)：把相連的兩點設為dis[i][j]=true，不相連的兩點設為dis[i][j]=flase，用Floyed算法的變形：
floyd算法本來用以求圖中任意兩點間的最短路徑，大體思路是：依次以每個點k作為i--->j的中間節(jié)點，求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. 兩個點是否連通：
- 記錄屬于哪個連通塊【用一個數(shù)組記錄】。判斷兩個點的數(shù)組id是否相同
- 或者：從指定一個點出發(fā)，進行一次遍歷，能夠從這個點出發(fā)到達的點就與起點連通的。這樣就可以求出這個頂點和其他頂點的連通情況。所以只要把每個頂點作為出發(fā)點都進行一次遍歷，就能知道任意兩個頂點之間是否有路存在。
6. 圖是否有環(huán)。
記錄前一個節(jié)點。如果在dfs過程中，下一個點被遍歷過且不是它的前一個節(jié)點，則說明有環(huán)
if(!marked[w])
dfs(g, w, v);
else if(w != u)
hasCycle = true;
7. 最小環(huán)
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著色優(yōu)化：
若圖G是可平面圖,則它的色數(shù)不超過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){ //遍歷每一個節(jié)點 vi
for(j = 1; j <= cl ;++j){ //對vi 節(jié)點嘗試使用顏色 j來著色(1<= j <= cl)
if(!isCollsion(a,c,i,j)){ // 若vi 著顏色j ，且與已經著色的節(jié)點(v0 - v(i-1))不發(fā)生任何著色沖突的話，就將vi著色為j
c[i] = j;
break;
}
if(c[i] == -1){ //若顏色庫中所有顏色都不能為vi節(jié)點 著色的話，就增加一種顏色,cl++;并將 該顏色賦予節(jié)點i
c[i] = ++cl;
}
}
}
