Graph

2015-02-06

#无向图的判环

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

算法步骤：

采用DFS，从任意一点开始遍历图
使用visited标记已经走过的路径
由于对于无向图，当前节点与相邻节点必然存在双向路径，使用parent标记父亲节点
遍历当前节点的所有相邻节点adj
如果当相邻节点adj不是父亲节点，且已经访问过，则说明存在环，直接返回存在环。
否则递归遍历相邻节点

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标记所有走过的节点。

#树的判定

树是特殊的无向图，其判定条件如下：

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

#有向图的判环

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

算法步骤：

采用DFS，从任意一点开始遍历图
使用visited标记已经走过的路径
使用数组path标记当前走的路径
遍历当前节点的相邻节点adj
当adj出现在路径中，则说明存在环
否则递归遍历

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

#有向图的连通性

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

算法步骤：

从任意一点p开始，检查其是否能通往其它所有点
将图上的所有连线颠倒

采用有向图判环方法，从p开始，检查其是否能通往其它所有点

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的节点表明当前工作可以开始

使用队列保存所有入度为0的节点
每次从队列中取出节点，进行访问后，扩展相邻的节点，修改相邻节点的入度值，如果为0则加入队列

如果未遍历为所有节点，则说明出现环(由于环内节点入度都大于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)保存队列

##深度优先遍历

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

同有向图判环方法类似，遍历整个图
当所有相邻节点访问完后，将节点加入待访问的最后。

逆序输出访问节点

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，终点的入度比出度少1。

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

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

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