1. what is graph？

联想一下航班运行轨迹，总是从一个地点到另一个地点。如果将这些地点连接起来，就成了一张航线图，如果你想使用计算机可以理解的方式画出这张图，就很自然地需要使用到Graph这个数据结构。

1.1 图的数据结构（邻接表形式）

假设航班是从LA -----> NYC------>LONDON------>TOKYO

那这些城市就是node，从A---->B的路线关系就是graph中的edge。

所以，对于图，最直接的存储方式就是邻接表。

一般的算法默认传入的也是邻接表的形式

1.2 代码实现

"""
比如上图，0 : [ 1, 4], 1:[0, 3, 4]
literally，使用python中的字典存储表示为key---value的形式
"""

num_nodes = 5
edges = [(0, 1), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (3, 4)]

class Graph():
    def __inti__(self, nodes=None, edges=None):
        if not nodes:
            self.nodes = nodes
        if not edges:
            self.edges = edges
        # data存储的是所有节点可以到达的节点，也就是邻接表
        self.data = [[] for _ in range(nodes)]
        for n1, n2 in edges:
            # print('node1:', n1, 'node2:', n2)
            self.data[n1].append(n2)
            self.data[n2].append(n1)

    def __repr__(self):
        return '\n'.join(
            ['{} : {}'.format(node, nebor) 
             for node, nebor in enumerate(self.data)]
        )

    def __str__(self):
        return self.__repr__()

                       
            

2 对无向图的操作

2.1 增加/删除边

最简单也是最基本的操作就是向邻接表添加/删除边。

    def add_edge(self, edge):
        n1, n2 = edge
        # self.data[i] is  index
        if n1 in self.data[n2] and n2 in self.data[n1]:
            print('existed edge')
            return
        self.data[n1].append(n2)
        self.data[n2].append(n1)
        return n1, n2

    def delete_edge(self, edge):
        n1, n2 = edge
        if n1 not in self.data[n2] and n2 not in self.data[n1]:
            return
        self.data[n1].remove(n2)
        self.data[n2].remove(n1)
        return n1, n2

2.2 图的广度遍历

和之前对树的遍历一致，因为要按照广度遍历，所以要依赖队列，先进先出。

我们期望直到遍历的顺序，所以定义一个bfs_order[   ]来存储图的遍历顺序。

在遍历的过程中，如果遍历过了，就不再需要再次访问，所以建立一个 visited列表来存储已经访问过的节点。

如果想知道每个节点和起始节点的距离（假设目前没有权重表示距离，node之间的距离都为1，使用dist[  ]列表存储距离，同时建立parent[  ] 来表示当前节点是从哪个节点遍历过来的。

所以bfs函数需要传入的参数就是start node。

核心思想就是：不断从队头取出当前节点，遍历其所有相邻节点，将未访问节点加入队尾

    def bfs(self, root):
        quene = deque([root])
        bfs_order = []
        visited = set([root])
        # 存储距离
        dist = [False] * len(self.data)
        # 存储父节点
        parent = [False] * len(self.data)

        dist[root] = 0

        while quene:
            node = quene.popleft()
            bfs_order.append(node)

            for v_node in self.data[node]:
                if v_node not in visited:
                    visited.add(v_node)
                    quene.append(v_node)
                    parent[v_node] = node
                    dist[v_node] = dist[node] + 1

        return bfs_order, parent, dist

2.3 图的连通性

对于无向图，我们说图是 连通的（connected），当且仅当：

从任意一个节点出发，通过图中的边，可以访问到所有其他节点。

所以bfs可以用来检查无向图是否连通。

    def is_connect(self, root):
        if not root:
            print('empty root')
        # root 是任意节点（无向图）
        quene = deque([root])
        visited = set([root])
        bfs_order = []

        while quene:
            node = quene.popleft()
            bfs_order.append(node)
            for v_node in self.data[node]:
                if v_node not in visited:
                    visited.add(v_node)
                    quene.append(v_node)
        print('bfs:', bfs_order)

        return len(visited) == len(self.data)

2.4 图的深度遍历

既然树有深度遍历，那么图也有深度遍历。

但是图和树也有不同之处。对于一颗树，他的数据结构需要root，并且带有左右节点，父节点。树的深度表现为当前节点到根节点的边的多少。

不过图其实没有root，节点之间也有多条路径。图中可能存在环，甚至由许多连通分量组成。（这个在离散数学中有专门讲解，很高兴我不懂离散数学也没有自己的见解）

so 图的深度是相对某一个节点的深度，当选择不同的节点作为‘root’，每个节点的深度也不一样。但是，当我们对图执行 DFS 时，图会被动态地“拉扯”成一棵树结构。
也就是说，DFS 会隐式构造一棵从起点出发的深度优先搜索树。

因此，深度这个概念对于图来说，并不是他的固有属性，而是在DFS 过程中，从起点到某节点所经历的递归层级（调用深度）。

因为深度遍历的思想继承自Tree，所以对于图的深度遍历思想也是一样的：

从根节点出发。不断深入，直到碰到叶子节点无法继续，再回溯到最近的分叉。（但是图是有环的，所以需要一个位置来存放已经访问过的节点，来防止重复访问）

    def dfs(self, root):
        if root is None:
            raise ValueError('empty root')
        visited = set([root])
        dfs_order = [root]
        dfs_depth = [0] * self.nodes
        parent = [-1] * self.nodes  # DFS Tree 的父亲

        def dfs_visit(node):

            for v_node in self.data[node]:
                if v_node not in visited:
                    visited.add(v_node)
                    parent[v_node] = node
                    dfs_order.append(v_node)
                    dfs_depth[v_node] = dfs_depth[node] + 1
                    dfs_visit(v_node)

        dfs_visit(root)

        return dfs_order, dfs_depth

2.5 判断图中是否有环

综上所述，

判断图中是否存在环可以总结为：

访问节点u时，u的邻接表中存在已访问过的节点，且此节点不是u的parent，则图中存在环。

    def has_circle(self, root):
        if root is None:
            raise ValueError('empty input')
        visited = set([root])
        parent = [-1] * self.nodes
        circle = False

        def dfs(root):
            # 未访问的树边
            for v_node in self.data[root]:
                if v_node not in visited:
                    visited.add(v_node)
                    parent[v_node] = root
                    dfs(v_node)
            # 处理非树边
                else:
                    if v_node != parent[root]:
                        circle = True
        dfs(root)

        return circle

3.Weighted Graphs  加权图

前面说明了，引入图的数据结构是因为现生中有非常多这样的情形，比如铁路，比如地图。

但是无向图的使用是比较有限的，更多的还是有向加权图，比如从上海到大版的航线和里程，就可以用有向加权图来表示。

此处要额外提一下，对于图来说，更重要的是边，而不是节点。如果最终想呈现的图想排除孤立节点，那节点就不是图的根本属性。

3.1 加权图的初始化

from collections import defaultdict

class w_graph():
    def __init__(self, nodes=None, edges=None, directed=False, weighted=False):
        self.directed = directed
        self.weighted = weighted
        self.data = defaultdict(list)
        #  key: node, value: dict of neighbor -> weight

        if edges is None:
            raise ValueError('empty edges')

        for node in nodes:
            self.add_node(node)

        for edge in edges:
            self.add_edge(edge)

    def add_node(self, node):
        if node not in self.data:
            self.data[node] = []

    def add_edge(self, edge):
        u, v, w = edge

        if self.weighted:
            self.data[u].append((v, w))
        else:
            self.data[u].append((v))

        if not self.directed:
            if self.weighted:
                self.data[v].append((u, w))
            else:
                self.data[v].append((u))

    def remove_edge(self, edge):
        u, v, w = edge
        if u in self.data:
            if self.weighted:
                self.data[u] = [item for item in self.data[u] if not (item[0] == v and item[1] == w)]
            else:
                self.data[u] = [item for item in self.data[u] if item != v]

        # 如果是无向图，还要删除 v → u
        if not self.directed and v in self.data:
            if self.weighted:
                self.data[v] = [item for item in self.data[v] if not (item[0] == u and item[1] == w)]
            else:
                self.data[v] = [item for item in self.data[v] if item != u]
        """
        attention
        因为edges是tuple结构，不可变（immutable），更符合“边对象固定不变”的语义。
        删除边最好用列表推导式匹配节点和权重，
        """

    def __repr__(self):
        # 输出self.data的值  u：[(v1, w1), (v2, w2)]
        return '\n'.join("{}: {}".format(key, value)
                         for key, value in self.data.items())

    def __str__(self):
        return '-------Graph---------' + '\n' + self.__repr__()


# 节点列表
nodes = ["Beijing", "Shanghai", "Guangzhou", "Shenzhen", "Chengdu"]

# 边列表 (u, v, w)
edges = [
    ("Beijing", "Shanghai", 1200),
    ("Beijing", "Guangzhou", 1800),
    ("Shanghai", "Shenzhen", 1400),
    ("Guangzhou", "Shenzhen", 200),
    ("Shenzhen", "Chengdu", 2200),
    ("Chengdu", "Beijing", 1600)
]

graph1 = w_graph(nodes, edges, True, True)
print(graph1)

会得到如下格式的输出

-------Graph---------
Beijing: [('Shanghai', 1200), ('Guangzhou', 1800)]
Shanghai: [('Shenzhen', 1400)]
Guangzhou: [('Shenzhen', 200)]
Shenzhen: [('Chengdu', 2200)]
Chengdu: [('Beijing', 1600)]

3.2 最短路径 Dijkstra's algorithm

Dijkstra是一种贪心算法

PS:

（Dijkstra 假设“已经确定的最短距离不会再被更新”，这个假设在负权情况下可能被打破，所以weight不能是负数）

算法步骤

1，初始化

        先将所有node标记为 unvisited。visited_node被添加到visited = set（）中。

        并以distance[node]表示某个节点的最短路径。初始化为distance = {node：inf}

2，对当前节点，访问他的unvisited neighbours，并计算最短路径

        （取距离当前节点距离最小的节点），与初始值比较，取较小值，并更新distance。

3，将当前节点标记为以访问。

4， 结束条件

        如果只是求两个特定节点的最短路径，当target出现在visited中时，就结束

        如果求整张图的最短路径，当未访问节点最小 dist = ∞时，停止。

        这表示未访问节点和源点不联通。

实现代码

朴素数组扫描

def shortest_path(graph, source=None, target=None):
    """
    朴素 Dijkstra：数组 + 线性扫描版本。
    graph.nodes : 可迭代的节点集合
    graph.data  : 邻接表，形如 data[u] = [(v, w), ...]
    """
    # ------------------------------------------------------------------
    """
        路径重构函数，
        因为当前的数据都是字典存储，是无序的，
        所以要想恢复路径，只能依赖parent指针
        如果是列表并且node是有序数字，就可以依照索引，直接输出parent[:target]
        不过这个只适合教学。现生没有这么容易
    """
    def reconstruct_path(parent, source, target):

        """
        根据target不断回溯parent直到source
        """
        result = []
        vis_parent = set()
        temp = target
        source = int(source)  # 强制类型一致
        while temp is not None:
            if temp in vis_parent:
                break
            vis_parent.add(temp)
            result.append(temp)
            temp = parent.get(temp)

        result.reverse()

        # 如果当前target可达source，则返回路径
        if result and result[0] == source:
            return result

        return []

    def get_all_paths(parent, source, nodes):
        paths = {}
        for target in nodes:
            paths[target] = reconstruct_path(parent, source, target)
        return paths

    # ===== 1. 参数检查 =====
    if source is None:
        raise ValueError("source node is required")

    # ===== 2. 初始化容器 =====
    visited = set()   # 已确定最短路的节点
    dist = {node: float('inf') for node in graph.nodes}  # 当前最优距离
    parent = {node: None for node in graph.nodes}  # 路径重构指针

    dist[source] = 0

    while True:

        # Step 1：在线性扫描中选择 dist 最小的未访问节点
        curr = None
        min_dist = float('inf')
        for node in graph.nodes:
            if node not in visited and dist[node] < min_dist:
                curr = node
                min_dist = dist[curr]

        # Step 2：若无可选节点，算法结束（图可能非连通）

        if curr is None:
            break
        # Step 3：若 curr 是目标节点，可提前停止
        if target is not None and curr == target:
            break

        # Step 4：搜索邻居，更新距离
        for nebor, w in graph.data.get(curr, []):
            if nebor in visited:
                continue
            if dist[curr] + w < dist[nebor]:
                dist[nebor] = dist[curr] + w
                parent[nebor] = curr
        # 将当前节点标记为已访问
        visited.add(curr)
        # print(visited)
        # 如果指定了节点，返回到当前节点的路径
        if target is not None:
            return dist[target], reconstruct_path(parent, source, target)
    """
    print('source:', source)
    print('parent:', parent)
    print('nodes:', graph.nodes)
    """

    f_dist = '\n'.join("{}: {}".format(key, value) for key, value in dist.items())
    all_path = get_all_paths(parent, source, graph.nodes)

    return f_dist, all_path


num_nodes = [i for i in range(9)]
edges5 = [(0, 1, 3), (0, 3, 2), (0, 8, 4), (1, 7, 4), (2, 7, 2), (2, 3, 6),
          (2, 5, 1), (3, 4, 1), (4, 8, 8), (5, 6, 8)]

graph2 = w_graph(num_nodes, edges5, weighted=True)
dist, path = shortest_path(graph2, 0)
print(dist)
print(path)

复杂度

• 朴素方法：遍历数组 → O(V)

• 主循环最多访问每个节点一次 → 外层循环 O(V) 

所以扫描节点的时间复杂度为O(V^2),此外，还需要每次访问邻居的权重，这部分的复杂度为O(E)

O(n) = O(V^2 + E)

这显然是非常高的。

可以发现，复杂度主要集中在遍历数组，每次都要扫描整个 dist[] 数组找到未访问节点中距离最小的节点 → O(V)。

优先队列优化

我们需要以一个复杂度更小的数据结构来存储，未访问节点及其当前距离。

那么”能否用一个结构，随时保持当前未访问节点中距离最小的节点？“

此前学到的完全二叉树就是一个可以考虑的DS：节点在数组里可以顺序存储，左/右孩子下标可直接计算。

因为当前需要min_dist,所以选择最小堆的数据结构。

代码

def dijkstra(graph, source=None, target=None):
    # ===== 1. 参数检查 =====
    if source is None:
        raise ValueError("source node is required")

    # ===== 2. 初始化容器 =====
    visited = set()   # 已确定最短路的节点
    dist = {node: float('inf') for node in graph.nodes}  # 当前最优距离
    parent = {node: None for node in graph.nodes}  # 路径重构指针

    heap = min_heap()
    dist[source] = 0

    heap.push((source, 0))
    # ===== 3. 更新距离和邻居 =====
    while not heap.empty():
        # step 1, 找到当前的节点和对应的最短距离
        curr, curr_dist = heap.pop()
        if curr_dist > dist[curr]:
            continue
        if curr in visited:
            continue
        # step 2：若无可选节点，算法结束（图可能非连通）
        if curr is None:
            break
        # Step 3：若 curr 是目标节点，可提前停止
        if target is not None and curr == target:
            break
        # Step 4：搜索邻居，更新距离
        for nebor, w in graph.data.get(curr, []):
            if nebor in visited:
                continue
            if dist[curr] + w < dist[nebor]:
                dist[nebor] = dist[curr] + w
                parent[nebor] = curr
                heap.push((nebor, dist[nebor]))
        visited.add(curr)

    return dist, parent


# 节点列表
nodes = ["Beijing", "Shanghai", "Guangzhou", "Shenzhen", "Chengdu"]

# 边列表 (u, v, w)
edges = [
    ("Beijing", "Shanghai", 1200),
    ("Beijing", "Guangzhou", 1800),
    ("Shanghai", "Shenzhen", 1400),
    ("Guangzhou", "Shenzhen", 200),
    ("Shenzhen", "Chengdu", 2200),
    ("Chengdu", "Beijing", 1600)
]

graph1 = w_graph(nodes, edges, True, True)

dist, parent = dijkstra(graph1, "Beijing")
print(dist)
print(parent)


num_nodes = [i for i in range(9)]
edges5 = [(0, 1, 3), (0, 3, 2), (0, 8, 4), (1, 7, 4), (2, 7, 2), (2, 3, 6),
          (2, 5, 1), (3, 4, 1), (4, 8, 8), (5, 6, 8)]

graph2 = w_graph(num_nodes, edges5, weighted=True)
dist_1, path = dijkstra(graph2, 7)
print('---------------all  shortest distance to each node-------------')
print(dist_1)
print('------------the shorted path to all nodes---------------')
print(path)