图

图的定义

• 有向图

• 无向图

• 邻接点（边的两个顶点互为邻接点）

• 关联边（一条边的两个顶点关联这条边）

• 路径

• 回路
• 简单路径

• 简单回路

• 连通图（任意两个顶点之间都存在路径）

• 强连通图（对有向图，任意两个顶点之间都存在路径）
• 子图
• 连通分量（无向图中的极大联通子图）
• 强连通分量（有向图中的极大强连通子图）
• 网络（边带权图）
• 生成树（连通图的一个包含其所有顶点的子图是一棵树，这棵树就是生成树）

图的存储结构

一张图，要存储的信息至少有两方面：

• 顶点的数据信息
• 顶点间的关系信息

邻接矩阵

图的邻接矩阵是一个n阶矩阵，物理上是一个二维数组。
对无向图而言，

• 其邻接矩阵是一个对称矩阵，且对角线元素均为零；
• 图的总度数就是矩阵中非零元素个数
• 图的边数就是非零元素个数的一半

对有向图而言：

• 第i个顶点的入度就是第i列非零元素个数
• 第i个顶点的出度就是第i行非零元素个数

类型实现

typedef struct ArcCell {
    VRType agj;
    Info *info; // 存放相关信息的指针
} ArcCell, AdjMatrix[M][N];
typedef struct {
    VertexType vexs[MAX];   // 顶点信息
    AdjMatrix arcs; // 存储弧的信息
    int vexnum, arcnum; // 存储顶点数，弧数
    GraphKind kind; // 存储图的种类
}

特点

空间复杂度比较高，为O(n^2)
插入边或弧都比较容易，但是插入顶点不容易

邻接表

邻接表定义分为两部分：边链表和顶点表

• 边链表：与顶点V关联的所有边组成一个链表，称为顶点V的边链表
• 顶点表：用顺序存储方式存储图的顶点表V1，V2，…，Vn，表示每一个顶点的结构。

邻接表的类型实现

typedef struct ArcNode {    // 边表的存储类型
    int adjvex; // 该弧所指向的顶点的位置
    VRType adj;
    struct ArcNode *nextarc;    // 指向下一条弧的指针
    InfoType *info; // 该弧相关信息的指针
} ArcNode;

typedef struct vnode {  // 顶点表的存储类型
    vertexxtype data;   // 存储该顶点的信息
    ArcNode *firstArc;  // 指向第一条依附于该顶点的弧，其实是一段边链表
} vNode, adjList[M];

typedef struct {    // 图的邻接表存储类型
    adjList vertices;   // 邻接表的顶点表
    int vexNum, arcNum;
    int kind;   // 存储图的种类标志
} ALGraph;

十字链表

图的遍历

概念————从图的某一个顶点出发，访问图中的所有顶点，且每一个顶点仅访问一次。一般可分为两种方法：广度优先搜索、深度优先搜索。

深度优先搜索

算法基本思想

1. 首先访问图中某一个顶点Vi，以该顶点为出发点；
2. 任选一个与该顶点Vi【邻接】的【未被访问】的顶点Vj，访问之；
3. 以Vj为新的出发点继续进行深度优先搜索，直到图中所有和Vi有路径的顶点均被访问到。

代码实现

对非连通图进行深度优先遍历

首先将图中每一个顶点的访问标志设为FAlSE，之后搜索图中每一个顶点，如果未被访问，就以之为起始点进行深度优先搜索；否则继续检查下一顶点。

深度优先搜索的应用

• 求深度优先生成树
• 判断图是否连通
• 求图的连通分量

广度优先搜索

算法思想

1. 首先访问图中某一个指定的出发点Vi
2. 然后依次访问Vi中的所有邻接点Vi1，Vi2，…，Vit；
3. 再依次以这些邻接点为顶点，访问各个顶点未被访问的邻接点，以此类推，直到图中所有顶点均被访问为止。

广度优先代码实现

广度优先搜索的应用

• 求广度优先生成树
• 判断图是否连通
• 求图的连通分量

图的连通性问题

无向图和有向图的连通性

通过广度优先搜索和深度优先搜索，都可以求出一张无向图的所有连通分量

最小生成树

对于网而言，各边权值（边长）总和最小的生成树称作最小生成树。
下面介绍几个求最小生成树的算法。

普里姆算法

从边入手，算法思路：

1. 算法开始时，设置U，T，U中存放初始顶点s，T为空集；
2. 找到与初始顶点s邻接的顶点，且连通它们的边是最短的，将该顶点入集合U，边入集合T；
3. 反复执行2，直到U=V时，算法终止。

克鲁斯卡尔算法

1. 从图中取最短边e，如果e所关联的两个顶点不在T的同一个连通分量中，则将该边加入T；
2. 从图中删除边e；
3. 重复1和2，直到T中有n-1条边。

有向无环图的应用

无环有向图被称作无环图，简称DAG图。
某些子工程必须在另外的一些子工程完成之后才能开始，对于整个工程与系统，人们主要关心的两方面问题：

• 工程能否顺利进行 ———— > 拓扑排序
• 完成整个工程所必须的最短时间 ———— > 关键路径

拓扑排序

相关概念

• 顶点活动网（AOV网）：将顶点表示活动，边表示活动之间的关系的网称为顶点活动网。
• 拓扑序列

拓扑排序特点

• 一个有向图的拓扑序列不一定唯一
• 通过构造拓扑序列，可判断AOV网是否存在环
• 有向无环图一定存在拓扑序列

拓扑排序基本思想

1. 从有向图中选择一个入度为零的顶点输出
2. 从图中删除该顶点及其所有出边
3. 重复执行1和2，直到全部顶点均已输出，或者图中剩余顶点的入度均不为零（此时说明图中有回路）

拓扑排序算法概要

关键路径

关键路径相关概念

1. 事件vi的最早发生时间
   从源点v1到vi的最长路径长度，记作ve(i);
2. 事件vk的最迟发生时间
   即vn的最早发生时间ve(n)减去vk到vn的最长路径长度，记作vl(k)
3. 活动的最早开始时间，是vi的最早开始时间,
   最晚开始时间，是vj的最迟开始时间减去的持续时间，记作el(i)。

最短路径问题

迪杰斯特拉算法

Dijkstra算法思想

• 按路径长度的递增次序，逐步产生最短路径
• 首先求出离源点路径长度最短的点，再参照它求出离源点次短的点，以此类推
• 注意：权值不能为负，否则该算法失效

Dijkstra算法概要

1. 引入辅助数组D[]，D[i]表示当前找到的源点到每一个终点i的最短路径长度，
   引入辅助数组final[]，final[i]=1表示顶点i的最短路径已求
   出，初始状态下final[v0]置为1，其他置为0;
2. 选择D[]中路径最小值的顶点v（final[v]必须为0），v就是当前求得的一条从v出发的最短路径的终点，并修改final[v]=1;
3. 修改未求出最短路径的顶点的最短路径长度，对于顶点w，若
   D[v]+G.arcs[v][w] < D[w],
   则修改 D[w]=D[v]+G.arcs[v][w],
   同时修改P[w]=v;
4. 重复操作2、3 n-1次，求得递增序列。

Dijkstra算法分析

时间复杂度体现在修改距离值和最小值，为O(n^2),
空间复杂度体现在两个辅助数组，为O(n)。

弗洛伊德算法

时间复杂度体现在三重循环，为O(n^3),
空间复杂度体现在使用了二维数组，为O(n^2)。