图的存储结构

图的相邻矩阵表示法

表示顶点间相邻关系的矩阵。

图的邻接表表示法

• 顶点表：对应 $n$ 个顶点，包括顶点数据和指向边表的指针。
• 边链表：对应 $m$ 条边，包括顶点序号和指向边表下一表目的指针。

无向图

无向图的邻接表

边链表中表目顺序往往按照顶点编号从小到大排列。

有向图

有向图的邻接表

只需要保存出边表和入边表之一即可。

图的周游

两类主要方式：

• 深度优先
• 广度优先

深度优先搜索

重点在于标记已经访问过的节点。