本篇主要涉及到图论的基本算法，不包含有关最大流的内容。图论的大部分算法都是由性质或推论得出来的，想朴素想出来确实不容易。

二分图(Is-Bipartite)

一个图的所有顶点可以划分成两个子集，使所有的边的入度和出度顶点分别在这两个子集中。

这个问题可以转换为上篇提到过的图的着色问题，只要看图是否能着2个颜色就行了。当然，可以回溯解决这个问题，不过对于着2个颜色可以BFS解决。

同样，一维数组colors表示节点已着的颜色。

伪代码：
IS-BIPARTITE(g,colors)
  let queue be new Queue
  colors[0] = 1
  queue.push(0)
  while queue.empty() == false
    let v = queue.top()
    queue.pop()
    for i equal to every vertex in g
      if colors[i] == 0
        colors[i] = 3 - colors[v]
        queue.push(i)
      else if colors[i] == colors[v]
        return false
    end
  end
  return true

时间复杂度:Θ(V+E)，V表示顶点的个数，E表示边的个数

DFS改良(DFS-Improve)

上篇文章提到过，搜索解空间是树形的，也就是在说BFS和DFS。那么在对图进行BFS和DFS有什么区别呢，这个问题要从解空间角度去理解。对图进行BFS的解空间是一颗树，可叫广度优先树。而DFS是多棵树构成的森林，可叫深度优先森林。

这里要对DFS进行小小的改良，它的性质会对解多个问题会很有帮助。原版DFS搜索的时候，会先遍历本顶点，再递归遍历临接的顶点。DFS改良希望能先递归遍历临接的顶点，再遍历本顶点，并且按遍历顺序逆序存储起来。

伪代码：
DFS-IMPROVE(v,visited,stack)
  visited[v] = true
  for i equal to every vertex adjacent to v
    if visited[i] == false
      DFS-IMPROVE(i,visited,stack)
  end
  stack.push(v)

这个改良版DFS有个很有用的性质就是，对于两个顶点A、B，存在A到B的路径，而不存在B到A的路径，则从记录的顺序中取出的时候，一定会先取出顶点A，再取出顶点B。以下为这个性质的证明。

假设：有两个顶点A和B，存在路径从A到B，不存在路径从B到A。

证明：分为两种情况，情况一，先搜索到A顶点，情况二，先搜索到B顶点。对于情况一，由命题可得，A一定存储在B之后，那么取出时先取出的是顶点A。对于情况二，先搜索到B顶点，由于B顶点搜索不到A顶点，则A一定存储在B之后，那么取出时仍先取出的是顶点A，命题得证。

DFS改良性质：对于两个顶点A、B，存在A到B的路径，而不存在B到A的路径，则从记录的顺序中取出的时候，一定会先取出顶点A，再取出顶点B。

欧拉回路(Eulerian-Path-And-Circuit)

在无向图中，欧拉路径定义为，一条路径经过所有的边，每个边只经过一次。欧拉回路定义为，存在一条欧拉路径且路径的起点和终点为同一个顶点。可以看到只有连通图才能有欧拉回路和欧拉路径。

这个算法很巧。如果一条路径要经过一个顶点，本质是从一条边到达一个顶点，然后从这个顶点通过另一条边出去。欧拉回路就是要求路径要经过所有的点，起点和终点还都是同一个顶点。那么就等价于要求所有顶点连接的边是2个。实际上，路径还可以经过顶点多次，那么就等价于要求所有顶点连接的边是偶数个。欧拉路径的要求就等价于所有顶点连接的边是偶数个，除了起点和终点两个顶点可以是奇数个。

先判断图是否是连通图。返回0代表没有欧拉回路或者欧拉路径，返回1代表有欧拉路径，返回2代表有欧拉回路。

伪代码：
EULERIAN-PATH-AND-CIRCUIT(g)
  if isConnected(g) == false
    return 0
  let odd = 0
  for v equal to every vertex in g
    if v has not even edge 
      odd = odd + 1
  end
  if odd > 2
    returon 0
  if odd == 1
    return 1
  if odd == 0
    return 2

时间复杂度:Θ(V+E)，V表示顶点的个数，E表示边的个数

拓扑排序(Topological-Sorting)

将一张有向无环图的顶点排序，排序规则是所有边的入度顶点要在出度顶点之前。可以看到，无向和有环图都不存在拓扑排序，并且拓扑排序可能存在多种解。

拓扑排序有两种解法，一种是从搜索角度。

如果我能保障先递归遍历临接的顶点，再遍历本顶点的话，那么遍历的顺序的逆序就是一个拓扑排序。那么就可以直接用DFS改良求解出拓扑排序。

伪代码：
TOPOLOGICAL-SORTING-DFS(g)
  let visited be new Array
  let result be new Array
  let stack be new Stack
  for v equal to every vertex in g
    if visited[v] == false
      DFS-IMPROVE(v,visited,stack)
  end
  while stack.empty() == false
      result.append(stack.top())
      stack.pop()
  end
  return result

时间复杂度:Θ(V+E)，V表示顶点的个数，E表示边的个数

另一种是贪心选择。

直觉上，既然要所有边的出度顶点在入度顶点之前，可以从入度和出度角度来解决问题。可以让入度最小的排序在前，也可以让出度最大的排序在后，排序后，这个顶点的边都不会再影响问题了，可以去掉。去掉后再重新加入新的顶点，直到加入所有顶点。

这个问题还有个隐含条件，挑选出、入度最小的顶点就等价于挑选出、入度为0的顶点。这是因为图必须是无环图，所以肯定存在出、入度为0的顶点，那么出、入度最小的顶点就是出、入度为0的顶点。

直觉上这是一个可行的策略，细想一下，按出度最大排序和按入度为零排序是否等价。实际上是不等价的，按入度为零排序，如果出现了多个入度为零的顶点，这多个顶点排序的顺序是无关的，可以任意排序。而按出度最大排序，出现了多个入度最大的顶点，这多个顶点排序是有关的，不能任意排序。所以，只能按入度为零排序。实际上，这个想法就是贪心选择。下面以挑选入度为零的边作为贪心选择解决问题，同样地，还是先证明这个贪心选择的正确性。

命题：入度为零的顶点v排序在前。

假设：S为图的一个拓扑排序，l为此排序的首个顶点。

证明：如果l=v，则命题得证。如果l不等于v，将l顶点从S中去除，然后加入顶点v得到新的排序S‘。因为S去除l以后l以后的排序没有变，仍为拓扑排序，v入度为零，v前面可以没有顶点，所以S’也为图的一个拓扑排序，命题得证。