图算法

数据结构

深度优先（DFS）

class graph:
    def __init__(self, gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict
# Check for the visisted and unvisited nodes
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited
gdict = {"a": {"b", "c"},
         "b": {"a", "d"},
         "c": {"a", "d"},
         "d": {"e"},
         "e": {"a"}
         }
dfs(gdict, 'a')

广度优先（BFS）

import collections
class graph:
    def __init__(self,gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict
def bfs(graph,startnode):
    seen,queue = {startnode}, collections.deque([startnode])
    while queue:
        vertex = queue.popleft()
        print(vertex)
        for node in graph[vertex]:
            if node not in seen:
                seen.add(node)
                queue.append(node)