企业官网建设流程全解析

第 3 页：Directed graphs（有向图定义）

内容：定义："Digraph. Set of vertices connected pairwise by directed edges."（有向图：由有向边连接成对的顶点集合。）

物理含义：

• 有向图（Directed Graph，简称 Digraph）的物理存储结构与无向图几乎相同，唯一区别在于addEdge(v, w)的动作。

• 无向图中，addEdge(v, w)在adj[v]中插入w，同时在adj[w]中插入v（双向记录）。

• 有向图中，addEdge(v, w)只在adj[v]中插入w（单向记录）。边 v→w 表示从顶点 v 指向顶点 w，方向是 v 到 w。

• 边本身不带有额外的“方向属性”字节。方向由邻接表中的存储位置决定：出现在adj[v]中的w表示有一条从 v 到 w 的边。

---

第 4 页：Vertex = intersection; edge = one-way street（顶点 = 路口；边 = 单行道）

内容：一张图，显示单行道网络。文字说明 "Vertex = intersection; edge = one-way street."

物理含义：

• 这是有向图的直观物理对应：城市路网中，每条街道有通行方向（单向行驶）。

• 如果你只能沿街道的指定方向行驶，那么从路口 A 到路口 B 可能存在路径，但从 B 到 A 可能不存在，或者存在不同的路径。

• 物理上，每条边只允许一个方向的遍历。遍历算法（DFS/BFS）在前进时只能沿着adj[v]中存储的方向走，不能反向（除非反向边也单独存储了）。

---

第 12 页：Some digraph problems（一些有向图问题）

内容：列出六个典型问题，每个配有小图：

• Path（路径）：是否存在从 s 到 t 的有向路径？

• Shortest path（最短路径）：从 s 到 t 的最短有向路径（最少边数）是什么？

• Topological sort（拓扑排序）：能否重新绘制有向图，使所有边都向上指？（即 DAG 的线性排序）

• Strong connectivity（强连通性）：所有顶点对之间是否都存在双向路径？

• Transitive closure（传递闭包）：对于哪些顶点对 v 和 w，存在从 v 到 w 的路径？

• PageRank（网页排名）：网页的重要性是多少？

物理含义：

• 这些问题是后续各小节的预告。前两个（Path, Shortest Path）可以通过 DFS/BFS 解决（和有向图版本的搜索一致）。

• Topological sort 需要检测有向无环图（DAG）。

• Strong connectivity 和 transitive closure 需要更强的算法（Kosaraju-Sharir、Floyd-Warshall 等）。

• PageRank 是迭代数值算法，不依赖图搜索，但依赖有向图结构。