一起动脑筋 · 先看一个小故事
学校、图书馆、公园之间有几条路。女孩发现路线会绕圈，光用家族树式的分叉画不全。
把过程摊开来看
- 点三个地点
- 边地点间的道路
- 路线沿边移动
- 环可能绕回起点
图用顶点表示对象，用边表示关系。
道路可以双向，也可以单向；还可以给边标路程或时间。不同标法会影响之后找路的算法。
01这里的“图”不是图片
数据结构里的图（Graph）不是照片或图画。
它是一组顶点（vertex）和连接这些顶点的边（edge）。
02一个最简单的图
ABCD
可以想象 A-B、B-C、A-D 之间存在连接。
03什么是顶点和边？
顶点
表示对象，例如城市、用户、网页。
边
表示对象之间的连接，例如道路、好友关系、链接。
04图可以有方向吗？
可以。
无向图
A 和 B 相连，没有方向。
有向图
A → B 与 B → A 可以是不同关系。
05图可以有环吗？
可以。
A→B→C→A
这形成一个环。和树不同，一般的图允许出现环。
06图一定所有点都连在一起吗？
不一定。
一个图可以包含多个互相没有路径连接的部分，这些部分可以形成不同的连通分量。
07现实中哪些问题可以抽象成图？
城市道路
城市是点，道路是边。
社交网络
用户是点，关系是边。
互联网
设备或网络是点，连接是边。
网页链接
网页是点，超链接是有向边。
08程序里怎样保存图？
常见方式包括：
- 邻接矩阵
- 邻接表
- 边列表
不同表示适合不同规模和操作。
你已经知道了什么
- 图由顶点和边组成。
- 图可以表示一般连接关系。
- 图可以有向或无向。
- 图可以有环，也可以不连通。
- 图可以用邻接表、邻接矩阵等方式存储。
下一篇：树和图有什么区别？
轮到你来试一试
单行路从学校到公园，能自动认为也能从公园走回学校吗？
想好了吗？点开看解释
不能。有向边只允许指定方向，需要另有反向道路才行。