十一. 图

价值成长

已于 2022-03-13 10:46:57 修改

阅读量376

点赞数

分类专栏：算法文章标签：算法

于 2022-02-05 16:27:42 首次发布

本文链接：https://blog.csdn.net/xd592319702/article/details/122791229

版权

算法专栏收录该内容

37 篇文章 ¥9.90 ¥99.00

订阅专栏

超级会员免费看

本文探讨了图的两种遍历方法：深度优先搜索(dfs)和广度优先搜索(bfs)，其中bfs能寻找最短路径。此外，文章提到了二分图的概念，解释了如何判断一个图是否为二分图，以及如何为二分图的节点进行颜色标记。最后，通过课程表问题展示了图的应用场景。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

edgeTo[] 存储从起点到一个顶点的已知路径上的最后一个顶点。s: 起点。 e: 终点。

dfs: 递归调用。

def dfs(G: Graph, v: int) -> int:
    visited[v] = True
	for w in G.adj(v):
	    if not visited[w]:
            edgeTo[w] = v
            dfs(G, w)

def pathTo(e: int) -> list:
    path = list()
    x = e
    while x != s:
        path.append(x)
        x = edgeTo[x]
    path.append(s)
    return path

bfs：可以找到最短路径。不是递归调用，不隐式的调用栈，显式的使用队列。

def bfs(G: graph, s: int):
    visited[s] = True
    q = collections.deque()
    q.append(s)
    while q:
        v = q.popleft()
        for w in G.adj(v):
            if not visited[w]:
                edgeTo[w] = v