定义：
图 是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E) ,其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

G = (V,{E}) ,G’ = (V’,{E’}) G’ 为 G的子图
几个概念：

  • 图中数据元素，称之为顶点（Vertex）
  • 图结构中，不允许没有顶点，若V是顶点的集合，则顶点集合V有穷非空
  • 在图中，任意两点之间都有可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的

无向边：若顶点Vi 到 Vj 之间的边没有方向，则称这条边为无向边（Edge）,用无序偶对（Vi,Vj）来表示
若图中任意两个顶点之间的边都是无向边，则称该图为无向图.用“（）”表示

有向边：若从顶点Vi 到 Vj 的边有方向，则称这条边为有向边，也称为弧（Arc）,用有序偶来表示，vi称为弧尾（tail），vj称为弧头（head），用“<>”表示

简单图：若不存在顶点到其自身的边，且同一条边不重复出现

无向完全图：在无向图中，如果任意两个顶点之间都存在边 n(n-1) /2 条边
有向完全图：如果任意两个顶点之间都存在方向互为相反的两条弧 n(n-1) 条边

与图的边或弧相关的数叫做权（weight）,这些权可以表示从一个顶点到另一个顶点的距离或者耗费
这种带权的图，通常称为网
**

图的顶点与边间的关系

对于无向图 G = (V,{E}） 如果（v,v’） 属于E ,顶点v 和 v’ 互为邻接点 相邻 关联
顶点V的度是和v相关联的边的数目

有向图，以顶点v为头的弧的数目称为V的入度，以v为尾的弧的数目为v的出度
TD(V) = ID(V) + OD(V)

路径的长度是路径上的边或弧的数目
第一个顶点到最后一个顶点相同的路径称为回路或环
序列中不重复出现的路径称为简单路径
除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路，称为简单回路或简单环

连通图

在无向图中，如果顶点V到顶点V’有路径，则称v和v’ 是连通的，如果对于图中任意两个顶点都是连通的，称G为连通图
有向，则称为强连通图

无向图中的极大连通子图称为连通分量，有向的则称为强连通分量

无向图中连通且n 个顶点n-1 条边叫生成树
有向图中一顶点入度为0 其余顶点入度为1的叫有向树，一个有向图由若干棵有向树构成生成森林

图的邻接矩阵存储方式是 用两个数组来表示图
一个一维数组存放 图中顶点的信息
一个二维数组 存放图中边或弧的信息

深度优先更适合目标明确，以找到目标为主的目的情况
广度优先更适合在不断扩大遍历范围时找到相对最优解的情况