图

基本概念

• 

• 注意：

  ​ 线性表可以是空表，树可以是空树，但图不可以是空，即v一定是非空集

无向图、有向图

简单图、多重图

• 简单图
• 多重图

顶点的度、入度、出度

• 无向图：顶点v的度是指依附于改顶点的边的条数，极左TD(v)

• 有向图：

  ​ 入读是以顶点v为终点的有向边的数目，记为ID(v)

  ​ 出度是以顶点v为起点的有向边的数目，记为OD(v)

  ​ 顶点的度等于入度和出度之和，TD(v)=ID(v)+OD(v)

顶点-顶点的关系描述

• 路径：顶点v1到顶点v2之间的一条路径
• 回路：第一个顶点和最后一个顶点相同的路径称为回路或环
• 简单路径：在路径序列中，顶点不重复出现的路径称为简单路径。
• 简单回路:除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
• 路径长度:路径上边的数目
• 点到点的距离:从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷
• 无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的
• 有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的

几种特殊的图