1.图的定义

图：图（graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V，E）,其中G表示一个图，V是图中顶点（vertex）的集合，E是图中边的集合。注意几点：1.线性表中我们把数据元素称之为元素，树中把数据元素称之为结点。对于图中的数据元素我们称之为顶点（vertex）。2.线性表中可以没有元素称之为空表，树中可以没有元素称之为空树，但是图中的顶点集合V有穷非空。3.线性表中相邻的数据元素之间具有线性关系，树结构中相邻两层的结点具有层次关系，而图中任意两个顶点都有可能具有关系，顶点之间的逻辑关系用边表示，边集可以为空。

无向边：若顶点到Vi到Vj之间的边没有方向，则称这条边为无向边（Edge），用无需偶对（Vi,Vj）来表示。
无向图：图中任意两个顶点之间的边都是无向边，则称该图为无向图（Undirected graph）。
例如：下图中就是一个无向图，顶点A与顶点D之间的边可以用无需偶对表示成（A，D），也可以表示成（D，A）。对于下图的无向图G1来说，G1 = （V1，{E1}），其中顶点集合为V1 = {A，B，C，D}，边集合为E1 = {（A，B），（A，C）,(A,D),(B,C),(C,D)}

无向图.png

有向边：若从顶点Vi到Vj的边有方向，则称这条边为有向边，也成为弧（Arc）,用有序偶对<Vi,Vj>来表示Vi称为弧尾（tail），Vj称为弧头（head）。
有向图：如果图中任意两个顶点之间的边都是有向边，则该图为有向图。例如：下图就是一个有向图，顶点A到顶点D之间的边称为就是弧，A是弧尾，D是弧头,<A,D>表示弧，因为弧有方向所以不能写成<D,A>.对于下图的有向图G2来说，G2 = (V2,{E2}),其中顶点集合为V2 = {A,B,C,D},弧集合E2 = {(A,D),(C,A),(B,A),(B,C)}.注意：无向边用()表示，有向边用<>表示。

有向图.png

简单图：若不存在顶点到其自身的边，且同一条边不重复出现，这样的图为简单图。例如下图就不是简单图：

非简单图.png

无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称改图为无向完全图。含有N个顶点的无向完全图有N*（N - 1）/2条边。

无向完全图.png

有向完全图：在有向图中任意两个顶点之间都存在方向互为相反的两条弧则称该图为有向完全图。含有N个顶点的有向完全图有N*（N-1）条弧。

有向完全图.png

权：与图的边或弧相关的数叫做权（Weight），这种带权的图称为网（netWork）。

网.png
子图：假设有两个图G=（V，{E}），G‘=（V’，{E‘}），如果V’包含于V，并且E‘包含于E，则G’称为G的子图（Subgraph）。

2.图的顶点与边之间的关系

对于无向图来说，假设一个图G=（V，{E}），如果边(V,V')属于E，则顶点V和V‘称为邻接点（Adjacent），即V和V’相邻接，边（V，V‘）与顶点V，V’相关联。顶点V的度是和V相关联的边的数目，即为TD（V）。边数为各顶点度数之和的一半。例如下图中：

无向图示例.png
上图中，边（A，D）与顶点A，D相关联，A，D互为邻接点，顶点A的度为3，各顶点度数之和为10正好是边数的一半。

对于有向图来说，假设一个图G=(V,{E}),如果弧<V,V'>属于E集合，则称顶点V邻接到顶点V’。弧<V,V'>和顶点V，V‘相关联。以顶点V为头的弧的数目称为V的入度（InDegree）,记为ID(V),以V为尾的弧的数目称为V的出度（OutDegree）记为OD（V）。顶点V的度为TD（V） = ID（V） + OD（V）。各顶点的出度和与各顶点的入度和与弧数相等。

有向图示例.png

上图中顶点A的入度为2，出度为1，A的度为3.

路径：从一个顶点V到另一个顶点V’的顶点序列（V= Vi,0,Vi1....Vim = V'）其中（Vi,j-1,Vi,j）属于边集合E并且1 <= j <= m.有向图的路径应满足：（V= Vi,0,Vi1....Vim = V'）其中<Vi,j-1,Vi,j>属于弧集合E并且1 <= j <= m
路径长度：路径上的边或弧的数目称为路径长度。例如下图中顶点B到D如黑线是一条路劲，其路径长度为2.