Graph

#无向图的判环

思想:如果一个点被访问两次,则说明存在两条不同的路径到达该点。将这两条路径连接起来,则必然存在环。

算法步骤:

  1. 采用DFS,从任意一点开始遍历图
  2. 使用visited标记已经走过的路径
  3. 由于对于无向图,当前节点与相邻节点必然存在双向路径,使用parent标记父亲节点
  4. 遍历当前节点的所有相邻节点adj
    如果当相邻节点adj不是父亲节点,且已经访问过,则说明存在环,直接返回存在环。
    否则递归遍历相邻节点
1
def isUndirectedCycleDFS(graph, node, visited, parent):
    if visited[node]:
        return false
    visited[node] = true
    for adj in graph[node].adjs:
        if adj != parent and visited[adj]: #此点已经被访问,且不是父亲节点
            return false
        if !isUndirectedCycleDFS(graph, adj, visited, node): #子节点存在环,直接返回
            return false
    return true

#无向图的连通性

思想:从任意一点开始,可以完整遍历图中所有节点。为了避免图中出现环而导致无限循环,使用visited标记所有走过的节点。

#树的判定

树是特殊的无向图,其判定条件如下:

  1. 树上所有节点是联通的
  2. 到任意一点只存在唯一路径 => 树上不存在环
  3. 两点之间只存在唯一路径

#有向图的判环

思想:记录从起点开始的访问路径,有向图存在环当且仅当:当前节点访问的下一个相邻节点出现在访问路径中。

算法步骤:

  1. 采用DFS,从任意一点开始遍历图
  2. 使用visited标记已经走过的路径
  3. 使用数组path标记当前走的路径
  4. 遍历当前节点的相邻节点adj
    当adj出现在路径中,则说明存在环
    否则递归遍历
1
def isDirectedCycleDFS(graph, node, visited, path):
    if visited[node]:
        return true
    visited[node] = true
    path[node] = true
    for adj in graph[node].adjs:
        if path[adj] or !isDirectedCycleDFS(graph, adj, visited, path):
            return false
    path[node] = false
    return true

#有向图的连通性

思想:对于任意一个点,当它能通往图上其它所有点,且图上其它所有点能到达该点则说明图是联通的

算法步骤:

  1. 从任意一点p开始,检查其是否能通往其它所有点
  2. 将图上的所有连线颠倒
  3. 采用有向图判环方法,从p开始,检查其是否能通往其它所有点
    1
    def isDirectedConnected(graph):
        init visited array to false
        traverse(graph, 0, visited)
        for flag in visited: #检查是否可达其它所有点
            if !flag:
                return fasle
       
        reversed_graph = reverseGraph(graph) #将图中连线颠倒
       
        init visited array to false
        traverse(reversed_graph, 0, visited)
        for flag in visited: #检查是否可达其它所有点
            if !flag:
                return fasle
        return true

#拓扑排序

##广度优先遍历

思想: 入度为0的节点表明当前工作可以开始

  1. 使用队列保存所有入度为0的节点
  2. 每次从队列中取出节点,进行访问后,扩展相邻的节点,修改相邻节点的入度值,如果为0则加入队列
  3. 如果未遍历为所有节点,则说明出现环(由于环内节点入度都大于0)。
    1
    for node in graph:
        if node not in inCnt:
            inCnt[node] = 1
        for adj in node.adjs:
            inCnt[adj] += 1
    for node, val in inCnt:
        if val == 0:

分析: 可以一边遍历一边输出结果,需要O(n)保存visited,O(n)保存入度,O(n)保存队列

##深度优先遍历

思想:当一个节点所有相邻节点访问完成后,此节点可以放在工程最后执行

  1. 同有向图判环方法类似,遍历整个图
  2. 当所有相邻节点访问完后,将节点加入待访问的最后。
  3. 逆序输出访问节点
    1
    def dfs(self, topo, path, visited, node):
        if node in visited:
            return True
        visited.add(node)
        path.add(node)
        for neigh in node.neighbors:
            if neigh in path:
                return False
            if neigh not in visited:
                if not self.dfs(topo, path, visited, neigh):
                    return False
        topo.append(node)
        path.remove(node)
        return True
    
    def topSort(self, graph):
        path, visited, topo = set(), set(), []
        for node in graph:
            if not self.dfs(topo, path, visited, node):
                throw DETECT_CYCLE
        topo.reverse()
        return topo

分析:在最后才能输出结果,需要O(n)保存Path,O(n)保存visited, O(n)保存最后结果

#欧拉回路

##无向图
条件是:

  1. 所有顶点的度为偶数。
  2. 图是联通的
    对于欧拉路径,起点和终点可以为奇数,其它顶点都为偶数
    打印欧拉回路:优先访问度为偶数的顶点,当不存在时才访问度为奇数的顶点

##有向图
条件是:

  1. 所有定点的入度等于出度
  2. 图是联通的
    对于欧拉路径,起点的入度比出度多1,终点的入度比出度少1。

#有向图的最短路径
设有V个顶点,E条边

  1. 无环图
    使用拓扑排序后,依次更新,复杂度O(V+E)
  2. 有环,无负边
    Dijkstra, 使用优先队列,每次从队首取出距离最近的顶点,O(E+VlgV)
  3. 有环,有负边
    BellFord, DP,从底向上计算一个顶点到经过至多i条边后到其他顶点的距离。O(V*E)

http://www.cnblogs.com/Ixia/p/3917675.html
邻接矩阵表示法