Coding interview 的 Graph cheatsheet

Introduction

Graph 是由一组对象（nodes/vertices）和它们之间的边（edges）组成的结构。边可以是 directed 或 undirected，也可以带权重（weighted graph）。Tree 是一种 undirected graph，其中任意两点之间只有唯一一条边，且不存在 cycle。

Graph 常用于描述无序实体之间的关系，比如：

• 人与人的朋友关系 - 节点是人，边表示两个人是朋友。
• 地点之间的距离 - 节点是地点，边表示地点相连，边的值表示距离。