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

二分图(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暗示边的个数

另一种是贪心选择。