认识图

介绍

术语:

• 顶点(vertex):表示图中的一个节点
• 边(edge):表示顶点与顶点之间的连线
• 度:一个顶点的度是相邻顶点的数量
• 简单路径:要求不包重复的顶点
• 回路:第一个顶点和最后一个顶点相同的路径
• 有向图:所有的边没有方向
• 无向图:边是有方向的
• 无权图:边没有携带权重
• 带权图:边有一定的权重

表示

邻接矩阵表示图

邻接矩阵的问题:邻接矩阵如果是一个稀疏图，那么会存在大量的 0 。这意味着我们浪费了存储空间来表示根本不存在的边

邻接表表示图

实现

数据结构与算法推荐资料

---