主题
面试速答（先看这里）
**一句话结论：**在无向图中，边没有方向。
60秒标准回答：
图是一种复杂的数据结构，用于有效地表示和处理由一组元素（称为顶点或节点）及其相互关联的信息（称为边）组成的集合。 它表明了物件与物件之间的 “多对多” 的一种复杂关系。 图数据结构非常适合用来表示任何形式的网络，例如社交网络、交通网络、通信网络等
图可以分为两大类： 有向图 和 无向图
在无向图中，边没有方向。如果顶点A与顶点B通过一条边相连，那么我们可以说A和B是互相连接的，这条边没有方向性，表示A到B和B到A都是可达的。无向图的边通常表示双向的或者双方等同的关系，如友谊、合作等
**答题顺序：**结论 → 原理/机制 → 关键流程 → 场景与取舍 → 易错点
回答主线：
- **要点1：**图是一种复杂的数据结构，用于有效地表示和处理由一组元素（称为顶点或节点）及其相互关联的信息（称为边）组成的集合。
- **要点2：**与无向图不同，有向图中的边具有方向。
- **要点3：**有权图和无权图是图数据结构的两种类型，它们主要区别在于边是否具有权重。
- **要点4：**在 无权图 中，边没有权重，即所有的边都被视为等同。
- **要点5：**图的遍历是指从图中的一个顶点开始，访问图中的所有顶点，并且保证每个顶点仅被访问一次的过程。
**记忆锚点：**Search → Breadth-First → Depth-First → 和无权图是图数据结构 → 地搜索图的分支的算法 → 组成的集合
关键取舍：
- 有权图和无权图是图数据结构的两种类型，它们主要区别在于边是否具有权重。
- 这种权重通常代表了连接两个节点之间的一种度量，如距离、时间、成本或资源使用量等。
- 在 有权图 中，边附带一个权重（或成本、标签），这可以用来表示从一个顶点到另一个顶点的代价或资源消耗。
加分表达：
- 如果顶点A与顶点B通过一条边相连，那么我们可以说A和B是互相连接的，这条边没有方向性，表示A到B和B到A都是可达的。
- 如果顶点A指向顶点B（A→B），那么这个方向表明从A到B有一条路径，而从B到A则不一定有路径。
- 图通常可以通过以下几种方式在计算机中表示和存储： 邻接矩阵 ：一个二维数组，其中的元素表示顶点之间是否存在边。
追问准备：
- 围绕「Search」：底层原理是什么？使用时有哪些边界和常见坑？
- 围绕「Breadth-First」：底层原理是什么？使用时有哪些边界和常见坑？
- 围绕「Depth-First」：底层原理是什么？使用时有哪些边界和常见坑？
- 如果线上出现异常，你会如何定位、验证并规避？
典型回答
图是一种复杂的数据结构，用于有效地表示和处理由一组元素（称为顶点或节点）及其相互关联的信息（称为边）组成的集合。它表明了物件与物件之间的**“多对多”**的一种复杂关系。图数据结构非常适合用来表示任何形式的网络，例如社交网络、交通网络、通信网络等。
图可以分为两大类：有向图和无向图
无向图
在无向图中，边没有方向。如果顶点A与顶点B通过一条边相连，那么我们可以说A和B是互相连接的，这条边没有方向性，表示A到B和B到A都是可达的。无向图的边通常表示双向的或者双方等同的关系，如友谊、合作等。
有向图
与无向图不同，有向图中的边具有方向。如果顶点A指向顶点B（A→B），那么这个方向表明从A到B有一条路径，而从B到A则不一定有路径。有向图的边可以表示如权限、流程控制或一种单向关系等更复杂的关系。
扩展知识
有权图和无权图
有权图和无权图是图数据结构的两种类型，它们主要区别在于边是否具有权重。这种权重通常代表了连接两个节点之间的一种度量，如距离、时间、成本或资源使用量等。
在无权图中，边没有权重，即所有的边都被视为等同。在这种图中，两个顶点之间的连接仅表示它们之间存在一种关系，而不提供关于这种关系的任何额外信息。
在有权图中，边附带一个权重（或成本、标签），这可以用来表示从一个顶点到另一个顶点的代价或资源消耗。权重可以是任何有意义的量度，如距离、时间、费用等。
图的存储方式
图通常可以通过以下几种方式在计算机中表示和存储：
- 邻接矩阵：一个二维数组，其中的元素表示顶点之间是否存在边。对于有向图，矩阵不对称；对于无向图，矩阵是对称的。
- 邻接表：为每个顶点创建一个列表，存储与该顶点直接相连的其他顶点。这种方法在稀疏图中比邻接矩阵更节省空间。
图的遍历
图的遍历是指从图中的一个顶点开始，访问图中的所有顶点，并且保证每个顶点仅被访问一次的过程。图的遍历主要有两种基本的图遍历方式：深度优先搜索（Depth-First Search, DFS）和广度优先搜索（Breadth-First Search, BFS）。
深度优先搜索是一种沿着图的边遍历顶点，尽可能深地搜索图的分支的算法。当到达一个顶点而这个顶点没有未访问的邻接顶点时，搜索将回溯到发现该顶点的那条边的起始顶点。这一过程一直进行到已发现从原始顶点可达的所有顶点为止。
广度优先搜索是从图的一个顶点开始，访问所有可从此顶点出发通过一条边直接到达的邻接顶点，然后对每一个已访问的邻接顶点，再访问它们的邻接点，并以此类推，层层扩展直到图中所有可达的顶点都被访问。
