[AIGC] 图论基础入门

Graph Theory

图论是数学的一个分支，旨在研究图（graph）的属性和应用。这是一个跨学科领域，因为图论可以用于描述和解决各种实际问题。如社交网络分析，电脑网络，生物网络等。

文章目录

- 什么是图？
- 图的基本性质
- LeetCode 图论相关问题解析及Python代码实现
- LeetCode 题目：207. 课程表
- - 解题思路：
  - Python 代码实现：

什么是图？

图是由点（称为节点或顶点）和线（称为边）组成的。这些点和线可能代表现实生活中的某些对象或实体，边表示这些对象之间的某种关系。

基本上，有两种类型的图：

无向图：边没有方向。如果存在一条连接节点 A 和节点 B 的边，那么我们可以说 A 是 B 的邻居，反之亦然。

eg. A – B
有向图：边有方向。如果存在一条从节点 A 指向节点 B 的边，那么我们只能说 B 是 A 的邻居，但不能说 A 是 B 的邻居。

eg. A --> B

注意：在无向图中，边 (A,B) 和 (B,A) 是相同的。但在有向图中，A->B 和 B->A 代表两个不同的边。

图的基本性质

现在我们已经了解了图是什么，那么我们就可以进一步讨论图论的一些基本性质和术语了。

度（Degree）：一个节点的度是其相邻节点的数量。在有向图中，我们区分入度（indegree）和出度（outdegree），分别表示指向节点和从节点指出的边的数量。
路径（Path）：在图中，一条路径是一个节点序列，其中每个节点都通过边与下一个节点相连。
循环（Cycle）：循环是一条路径的特殊类型，其中第一个节点和最后一个节点是同一节点。
连通性（Connectivity）：在无向图中，如果从任何节点可以到达任何其他节点，那么图是连通的。在有向图中，这称为强连通性。
子图（Subgraph）：子图是原图的一部分，包含原图的一些节点和边。树（Tree）就是一种没有环的连通无向图。

LeetCode 图论相关问题解析及Python代码实现

接下来，我们将讨论一些LeetCode上的图论相关问题，并提供Python代码及解题思路。

（注意：以下题目仅作为图论入门阶段的学习，可能不涵盖图论所有范围和技巧）

好的，我已经为您找到了一些具有图论问题的 LeetCode 代码解决方案。其中一些最受欢迎和全面的资源包括：

coding-interview-gym by partho-maple
- ⭐星数: 832
- 💬描述: leetcode.com，algoexpert.io solutions in python and swift
- 主要语言: Python
leetcode by hongbo-miao
- ⭐星数: 197
- 💬描述: LeetCode solutions
- 主要语言: Python
Algorithms by kumailn
- ⭐星数: 55
- 💬描述: ✨ a bunch of algorithms in a bunch of languages ✨
- 主要语言: Python

以上代码库大多专注于 LeetCode 的问题解决，并涉及诸多热门语言解决方案。虽然这些代码库提供了许多问题的解决方案，但每个问题的详细解析或讨论可能因代码库而异。建议在查看这些资源时，重点理解代码逻辑并尝试自己解决这些问题以提升技能。

如果您需要了解关于特定问题的更多信息，我建议访问 LeetCode的图论问题页面，这将提供大量有关图论问题的详细信息。

LeetCode 题目：207. 课程表

这是一道比较经典的图论问题。问题介绍如下：

现在你总共有 n 门课需要选，记为 0 到 n-1。在选修某些课程之前需要一些前置课程，例如想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们之间这种前置课程关系：[0,1]。

给定课程总量以及它们的前置课程，判断是否可能完成所有课程的学习？

解题思路：

我们要找的是课程间的依赖关系，这个关系其实就是一个有向图。我们可以使用拓扑排序来解决这个问题。一个有向图如果没有环，那么一定存在拓扑排序。

我们首先遍历所有的边，计算每门课程的入度（前置课程数量）。每次选择一个入度为0的课程，将它的所有后继课程的入度减1，直到所有的课程的入度都为0。如果还有课程的入度不为0，那么说明图中存在环，也就不能完成所有课程的学习。

Python 代码实现：


def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    from collections import deque
    # 入度表
    indegrees = [0 for _ in range(numCourses)]
    # 邻接表
    adjacency = [[] for _ in range(numCourses)]
    # 队列
    queue = deque()
    # 通过 prerequisites 得到入度表和邻接表
    for cur, pre in prerequisites:
        indegrees[cur] += 1
        adjacency[pre].append(cur)
    # 将所有入度为 0 的节点入队
    for i in range(len(indegrees)):
        if not indegrees[i]: queue.append(i)
    
    # BFS 拓扑
	  while queue:
	      pre = queue.popleft()
	      numCourses -= 1
	      for cur in adjacency[pre]:
	          # 将后继课程的入度 -1
	          indegrees[cur] -= 1
	          # 如果后继课程入度为 0，那么将其加入到队列中
	          if not indegrees[cur]: queue.append(cur)
	
	  # 如果所有的课程都已经学完，那么说明可以完成课程学习，否则就不能
	  return not numCourses