当前位置:AIGC资讯 > AIGC > 正文

[AIGC] 图论基础入门

图论是数学的一个分支,旨在研究图(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->BB->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

这是运用了图论中的拓扑排序的技术来解决这个问题的。

以上便是对于 LeetCode 207.课程表 这个题目的解题思路及其 Python 代码实现,希望对你有所帮助。如果需要更多的帮助或者有其他的问题,欢迎随时告诉我。

我希望这些信息对您有所帮助!如果您有其他问题或需要更深入的解析,请告诉我!

总结

本文介绍了图论的基本概念、性质和实际应用,包括无向图和有向图的定义、图的基本性质如度、路径、循环、连通性和子图等。文章还通过解析LeetCode上的图论相关问题,提供了Python代码实现和解题思路,特别是针对“课程表”这一经典图论问题,详细阐述了如何使用拓扑排序判断是否能完成所有课程的学习。这些内容不仅展示了图论在解决实际问题中的强大功能,也为学习和掌握图论知识提供了实用的参考。

更新时间 2024-07-11