图

一、图

  1. 图G是由两个集合V和E构成的二元组，记作G=(V，E)，其中V是图 中顶点的非空有限集合，E是图中边的有限集合。
    ● 有向图：图G中的每条边都是有方向的，顶点间的关系用 <vi，vj>表示；
    ● 无向图：图G中的每条边都是无方向的；顶点 间的关系用(vi，vj)表示；
    ● 完全图：图G任意两个顶点都有一条边相连接；

    ● 权： 在图的边或弧中给出相关的数（非负），称为权。
    ● 网：图上的边或弧带权则称为网。

    ● 有向完全图：n 个顶点的有向图有n(n-1) 条边。
    ● 无向完全图：n 个顶点的无向图有 n(n-1)/2 条边。

  2. 度：顶点v 的度是与它相关联的边的条数。记作TD(v)。
    入度：是以 v 为终点的有向边的条数, 记作 ID(v);
    出度：是以 v 为始点的有向边的条数, 记作 OD(v)。
    在有向图中, 顶点的度等于该顶点的入度与出度之和。

  3. 带权图 即边上带权的图。其中权是指每条边标上的具有某种含义的数值 （即与边相关的数）。

  1. 连通图
    在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是 连通的。如果图中任意一对顶点都是连通的，则称此图是连 通图。无向图 G=(V,E) 是连通的，那么边的数目大于等于顶点 的数目减 1
    强连通图：在有向图中，若对于每一对顶点vi和vj，都存在一 条从vi到vj和从vj到vi的路径，则称此图是强连通图。

  1. 生成树
    （最小生成树） 是一个极小连通子图，它含有图中全部n个顶点，但只有n-1 条边。如下所示，图1是一个连通图，图2和图3都是它的生成树：
    如果在生成树上添加1条边 ，必定构成一个环。
    若图中有n个顶点，却少于n-1条边 ，必为非连通图。

二、图的存储结构

图的存储结构有
● 邻接矩阵
● 邻接表
● 十字链表
● 邻接多重表

  1. 邻接矩阵
    对于一个具有n个结点的图，可以使用n*n的矩阵(二维数组)来 表示它们间的邻接关系。

  2. 邻接表
    邻接表由表头结点和表结点两部分组成，其中图中每个顶点均 对应一个存储在数组中的表头结点。如这个表头结点所对应的 顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向 的单向链表中。

三、图的遍历

  1. 深度优先搜索( DFS )
    访问起始点 v;
    若v的第1个邻接点没访问过，深度遍 历此邻接点；
    若当前邻接点已访问过，再找v的第2 个邻接点重新遍历。
  2. 广度优先搜索( BFS )
    在访问了起始点v之后，依次访问 v的 邻接点；
    然后再依次（顺序）访问这些点（下 一层）中未被访问过的邻接点；
    直到所有顶点都被访问过为止。

    附：基本算法——深度优先搜索（DFS）和广度优先搜索（BFS）

四、拓扑排序

AOV网是一种有向无环图，顶点表示一项工作，有向边表示 前一项工作完成后才能开始后一项工作。AOV网中的顶点之 间隐含着某种顺序，求解这个顺序序列的操作称为拓扑排序。 对AOV网进行拓扑排序的基本思想是：
（1）从AOV网中选择一个没有前驱的顶点输出它；
（2）从AOV网中删去该顶点，且删去所有以该顶点为尾的弧；
（3）重复上述两步，直到全部顶点都被输出，或AOV网中不 存在没有前驱的顶点。

AOV网的拓扑序列不是唯一的，
(1) C1,C8,C9,C2,C3,C5,C4,C7,C6
(2) C2,C1,C3,C5,C4,C6,C8,C9,C7
(3) C1,C2,C3,C8,C9,C5,C4,C6,C7