图的基础定义
图（Graph）是数据结构中非常经典的结构，由两个集合组成：顶点集 V 和边集 E，记作 G=(V,E)。其中 V 是非空有限集合，代表图中的节点；E 是 V 中顶点偶对的有限集合，代表连接这些节点的边。如果 E 为空，那图就只剩下一堆孤立的点。
根据边的方向性，图主要分为两类：
- 有向图：边是有序的顶点对 <x,y>，表示从 x 指向 y 的弧。这里 x 是弧尾，y 是弧头，<x,y> 和 <y,x> 是两条不同的边。
- 无向图：边是无序的顶点对 (x,y)，表示 x 和 y 之间相互关联，(x,y) 等同于 (y,x)。
核心术语解析
理解图之前，有几个术语必须搞清楚，这直接关系到后续算法的实现逻辑。
- 完全图：无向图中若有 n(n-1)/2 条边，或有向图中有 n(n-1) 条弧，则称为完全图。这意味着任意两点间都有直接连接。
- 度、入度与出度：顶点的度指关联边的数量。在有向图中，分为入度（指向该点的弧数）和出度（从该点发出的弧数），两者之和等于总度数。
- 路径与回路：路径长度即经过的边或弧的数量。若路径首尾顶点相同，则构成回路或环。
- 连通性：无向图中若任意两点间都有路径，则为连通图。有向图中若任意两点间双向可达，则称为强连通图。
图的遍历算法
遍历是处理图结构最常用的操作，主要有两种策略：深度优先搜索（DFS）和广度优先搜索（BFS）。
深度优先搜索（DFS）
DFS 的思路很像树的先序遍历，讲究'一条路走到黑'。
- 从某个顶点出发，访问并标记它。
- 接着找它的第一个未被访问的邻接点，递归执行上述步骤。
- 当无路可走时，回溯到上一个顶点，尝试其他未访问的邻接点。
- 重复直到所有顶点都被访问过。
广度优先搜索（BFS）
BFS 则更像层层扩散，通常借助队列来实现。
- 起点入队并标记已访问。
- 取出队首顶点，将其所有未访问的邻接点入队并标记。
- 循环此过程，直到队列为空。
这两种方法各有优劣，DFS 适合寻找特定路径或连通分量，BFS 则常用于求最短路径（无权图）。
拓扑排序与应用
在项目管理或任务调度中，我们常遇到依赖关系，这时就需要用到 AOV-网（Activity On Vertex Network）。
- AOV-网：用顶点表示活动，弧表示优先关系。若 a 到 b 有路径，a 就是 b 的前驱。
- 拓扑排序过程：
- 选一个没有前驱的顶点输出。
- 删除该顶点及其发出的所有弧。
- 重复上述步骤，直到所有顶点输出或无法继续。
- 若输出的顶点数少于总数，说明图中存在环，无法进行拓扑排序。
关键路径分析
如果是带权重的工程网络（AOE-网），问题就变成了估算工期。路径上各弧权值之和即为带权路径长度。我们要找的是从源点到汇点的最长路径，这条路径决定了整个工程的最短完成时间，被称为关键路径。位于关键路径上的活动就是关键活动，任何延误都会影响整体进度。值得注意的是，关键路径可能不止一条。
掌握这些基础概念，对于理解更复杂的图算法至关重要。实际开发中，无论是依赖管理还是网络路由，背后都离不开图论的支持。
