0. 前言

Reference : 8.1, 8.2

1. 什么是 graph
2. 如何使用 graph
3. 如何实现 graph 这个 ADT （多种方式）
4. 如何用 graph 解决一些问题（最短路径 Shortest Path）

Graph 是比 Tree 更加 general 的一种数据结构，Tree 其实就是一种特殊的 Graph。

Graph 可以用来代表很多东西，包括道路系统、航线、互联网的链接、甚至是选课路径。

不同的数据结构是为了解决不同的问题。 Graph 可以帮助我们解决一些用其他数据结构很难解决的问题。

1. Graph 的常见术语

1. Vertex(node) - it’s name is called “key”, additional info is called “payload”
2. Edge(arc) - connects 2 vertices to show relationship, 可以是单向关系也可以是双向关系
   1. 假如图里面所有的edge都是单向，就是directed graph或者diagraph；
3. Weight - edge may be weighted to show there is a cost to go from one vertex to another. 在路线图里面可以表示两地距离。
4. Path - 从 A 到 B 经过的 edge 的有序集合。
   • Formally we would define a path as 𝑤1,𝑤2,…,𝑤𝑛 such that (𝑤𝑖, 𝑤𝑖 + 1) ∈ 𝐸 for all 1 ≤ 𝑖 ≤ 𝑛−1
   • 假如 edge 没有 weight 这个属性，那么路径的长度就等于 edge 的数量
   • 假如有 weight 属性，那么就等于 weight 的总和
5. Cycle - 在 directed graph 里面就是一个起点和终点 node 一样的 path
   • 没有 cycle 的 graph 叫做 acyclic graph
   • 没有 cycle 的 directed graph 叫做 directed acyclic graph（DAG），假如问题可以被 DAG 所代表，那么我们就能解决一些重要的问题。

G = (V, E)

• V 是 vertex 的集合，
• E 是 edge 的集合，
• 每个 edge 都有一个 tuple (x, y)，x, y ∈ 𝑉
  • 如果要加 weight 的话可以在 tuple 里面加入第三个元素
• subgraph（子图）s 包含 E 的一部分和 V 的一部分
  • s = (v, e), 𝑒 ⊂ 𝐸, 𝑣 ⊂ 𝑉

𝑉 = {𝑉0,𝑉1,𝑉2,𝑉3,𝑉4,𝑉5}

𝐸 = {(𝑣0,𝑣1,5),(𝑣1,𝑣2,4),(𝑣2,𝑣3,9),(𝑣3,𝑣4,7),(𝑣4,𝑣0,1),(𝑣0,𝑣5,2),(𝑣5,𝑣4,8),(𝑣3,𝑣5,3),(𝑣5,𝑣2,1)}