文章目录
article
图简介
AI文章摘要
gemini-2.0-flash-lite
这篇文章介绍了图的基本概念、分类、性质以及遍历方法。图由顶点和边组成，文章定义了度、行走路径、路径等概念。图的分类包括空图、单点图、无向图、有向图等。文章还介绍了有向图和无向图的最大边数计算方法。最后，文章讲解了广度优先遍历和深度优先遍历的实现方法，并指出需要使用队列或栈来辅助遍历，同时使用已发现数组或哈希映射来避免闭环。文章还提供了Python代码示例，展示了图的封装。
图(Graph)
对于图我们关注以下概念：
- 度(degree)： 节点连接的边数。入度(in degree)，节点连接的入边数。出度(out degree)，节点连接的出边数。
- 顶点(vertex)：顶点是图的基本组成部分，有时也叫节点(Node)
- 边(edge): 边用于连接图中的两个顶点。
- 行走路径(walk)： 行走路径是一个节点序列，节点前驱后继需要有边进行连接。
- 路径(path): 路径是一个特殊的行走路径，他不包含重复节点。
在某些书籍中，行走路径(walk)称为路径(path)， 而路径(path)则称为简单路径(simple path)本质上是一样的。
图的分类
- 空图(Null Graph): 不包含边的图。
- 单点图(Trivial Graph): 仅包含1个节点的图
- 无向图(Undirected Graph): 图中的边无确定方向的图。
- 有向图(Directed Graph)：图中的边有确定方向的图。
- 连通图(Connected Graph): 通过图中任一节点可以访问图中其他任意节点的图。
- k-常规图(K Regular Graph): 图中任一节点的度都为k的图。若$k=v-1$则称为完全图，它包含最多的边数。
- 环图(Cycle/Cyclic Graph): 图中所有节点包围成一个环称为环图(Cycle Graph)，图中节点至少形成1个环的图称为(Cyclic Graph)有环图。
- 二分图(Bipartite Graph): 图中节点可分为两分区，分区内节点间不通过边进行连接。
- 加权图(Weighted Graph)： 图中边进行赋权的图。
图的性质
有向图中节点数量$V_{n} = D_{out} = D_{in}$，最大边数$E_{max} = V_{n} * (V_{n} - 1)$
无向图中最大边数$E_{max} = \frac{V_{n} * (V_{n} - 1)}{2}$
图的遍历
广度优先遍历
我们可以使用队列跟踪当前顶点的所有邻接顶点。但图可能存在闭环，需要定义一个已发现数组或哈希映射，遍历邻接顶点时将未发现的顶点入队，并设置顶点为已发现。
深度优先遍历
我们可以使用栈跟踪当前顶点的所有邻接顶点。但图可能存在闭环，需要定义一个已访问数组或哈希映射，在访问当前顶点时先判断是否被访问，访问过后设置顶点为已访问。