文章目录
article
图简介
AI文章摘要
qwen-turbo-latest
加载中...
图(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}$
图的遍历
广度优先遍历
和树的广度优先遍历相似，我们可以使用队列记录待访问节点。但需要注意树是无环的，图是有可能有环的，在遍历的时候需要确保节点仅访问一次。 我们需要一个数组或哈希表用于记录已发现的节点，在是将节点的另接节点入队前检查该节点是否已经被发现。