图论

更新: 10/1/2024 字数: 0 字 时长: 0 分钟

图的定义

图是由顶点（或称为节点）和边（或称为连接）组成的数据结构。顶点表示对象，边表示对象之间的关系。

图的分类

有向图和无向图

• 有向图：边有方向，从一个顶点指向另一个顶点。
• 无向图：边没有方向，两个顶点之间的连接是双向的。

连通图和非连通图

• 连通图：任意两个顶点之间都有路径相连。
• 非连通图：存在两个顶点之间没有路径相连。

图的表示

图可以用多种方式表示，常见的有邻接矩阵和邻接表。

邻接矩阵

邻接矩阵是一个二维数组，其中行和列分别表示图的顶点，矩阵的元素表示两个顶点之间是否存在边。

邻接表

邻接表是一种链表数组，其中每个顶点对应一个链表，链表中存储了与该顶点相连的顶点。

图的遍历

图的遍历是指访问图中的所有顶点，常见的有深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索（DFS）

深度优先搜索是一种递归的图遍历算法，从一个顶点开始，沿着一条路径一直走到底，然后回溯到上一个顶点，继续沿着另一条路径走到底，直到所有顶点都被访问过。