[算法] 学习无向图

本文是学习http://algs4.cs.princeton.edu/41graph/的吐槽和体会。

一点吐槽

一开始对GraphClient.java中numberOfSelfLoops函数进行count/2不解，翻回Graph.java，看看addEdge函数才明白，合着对自循环连接，adj里面加两次。这么干有什么好处么？！！

再后来看Cycle.java，对hasParallelEdges函数又不解，仔细想想Graph.java不但接受addEdge(1,23)和addEdge(23, 1)，对执行多次addEdge(1,23)也不拒绝。一个无向图这么弄，对么？算不算检查不严格呀？！！

理解Cycle.java

示例代码：

public static void main(String[] args) {
  Graph G = new Graph(4);
  G.addEdge(0, 1);
  G.addEdge(1, 2);
  G.addEdge(1, 3);
  G.addEdge(2, 3);    
  Cycle finder = new Cycle(G);
  if (finder.hasCycle()) {
    for (int v : finder.cycle()) {
      StdOut.print(v + " ");
    }
    StdOut.println();
  }
  else {
    StdOut.println("Graph is acyclic");
  }
}

dfs搜索：

|上一节点u|当前节点v|下一节点w|注解 |—– |-1|0|1|节点1没有标注，嵌套dfs |0|1|3|节点3没有标注，嵌套dfs |1|3|2|节点2没有标注，嵌套dfs |3|2|1|节点1已标注，发现cycle，创建栈，依次：

(在for循环中)push 2
(在for循环中)push 3
push 1
push 2说白了就是当发现下一节点w已经标注，那就返回去找w到v的路径，然后凑上w和v，就是一个环路。

理解Bipartite.java

二分图又称作二部图、两偶图，是图论中的一种特殊模型。设G=(V,E）是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B），并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集（iin A,j in B），则称图G为一个二分图。

简而言之，就是顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集。

Bipartite.java的控制流与CC.java差不多。设定图中节点为红黑两种颜色，为了使相邻节点不同颜色，dfs时下一节点颜色为当前节点反色。当遇到环路时，如果环路节点数为奇数个（下一节点已标注且颜色与当前节点相同），则该图非二分图。

理解Bridge.java

桥（割边cut-edge）是一个边，当其被删除时连通组件个数会增多。同样道理，一个边仅没有被任何环路包含时才是一个桥。

示例代码：

public static void main(String[] args) {
        Graph G = new Graph(5);
        G.addEdge(0, 1);
        G.addEdge(1, 3);
        G.addEdge(1, 2);
        G.addEdge(2, 3);
        G.addEdge(3, 4);        
  StdOut.println(G);

  Bridge bridge = new Bridge(G);
  StdOut.println("Edge connected components = " + bridge.components());
}

dfs搜索： dfs过程中，发现环路后整个环路上所有节点low值降成环路中第一个处理节点的pre值。下一个节点pre值与最终low值一致的话，当前节点和下一节点之间的边为桥。

注：对于连接组件的第一个处理节点，Cycle.java中dfs函数的u参数为-1，而Bridge.java中的dfs函数的u参数为当前节点v。

输出日志：

5 vertices, 5 edges 
0: 1 
1: 2 3 0 
2: 3 1 
3: 4 2 1 
4: 3 

3-4 is a bridge
0-1 is a bridge
Edge connected components = 3

理解Biconnected.java

关节点（articulation vertex，又称割点cutvertex）是一个节点，当其被删除时连通组件个数会增多。当没有关节点时，图为双连通图。

示例代码：

public static void main(String[] args) {
  Graph G = new Graph(5);
  G.addEdge(0, 1);
  G.addEdge(1, 3);
  G.addEdge(1, 2);
  G.addEdge(2, 3);
  G.addEdge(3, 4);
  StdOut.println(G);

  Biconnected bic = new Biconnected(G);

  // print out articulation points
  StdOut.println();
  StdOut.println("Articulation points");
  StdOut.println("-------------------");
  for (int v = 0; v < G.V(); v++)
    if (bic.isArticulation(v)) StdOut.println(v);
}

dfs搜索： dfs过程中，发现环路后整个环路上所有节点low值降成环路中第一个处理节点的pre值。当前节点pre值小于等于下一节点最终low值，且当前节点非连接组件第一个处理节点时，当前节点即为割点。

注：对于连接组件的第一个处理节点，Cycle.java中dfs函数的u参数为-1，而Biconnected.java中的dfs函数的u参数为当前节点v。

输出日志：

5 vertices, 5 edges 
0: 1 
1: 2 3 0 
2: 3 1 
3: 4 2 1 
4: 3 


Articulation points
-------------------
1
3

理解EulerianCycle.java

通过图（无向图或有向图）中所有边且每边仅通过一次通路称为欧拉通路（Eulerian trail，Eulerianpath），相应的回路称为欧拉回路（ Eulerian circuit，Euleriancycle）。具有欧拉回路的图称为欧拉图（EulerGraph），具有欧拉通路而无欧拉回路的图称为半欧拉图（Semi-Eulerian）。

|图论起源于18世纪，1736年瑞士数学家欧拉（Euler）发表了图论的第一篇论文“哥尼斯堡七桥问题”。在当时的哥尼斯堡城有一条横贯全市的普雷格尔河，河中的两个岛与两岸用七座桥连结起来。当时那里的居民热衷于一个难题：有游人怎样不重复地走遍七桥，最后回到出发点。为了解决这个问题，欧拉用A,B,C,D4个字母代替陆地，作为4个顶点，将联结两块陆地的桥用相应的线段表示，于是哥尼斯堡七桥问题就变成了图中，是否存在经过每条边一次且仅一次，经过所有的顶点的回路问题了。欧拉在论文中指出，这样的回路是不存在的。|

无向连通图G含有欧拉通路，当且仅当G有零个或两个奇数度的结点；无向连通图G是欧拉图，当且仅当G不含奇数度结点(G的所有结点度数为偶数)。

EulerianCycle.java判断当某个节点度为奇数，则不是欧拉图。否则任选一点度大于零的点做起点，记录路径是否走过，一点接一点直到当前点对相邻点没有未走路径为止。最后判断所走路径上节点数是否为图所有节点个数+1，如不等则非欧拉图。（感觉即使是欧拉图靠贪婪查找也不确保能获得正确路径。）

平面图

一个图是片面的，指其画在平面时边没有交叉。Hopcroft-Tarjan算法基于dfs能在线性时间内判断图是否为平面的。

汉密尔顿图

通过图（无向图或有向图）中所有节点且每节点仅通过一次的通路称为哈密顿通路（Hamiltonian path，Traceablepath），相应的回路称作汉密尔顿回路（Hamiltonian cycle）。

美国图论数学家奥勒在1960年给出了一个图是哈密尔顿图的充分条件：对于顶点个数大于2的图，如果图中任意两点度的和大于或等于顶点总数，那这个图一定是哈密尔顿图。寻找哈密顿路径是一个典型的NP-完全问题。