图的定义
- 一个图G(Graph)是由两个集合:V和E所组成的，V是有限的非空顶点(Vertex)集合，E是用顶点表示的边(Edge)集合，图G的顶点集和边集分别记为V(G)和E(G)，而将图G记作G=(V，E)。
- 可以看出，一个顶点集合与连接这些顶点的边的集合可以唯一表示一个图。
- 在图中，数据结构中的数据元素用顶点表示，数据元素之间的关系用边表示。
图的相关概念
有向图(括号是尖括号）
- 图中每条边都是有方向的。从顶点vi到顶点vj表示为<vi，vj>
而从顶点vj到顶点vi表示为<vj,vi>。有向边也称为弧。起点称为弧尾终点称为弧头。
无向图(括号是圆括号）
完全图
若一个无向图具有n个顶点，而每一个顶点与其他n-1个顶点之间都有边，则称之为无向完全图。显然，含有n个顶点的无向完全图共有n(n-1)/2条边，类似地，有n个顶点的有向完全图中弧的数目为n(n-1)，即任意两个不同顶点之间都存在方向相反的两条弧。
图的存储结构
(1)邻接矩阵表示法
有边就记为1，无边记为0
无向图都是对称的
网(带有权值的图)的邻接矩阵的表示:
(2)邻接链表表示法
- 邻接链表是为图的每一个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点vi的表(对于有向图是以vi为尾的弧)
- 邻接链表中的表节点有表节点和表头节点两种类型
无向图的邻接链表表示法
有向图的邻接链表表示法
带权值的网的邻接链表表示法
