第八章 图
图的基本概念
图定义：
图是由顶点集合及顶点间的关系 集合组成的一种数据结构：
Graph＝( V, E )
V = { x | x 属于某个数据对象} 是顶点的有穷非空集 合；
E = {(x,y)|x,y 属于 V }或者{<x, y> | x, y属于 V && Path (x, y)} 是顶点之间关系的有穷集合，也叫做边(edge)集合。
Path (x, y)表示从 x 到 y 的一条单向通路, 它是有方向的。
有向图:
图G中的每条边都是有方向的；
无向图:
图G中的每条边都是无方向的；
完全图
图G任意两个顶点都有一条边相连接
若有 n 个顶点的无向图有 n(n-1)/2 条边, 则此图为 完全无向图。
有 n 个顶点的有向图有n(n-1) 条边, 则此图为完全有向图。
子图
设有两个图G＝(V, E) 和G'＝(V', E')。若V '含于V 且E'含于E, 则称图G'是图G的子图。
权
某些图的边具有与它相关的数, 称之为权。这种带 权图叫做网络。
邻接顶点
如果 (u, v) 是 E(G) 中的一条边， 则称 u 与 v 互为邻接顶点。
顶点的度
一个顶点v的度是与它相关联的边 的条数。记作TD(v)。在有向图中, 顶点的度 等于该顶点的入度与出度之和。
顶点 v 的入度是以 v 为终点的有向边的条数, 记作 ID(v);
顶点 v 的出度是以 v 为始点的有向边的条数, 记作 OD(v)。
路径
在图 G＝(V, E) 中, 若从顶点 vi 出发, 沿一些 边经过一些顶点 vp1, vp2, …, vpm，到达顶点vj。 则称顶点序列 (vi vp1 vp2 ... vpm vj) 为从顶点vi 到顶点 vj 的路径。
经过的边(vi, vp1)、(vp1, vp2)、..、(vpm, vj) 是 属于E的边。
路径长度
非带权图的路径长度是指此路径 上边的条数。带权图的路径长度是指路径 上各边的权之和。
简单路径
若路径上各顶点 v1, v2, ..., vm 均不 互相重复, 则称这样的路径为简单 路径。
回路
若路径上第一个顶点 v1 与最后一 个顶点vm 重合, 则称这样的路径为回路 或环。
连通图与连通分量
在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与 v2是连通的。如果图中任意一对顶点都是连通的, 则称 此图是连通图。非连通图的极大连通子图叫做连通分量。
强连通图与强连通分量
在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi 到vj和从vj到vi的路径, 则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。
生成树
一个连通图的生成树是其极小连通子图， 在 n 个顶点的情形下，有 n-1 条边。
两类图形不在本章讨论之列：有自环的图，多重图。
//图的抽象数据类型
class Graph { //对象: 由一个顶点的非空集合和一个边集合构成 //每条边由一个顶点对来表示。
public:
Graph(); //建立一个空的图
~Graph();
virturl void insertVertex (const T& vertex); //插入一个顶点vertex, 该顶点暂时没有入边 virtual void removeVertex (int v); //在图中删除顶点v和所有关联到它的边
virtual void insertEdge (int v1, int v2, int weight); //在图中插入一条边(v1, v2, w)
virtual void removeEdge (int v1, int v2); //在图中删去边(v1,v2)
bool IsEmpty();//若图中没有顶点, 则返回true, 否则false
T getWeight (int v1, int v2); //函数返回边 (v1,v2) 的权值
virtual int getFirstNeighbor (int v); //给出顶点 v 第一个邻接顶点的位置
virtual int getNextNeighbor (int v, int w);//给出顶点 v 的某邻接顶点 w 的下一个邻接顶点
virtual T getValue(int i);
virtual E getWeight(int v1, int v2) ;
int NumberOfVertices();
int NumberOfEdges();
};
图的存储表示
图的特点：非线性结构（m :n ）
顺序存储结构：
1）（多个顶点，无序可言）
2）但可用二维数组描述元素间关系。（ 邻接矩阵）
链式存储结构：可用多重链表
邻接表
邻接多重表
十字链表
重点介绍： 邻接矩阵(数组)表示法 邻接表(链式)表示法
邻接矩阵 (Adjacency Matrix)
表示图： 一个顶点表（记录各个顶点信息） 一个邻接矩阵（表示各个顶点之间关系）
设图 A = (V, E) 有 n 个顶点，则图的邻接矩阵是一个二维数组 A.Edge[n][n]，定义为：
A.Edge[i] [j]= 1 ,如果<i,j>∈E 或者（i,j）∈E
否则A.Edge[i] [j]=0
分析1：无向图的邻接矩阵是对称的；
分析2：顶点i 的度＝第 i 行 (列) 中1 的个数；
特别：完全图的邻接矩阵中，对角元素为0，其余全1。
注：在有向图的邻接矩阵中，第i行含义：以结点vi为尾的弧(即出度边）；第i列含义：以结点vi为头的弧(即入度边）。
分析1：有向图的邻接矩阵可能是不对称的。
分析2：顶点的出度=第i行元素之和，OD( Vi )= ∑ A.Edge[ i ] [j ]
顶点的入度=第i列元素之和。ID( Vi )=∑ A.Edge[ j ] [i ]
顶点的度=第i行元素之和+第i列元素之和,
网络的邻接矩阵
图的模板基类
在模板类定义中顶点数据类型是变量，边 的权值是变量。
因此数据类型参数表 <class T, class E> 中， T是顶点数据的类型，E是边上所附数据的 类型。
这个模板基类是按照最复杂的情况（即带 权无向图）来定义的，如果需要使用非带 权图，可改为 < class T>。
//图的模板基类
template <class T, class E> class Graph { //图的类定义
private:
T *VerticesList; //顶点表
E **Edge; //邻接矩阵
protected:
int maxVertices; //图中最大顶点数
int numVertices; //当前顶点数
int numEdges; //当前边数
//GraphKind kind //图的种类(这样不用分类定义)
int getVertexPos (T vertex); //给出顶点vertex在图中位置
public: //相关操作……
}
//用邻接矩阵表示的图的类定义
template <class T, class E>
class Graphmtx : public Graph<T, E>
{
friend istream& operator >> ( istream& in, Graphmtx<T, E>& G); //输入
friend ostream& operator << (ostream& out, Graphmtx<T, E>& G); //输出
private:
int getVertexPos (T vertex)
{ //给出顶点vertex在图中的位置
for (int i = 0; i < numVertices; i++)
if (VerticesList[i] == Vertex) return i;
return -1; };
public:
Graphmtx (int sz = DefaultVertices); //构造函数
～Graphmtx () //析构函数
{ delete [ ]VerticesList; delete [ ]Edge; }
T getValue (int i) { //取顶点 i 的值, i 不合理返回0
return i >= 0 && i <= numVertices ? VerticesList[i] : NULL; }
E getWeight (int v1, int v2) { //取边(v1,v2)上权值
return v1 != -1 && v2 != -1 ? Edge[v1][v2] : 0; }
int getFirstNeighbor (int v); //取顶点 v 的第一个邻接顶点
int getNextNeighbor (int v, int w); //取 v 的邻接顶点 w 的下一邻接顶点
bool insertVertex (const T vertex); //插入顶点vertex
bool insertEdge (int v1, int v2, E cost); //插入边(v1, v2),权值为cost
bool removeVertex (int v); //删去顶点 v 和所有与它相关联的边
bool removeEdge (int v1, int v2); //在图中删去边(v1,v2) };
template <class T, class E> Graphmtx<T, E>::Graphmtx (int sz) { //构造函数 maxVertices = sz;
numVertices = 0;
numEdges = 0;
int i, j;
VerticesList = new T[maxVertices]; //创建顶点表
Edge = (E **) new E *[maxVertices];
for (i = 0; i < maxVertices; i++)
Edge[i] = new E[maxVertices]; //邻接矩阵
for (i = 0; i < maxVertices; i++) //矩阵初始化
for (j = 0; j < maxVertices; j++)
Edge[i][j] = (i == j) ? 0 : maxWeight;
};
template <class T, class E> int Graphmtx<T, E>::getFirstNeighbor (int v) {
//给出顶点位置为v的第一个邻接顶点的位置,如果找不到, 则函数返回-1
if (v != -1) {
for (int col = 0; col < numVertices; col++)
if (Edge[v][col] && Edge[v][col] < maxWeight)
return col; }
return -1; };
template <class T, class E>
int Graphmtx<T, E>::getNextNeighbor (int v, int w) {
//给出顶点 v 的某邻接顶点 w 的下一个邻接顶点
if (v != -1 && w != -1) {
for (int col = w+1; col < numVertices; col++)
if (Edge[v][col] && Edge[v][col] < maxWeight)
return col; }
return -1; };
邻接矩阵法优点：容易实现图的操作，如：求某顶点的度、判断 顶点之间是否有边（弧）、找顶点的邻接点等等。
邻接矩阵法缺点：n个顶点需要 n*n 个单元存储边(弧);空间效率 为O(n^2)。 对稀疏图而言尤其浪费空间。
为此需把邻接矩阵的各行分别组织为一个单链表
图的邻接表存储结构
在邻接表表示法中
•顶点：通常按编号顺序将顶点数据存储在一维数组中
•关联同一顶点的边：用单链表存储
无向图的邻接表
顶点的度：统计某顶点对应边链表中结点个数。
某条边(vi, vj)在邻接表中有两个边结点，分别 在第 i 个顶点和第 j 个顶点对应的边链表中。
有向图的邻接表和逆邻接表
特性总结：
图中有 n 个顶点，e 条边，
邻接表表示无向图时，需要 n 个顶点结点，2e 个边结点；
用邻接表表示有向图时，若不考虑逆邻接表，只需 n 个顶点结点，e 个边结点。
当 e 远远小于 n2 时，可以节省大量的存储空 间。
怎样计算无向图顶点的度？
TD(Vi) =单链表中链接的结点个数
怎样计算有向图顶点的出度？
OD(Vi)＝单链出边表中链接的结点数
怎样计算有向图顶点的入度？
ID(Vi) ＝邻接点为Vi的弧个数
怎样计算有向图顶点Vi的度：
TD(Vi) = OD( Vi )+ID( Vi )
邻接表的优点： 空间效率高；容易寻找顶点的邻接点；
邻接表的缺点： 判断两顶点间是否有边或弧， 需搜索两结点对应的单链表，没有邻接矩阵方便。
网络 (带权图) 的邻接表
统计出边表中结点个数，得到该顶点的出度；
统计入边表中结点个数，得到该顶点的入度。
单链表结点中包含另一顶点的下标 dest 和指针 link。对于带权图，边结点中还要 保存该边的权值cost。
用邻接表表示的图的类定义
template <class T, class E> struct Edge
{ //边结点的定义
int dest; //边的另一顶点位置
E cost; //边上的权值
Edge<T, E> *link; //下一条边链指针
Edge () {} //构造函数
Edge (int num, E cost): dest (num), weight (cost), link (NULL) { } //构造函数
bool operator != (Edge<T, E>& R) const
{ return dest != R.dest; } //判边等否
};
template <class T, class E> struct Vertex { //顶点的定义
T data; //顶点的名字
Edge<T, E> *adj; //边链表的头指针
};
template <class T, class E>
class Graphlnk : public Graph<T, E>
{ //图的类定义
private:
Vertex<T, E> *NodeTable;//顶点表 (各边链表的头结点)
protected:
int maxVertices; //图中最大顶点数
int numVertices; //当前顶点数
int numEdges; //当前边数
int getVertexPos (const T vertx) { //给出顶点vertex在图中的位置
for (int i = 0; i < numVertices; i++)
if (NodeTable[i].data == vertx) return i;
return -1; }
public:
Graphlnk (int sz = DefaultVertices); //构造函数
~Graphlnk(); //析构函数
T getValue (int i) { //取顶点 i 的值
return (i >= 0 && i < NumVertices) ? NodeTable[i].data : 0;
}
E getWeight (int v1, int v2); //取边(v1,v2)权值
bool insertVertex (const T& vertex);
bool removeVertex (int v);
bool insertEdge (int v1, int v2, E cost);
bool removeEdge (int v1, int v2);
int getFirstNeighbor (int v);
int getNextNeighbor (int v, int w);
friend istream& operator >> (istream& in, Graphlnk<T, E>& G);
friend ostream& operator << (ostream& out, Graphlnk<T, E>& G);
};
template <class T, class E> Graphlnk<T, E>::Graphlnk (int sz) {
//构造函数：建立一个空的邻接表
maxVertices = sz;
numVertices = 0;
numEdges = 0;
NodeTable = new Vertex<T, E>[maxVertices]; //创建顶点表数组
if (NodeTable == NULL)
{ cerr << "存储分配错！" << endl; exit(1); }
for (int i = 0; i < maxVertices; i++)
NodeTable[i].adj = NULL; };
template <class T, class E> Graphlnk<T, E>::～Graphlnk() {
//析构函数：删除一个邻接表
for (int i = 0; i < numVertices; i++ ) {
Edge<T, E> *p = NodeTable[i].adj;
while (p != NULL)
{
NodeTable[i].adj = p->link;
delete p; p = NodeTable[i].adj; }
} delete [ ]NodeTable;
//删除顶点表数组 };
template <class T, class E>
int Graphlnk<T, E>::getFirstNeighbor (int v) {
//给出顶点位置为 v 的第一个邻接顶点的位置,果找不到, 则函数返回-1
if (v != -1) { //顶点v存在
Edge<T, E> *p = NodeTable[v].adj; //对应边链表第一个边结点
if (p != NULL) return p->dest; //存在, 返回第一个邻接顶点
}
return -1; //第一个邻接顶点不存在
};
template <class T, class E> int Graphlnk<T, E>::getNextNeighbor (int v, int w)
{ //给出顶点v的邻接顶点w的下一个邻接顶点的位置,若没有下一个邻接顶点, 则函数返回-1
if (v != -1) { //顶点v存在
Edge<T, E> *p = NodeTable[v].adj;
while (p != NULL && p->dest != w)
p = p->link;
if (p != NULL && p->link != NULL)
return p->link->dest; //返回下一个邻接顶点
}
return -1; //下一邻接顶点不存在
};
图的遍历与连通性
从已给的连通图中某一顶点出发，沿着一些边访遍图 中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历 (Graph Traversal)。
图的遍历操作是求解图的连通性问题、拓扑排序等问题的基础。
遍历方法:
深度优先遍历DFS (Depth First Search)
广度优先遍历BFS (Breadth First Search)
遍历实质：
找每个顶点的邻接点的过程。
图的特点：
图中可能存在回路，且图的任一顶点都 可能与其它顶点相通，在访问完某个顶点之后可能 会沿着某些边又回到了曾经访问过的顶点。
怎样避免重复访问？
解决思路：可设置一个辅助数组 visited [n ]，用来 标记每个被访问过的顶点。它的初始状态为0，在图的遍历过程中，一旦某一个顶点i 被访问，就立即改 visited [i]为1，防止它被多次访问。
深度优先搜索DFS (Depth First Search)
深度优先遍历图的方法是，从图中某顶点v出发：
(1)访问顶点v；
(2)依次从v的未被访问的邻接点出发，对图进行深度优先 遍历；直至图中和v有路径相通的顶点都被访问；
(3)若此时图中尚有顶点未被访问，则从一个未被访问的 顶点出发，重新进行深度优先遍历，直到图中所有顶点 均被访问过为止。对非连通 图
深度优先搜索遍历类似于树的先序遍历。
深度优先遍历过程是递归的，在遍历过程中，若 某个顶点的所有邻接顶点均被访问过，则需要回溯。
//连通图的深度遍历
template<class T, class E>
void DFS (Graph<T, E>& G, int v, bool visited[]) {
cout << G.getValue(v) << ' '; //访问顶点v
visited[v] = true; //作访问标记
int w = G.getFirstNeighbor (v); //第一个邻接顶点
while (w != -1) { //若邻接顶点w存在
if ( !visited[w] ) DFS(G, w, visited); //若w未访问过, 递归访问顶点w
w = G.getNextNeighbor (v, w); //下一个邻接顶点 }
};
//图的深度优先搜索算法
template<class T, class E>
void DFSTraverse (Graph<T, E>& G, const T& v) {
//从顶点v出发对图G进行深度优先遍历的主过程
int i, loc, n = G.NumberOfVertices(); //顶点个数
bool *visited = new bool[n]; //创建辅助数组
for (i = 0; i < n; i++) visited [i] = false; //辅助数组初始化
loc = G.getVertexPos(v);
DFS (G, loc, visited); //从顶点0开始深度优先搜索
delete [] visited; //释放visited
};
广度优先搜索BFS (Breadth First Search)
基本思想：——仿树的层次遍历过程。
广度优先搜索（遍历）步骤：
简单归纳：
①访问了起始点v之后，
②依次访问 v的邻接点。
③然后再依次访问这些顶点的未被访问过的邻接点； 直到所有顶点都被访问过为止。 （连通图）
若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止（非连通图）
计算机如何实现BFS？
除辅助数组visited [n ]外，还需再开一辅助队列
(1)首先访问顶点v，并将其访问标志置为已被访问，即visited[v]=1，并入队；
(2)接着依次访问与顶点v有边相连的所有未访问顶点W1， W2，…，Wt，并入队；
(3)然后再按顺序访问与W1，W2，…，Wt有边相连又未曾访 问过的顶点；
依此类推，直到图中所有顶点都被访问完为止 。
//图的广度优先搜索算法
template <class T, class E>
void BFS (Graph<T, E>& G, const T& v) {
int i, w, n = G.NumberOfVertices(); //图中顶点个数
bool *visited = new bool[n];
for (i = 0; i < n; i++) visited[i] = false;
int loc = G.getVertexPos (v); //取顶点号
cout << G.getValue (loc) << ' '; //访问顶点v
visited[loc] = true; //做已访问标记
Queue<int> Q; Q.EnQueue (loc); //顶点进队列, 实现分层访问 图的广度优先搜索算法
while (!Q.IsEmpty() ) { //循环, 访问所有结点
Q.DeQueue (loc);
w = G.getFirstNeighbor (loc); //第一个邻接顶点
while (w != -1) { //若邻接顶点w存在
if (!visited[w]) { //若未访问过
cout << G.getValue (w) << ‘ ’; //访问
visited[w] = true;
Q.EnQueue (w); //顶点w进队列
}
w = G.getNextNeighbor (loc, w); //找顶点loc的下一个邻接点
}
} //外层循环，判队列空否
} // 如果对于非联通的图
delete [] visited;
};
连通分量 (Connected component)
当无向图为非连通图时，从图中某一顶点出发，利 用深度优先搜索算法或广度优先搜索算法不可能遍 历到图中的所有顶点，只能访问到该顶点所在最大 连通子图（连通分量）的所有顶点。
若从无向图每一连通分量中的一个顶点出发进行遍 历, 可求得无向图的所有连通分量。
例如，对于非连通的无向图，所有连通分量的生成 树组成了非连通图的生成森林。
最小生成树
对连通图进行遍历，得到的是什么？
——得到的将是一个极小连通子图，即图的生成树！ 由深度优先搜索得到的，称为深度优先搜索生成树。 由广度优先搜索得到的，称为广度优先搜索生成树。
对非连通图进行遍历，得到的是什么？
—— 得到的是各连通分量的生成树，即图的生成森林
求解步骤：
Step1:先用邻接矩阵或邻接表表示；
Step2:写出DFS或BFS结果序列；
Step3:画出对应生成树或森林。
最小代价生成树
在一个连通网的所有生成树中， 各边的代价之和 最小的那棵生成树。简称为最小生成树(MST)。
构造最小生成树的准则：
- 必须使用且仅使用n-1条边来联结网络中的n个顶点
- 不能使用产生回路的边。
- 各边上的权值的总和达到最小。
典型用途：
欲在n个城市间建立通信网，则n个城市应铺n-1条线路； 但因为每条线路都会有对应的经济成本，而n个城市至多可 能有n(n-1)/2 条线路，那么，如何选择n–1条线路，使总 费用最少？
数学模型： 顶点———表示城市，有n个； 边————表示线路，有n–1条； 边的权值—表示线路的经济代价； 连通网——表示n个城市间通信网。
下面仅讨论无向网的最小生成树问题。
有多种算法，但最常用的是以下两种：
Prim（普里姆）算法： 将顶点归并，与边数无关，适于稠密网
Kruskal（克鲁斯卡尔）算法： 将边归并，适于求稀疏网的最小生成树
这两个算法，都是利用MST 性质来构造最小生成树的 。
MST性质
假设G=(V, E)是一个无向连通网，U是顶点集V的一 个非空子集。若(u, v)是一条具有最小权值的边，其 中u∈U，v∈V－U，则必存在一棵包含边(u, v)的最 小生成树。
克鲁斯卡尔 (Kruskal) 算法
克鲁斯卡尔算法的基本思想：
设有一个有 n 个顶点的连通网络 N = { V, E }, 最初先构造一 个只有 n 个顶点, 没有边的非连通图 T = { V, Ø }, 图中每个顶 点自成一个连通分量。
当在 E 中选到一条具有最小权值的边时, 若该边的两个顶点 落在不同的连通分量上，则将此边加入到 T 中。
如此重复下去, 直到所有顶点在同一个连通分量上为止。
不用最小堆的算法实现：
//顶点结点：
typedef struct
{ int data; //顶点信息
int jihe;
}VEX;
//边结点
typedef struct
{ int tail, head; //边依附的两顶点
int cost; //边的权值
int flag; //标志域
}EDGE;
0）用顶点数组和边数组存放顶点和边信息
1）初始时，令每个顶点的集合互不相同；每个边的flag为0
2）选出权值最小且flag为0的边
3）若该边依附的两个顶点的集合值不同，即非连通，则令该边的flag=1, 选中该边；再令该边依附的两顶点的集合以及两集合中所有顶点的集合 相同 若该边依附的两个顶点的集合值相同，即连通，则令该边的flag=2, 即舍去该边
4）重复上述步骤，直到选出n-1条边为止
算法的框架
利用最小堆(MinHeap)和并 查集(DisjointSets)来实现克鲁斯卡尔算法
首先, 利用最小堆来存放E中的所有的边, 并选出最小边
利用并查集的运算检查两顶点是否在同一连通分量 上。
//最小生成树类定义
const float maxValue = FLOAT_MAX //机器可表示的、问题中不可能出现的大数
template <class T, class E>
struct MSTEdgeNode { //树边结点的类定义
int tail, head; //两顶点位置
E cost; //边上的权值
MSTEdgeNode() : tail(-1), head(-1), cost(0) { } //构造函数
};
template <class T, class E>
class MinSpanTree { //树的类定义
protected:
MSTEdgeNode<T, E> *edgevalue; //边值数组
int maxSize, n; //最大元素个数和当前个数
public:
MinSpanTree (int sz = DefaultSize-1) : MaxSize (sz), n (0)
{
edgevalue = new MSTEdgeNode<T, E>[sz];
}
int Insert (MSTEdgeNode& item);
};
在求解最小生成树时，可以用邻接矩阵存储图， 也可以用邻接表存储图。算法中使用图的抽象 基类的操作，无需考虑图及其操作的具体实现。
Kruskal算法的实现
#include "heap.h"
#include "UFSets.h"
template <class T, class E>
void Kruskal (Graph<T, E>& G, MinSpanTree<T, E>& MST) {
MSTEdgeNode<T, E> ed; //边结点辅助单元
int u, v, count;
int n = G.NumberOfVertices(); //顶点数
int m = G.NumberOfEdges(); //边数
MinHeap <MSTEdgeNode<T, E>> H(m); //最小堆
UFSets F(n); //并查集
for (u = 0; u < n; u++)
for (v = u+1; v < n; v++) //无向连通图
if (G.getWeight(u,v) != maxValue) {
ed.tail = u; ed.head = v; //插入堆
ed.cost = G.getWeight (u, v);
H.Insert(ed);
}
count = 1; //最小生成树边数计数
while (count < n) { //反复执行, 取n-1条边
H.Remove(ed); //退出具最小权值的边
u = F.Find(ed.tail); v = F.Find(ed.head);//取两顶点所在集合的根u与v
if (u != v) { //不是同一集合,不连通
F.Union(u, v); //合并,连通它们
MST.Insert(ed); //该边存入MST
count++;
} }
}；
普里姆(Prim)算法
普里姆算法的基本思想：
从连通网络 N = {V, E}中的某一顶点 u0 出发, 选择与 它关联的具有最小权值的边 (u0, v), 将其顶点加入到 生成树顶点集合U中。
以后每一步从一个顶点在集合U中, 而另一个顶点不 在集合U中的各条边中选择权值最小的边(u, v), 把它 的顶点加入到集合U中。
如此继续下去, 直到网络中的所有顶点都加入到生 成树顶点集合U中为止。
注意：当各边有相同权值时，由于选择的随意 性，产生的生成树可能不唯一。
Prim算法的实现
#include "heap.h"
template <class T, class E>
void Prim (Graph<T, E>& G, const T u0,MinSpanTree<T, E>& MST) {
MSTEdgeNode<T, E> ed; //边结点辅助单元
int i, u, v, count;
int n = G.NumberOfVertices(); //顶点数
int m = G.NumberOfEdges(); //边数
int u = G.getVertexPos(u0); //起始顶点号
MinHeap <MSTEdgeNode<T, E>> H(m); //最小堆
bool Vmst = new bool[n]; //最小生成树顶点集合
for (i = 0; i < n; i++) Vmst[i] = false;
Vmst[u] = true; //u 加入生成树
count = 1;
do { //迭代
v = G.getFirstNeighbor(u);
while (v != -1) { //检测u所有邻接顶点
if (!Vmst[v]) { //v不在mst中
ed.tail = u; ed.head = v;
ed.cost = G.getWeight(u, v);
H.Insert(ed); //(u,v)加入堆
} //堆中存所有u在mst中, v不在mst中的边
v = G.getNextNeighbor(u, v);
}
while (!H.IsEmpty() && count < n) {
H.Remove(ed); //选堆中具最小权的边
if (!Vmst[ed.head]) {
MST.Insert(ed); //加入最小生成树
u = ed.head; Vmst[u] = true; //u加入生成树顶点集合
count++;
break; //找找未曾加入的边入栈
} }
} while (count < n);
};
Prim算法（只用数组记录最值当前状态）自学
void MiniSpanTree_PRIM(MGraph G, VertexType u) {
// 用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T 的各条边。
// 记录从顶点集U到V－U的代价最小的边的辅助数组定义：
// struct {
// VertexType adjvex;
// VRType lowcost;
// } closedge[MAX_VERTEX_NUM];
int i,j,k;
k = LocateVex ( G, u );
for ( j=0; j<G.vexnum; ++j ) {
// 辅助数组初始化
if (j!=k)
{ closedge[j].adjvex=u;
closedge[j].lowcost=G.arcs[k][j].adj; }
}
closedge[k].lowcost = 0; // 初始，U＝{u}
for (i=1; i<G.vexnum; ++i) { // 选择其余G.vexnum-1个顶点
k = minimum(closedge); // 求出T的下一个结点：第k顶点
//此时closedge[k].lowcost =
//MIN{ closedge[vi].lowcost | closedge[vi].lowcost>0, vi∈V-U }
printf(closedge[k].adjvex, G.vexs[k]); // 输出生成树的边
closedge[k].lowcost = 0; // 第k顶点并入U集
for (j=0; j<G.vexnum; ++j)
if (G.arcs[k][j].adj < closedge[j].lowcost) {
// 新顶点并入U后重新选择最小边
// closedge[j] = { G.vexs[k], G.arcs[k][j].adj };
closedge[j].adjvex=G.vexs[k];
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
} // MiniSpanTree
显然， Prim算法的时间效率＝O（n^2）
两种算法比较
Prim：从某一个顶点出发寻找到其他顶点 最小了分支（与顶点有关）
Kruscal：先对边排序，再测试连通（与边有关）
最短路径
最短路径问题：如果从图中某一顶点（称为源 点）到另一顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边 上的权值总和达到最小。
问题解法 :边上权值非负情形的单源最短路径问题 — Dijkstra算法
典型用途：交通问题。如：城市A到城市B有多条线路， 但每条线路的交通费（或所需时间）不同，那么，如何 选择一条线路，使总费用（或总时间）最少？ （注：最短路径与最小生成树不同，路径上不一定包含n 个顶点）
问题抽象：在带权有向图中A点（源点）到达B点（终点） 的多条路径中，寻找一条各边权值之和最小的路径，即 最短路径.
边上权值非负情形的 单源最短路径问题
目的： 设一有向图G=（V, E），已知各边的权值， 以某指定点v0为源点，求从v0到图的其余各点的最短 路径。限定各边上的权值大于或等于0。
Dijkstra提出按路径长度的递增次序, 逐步产生最短 路径的算法。
假设S是已求得的最短路径的终点的集合，则可 证明：下一条最短路径必然是从v0 出发，中间只经过S 中的顶点便可到达的那些顶点vx (vxV-S )的路 径中路径长度值最小的一条。逐步扩充S,将终点加入集合S中。
Dijkstra 算法的基本步骤
-
设V0是起始源点，S是已求得最短路径的终点集合。 1) V-S = 未确定最短路径的顶点的集合， 初始时 S={V0}
-
选择下一条长度最短的路径：
① Vi V - S ，求出V0 到Vi 中间只经 S 中顶点的最短 路径；
② 上述最短路径中长度最小者即为下一条长度最短的路径
③ 将所求最短路径的终点加入S 中，并作调整；
- 重复2）直到求出所有终点的最短路径
数据结构描述
1 引入辅助数组dist[]
dist[]:存放当前找到的从源点V0到每个终点的最短路径长度
初始状态： 若从v0到顶点vi有边, 则dist[i]为该边的权值； 若从v0到顶点vi无边, 则dist[i]为 ∞
每次求得一条最短路径后, 其终点vk 加入集合S，然后对所有的vi V-S，修改其 dist[i]值
2 s[]: 存放点是否已确定最短路径的状态
3 path[]:表示从V0到各终点的最短路径上，此顶点的前一顶 点的序号；若从V0到某终点无路径，则用0作为其前一顶 点的序号。
算法描述：
（1）S为已找到从源点v0出发的最短路径的终点集合，初始为{v0}. 辅助数组 dist [ n ]存储各终点当前找到的最短路径的长度
（2）选择u，使得<v0,u>是这些路径中长度最短的路径，加入已求 的最短路径的点集合
dist [ u ]＝min{dist[i] | i∈V-S } // i是S集之外的顶点
// dist[u]是从源点v0到S集外所有顶点的弧中最短的一条
S= S ∪{u} //将u加入S集
（3）对于所有不在S中的终点w，进行路径调整： dist[u]+ A[u,i]< dist[i] // 即(v0,u)＋(u,i)<(v0,i) 则修改dist[i]为： dist[i]＝ dist[u]+ A[u,i]
重复操作（2）、（3）共n-1次，由此求得从v0到各终点的最短路径。
从单个顶点到其他各顶点最短路径的算法
void ShortestPath (Graph<T, E>& G, T v, E dist[], int path[]) {
int n = G.NumberOfVertices();
bool *S = new bool[n]; //最短路径顶点集
int i, j, k; E w, min;
for (i = 0; i < n; i++) {
dist[i] = G.getWeight(v, i);
S[i] = false;
if (i != v && dist[i] < maxValue) path[i] = v;
else path[i] = -1;
S[v] = true; dist[v] = 0; //顶点v加入顶点集合
for (i = 0; i < n-1; i++) { //求解各顶点最短路径
min = maxValue; int u = v;
for (j = 0; j < n; j++)
if (!S[j] && dist[j] < min)
{ u = j; min = dist[j];} //将源点V加 入S后, 初始化剩 余点的当前路径
S[u] = true//将顶点u加入集合S
for (k = 0; k < n; k++) {
w = G.GetWeight(u, k); //然后对其余各点路径 进行适当调整：,并记 录每个点的前驱
if (!S[k] && w < maxValue &&
dist[u]+w < dist[k]) {
dist[k] = dist[u]+w;
path[k] = u;
} } }
};
活动网络
用顶点表示活动的网络 (AOV网络)
计划、施工过程、生产流程、程序流程等都是“工 程”。除了很小的工程外，一般都把工程分为若干 个叫做“活动”的子工程。完成了这些活动，这个 工程就可以完成了。
例如，计算机专业学生的学习就是一个工程，每一 门课程的学习就是整个工程的一些活动。其中有些 课程要求先修课程，有些则不要求。这样在有的课 程之间有领先关系，有的课程可以并行地学习。
可以用有向图表示一个工程。在这种有向图中， 用顶点表示活动，用有向边<Vi, Vj>表示活动Vi 必须先于活动Vj 进行。这种有向图叫做顶点表 示活动的AOV网络 (Activity On Vertices)。
拓扑排序
问题：
假设以有向图表示一个工程的施工图或程 序的数据流图，则图中不允许出现回路
如何检查有向图中是否存在回路的方法之 一，是对有向图进行拓扑排序。
什么是拓扑排序：
对有向图进行如下操作： 按照有向图给出的次序关系，将图中顶点排成一个线 性序列，对于有向图中没有限定次序关系的顶点，则 可以人为加上任意的次序关系。 由此所得顶点的线性序列称为拓扑有序序列构造有向图的一个拓扑序列的过程称为拓扑排序。
若该线性序列中包含AOV网全部顶点，则AOV网无环，否 则，AOV网中存在有向环，此AOV网络所代表的工程是不 可行的。
进行拓扑排序的方法
① 输入AOV网络。令 n 为顶点个数。
② 在AOV网络中选一个没有直接前驱的顶点, 并 输出之;
③ 从图中删去该顶点, 同时删去所有它发出的有 向边;
④ 重复以上 ②、③步, 直到 全部顶点均已输出，拓扑有序序列形成， 拓扑排序完成；或 图中还有未输出的顶点, 但已跳出处理循环。 说明图中还剩下一些顶点, 它们都有直接前 驱。这时网络中必存在有向环。
在邻接表中增设一个数组count[]，记录各顶点入 度。入度为零的顶点即无前驱顶点。
在输入数据前, 顶点表NodeTable[]和入度数组 count[]全部初始化。在输入数据时, 每输入一条 边<j, k>, 就需要建立一个边结点, 并将它链入相 应边链表中, 统计入度信息：
Edge * p = new Edge< int > (k); //建立边结点, dest 域赋为 k
p->link = NodeTable[j].adj;
NodeTable[j].adj = p; //链入顶点j的边链表的前端
count[k]++; //顶点k入度加一
在算法中, 使用一个存放入度为零的顶点的链 式栈, 供选择和输出无前驱的顶点。
拓扑排序算法可描述如下：
1、建立入度为零的顶点栈;
2、当入度为零的顶点栈不空时, 重复执行
从顶点栈中退出一个顶点, 并输出之;
从AOV网络中删去这个顶点和它发出的 边, 边的终顶点入度减一;
如果边的终顶点入度减至0, 则该顶点进 入度为零的顶点栈;
3、如果输出顶点个数少于AOV网络的顶点 个数, 则报告网络中存在有向环。
在算法实现时, 为了建立入度为零的顶点栈,可 以不另外分配存储空间, 直接利用入度为零的 顶点的count[ ]数组元素。设立一个栈顶指针 top, 指示当前栈顶位置, 即某一个入度为零的 顶点。栈初始化时置top = -1。
//将顶点i 进栈时执行以下指针的修改：
count[i] = top; top = i ; // top指向新栈顶i, 原栈顶元素在count[i]中
//退栈操作可以写成：
j = top; top = count[top]; //位于栈顶的顶点记于 j, top退到次栈顶
拓扑排序的算法
template <class T, class E>
void TopologicalSort (Graph<T, E>& G)
{ int i, j, w, v;
int top = -1; //入度为零顶点的栈初始化
int n = G.NumberOfVertices(); //网络中顶点个数
int *count = new int[n]; //入度数组兼入度为零顶点栈
for (i = 0; i < n; i++) count[i] = 0;
cin >> i >> j; //输入一条边(i, j)
while (i > -1 && i < n && j > -1 && j < n) {
G.insertEdge (i, j);
count[j]++;
cin >> i >> j; }
for (i = 0; i < n; i++) //初始化，检查网络所有顶点
if (count[i] == 0) //入度为零的顶点进栈
{ count[i] = top; top = i; }
for (i = 0; i < n; i++) //期望输出n个顶点
if (top == -1) { //中途栈空,转出
cout << “网络中有回路！" << endl;
return;
}
else
{ //继续拓扑排序
v = top; top = count[top]; //退栈v
cout << G.getValue(v) << " " << endl; //输出
w = G.GetFirstNeighbor(v);
while (w != -1) { //扫描顶点v的出边表
count[w]--; //邻接顶点入度减一
if (!count[w])
{ count[w] = top; top = w; } //入度减至零,进栈
w = G.GetNextNeighbor (v, w);
} //一个顶点输出后，调整其邻接顶点入度
}
};
分析此拓扑排序算法可知，如果AOV网络有 n个顶点，e条边，在拓扑排序的过程中，搜 索入度为零的顶点，建立链式栈所需要的时 间是O(n)。在正常的情况下，有向图有n个顶 点，每个顶点进一次栈，出一次栈，共输出 n 次。顶点入度减一的运算共执行了e次。所 以总的时间复杂度为O(n+e)。
用边表示活动的网络(AOE网络)
用一个带权有向图（DAG）描述工程的预计进度。
顶点表示事件，有向边表示活动，边e的权c(e） 表示完成活动e所需的时间(比如 天数）。
图中入度为0的顶点表示工程的开始事件（如开工 仪式），出度为0的顶点表示工程结束事件。
关键路径
从AOE网中源点到汇点的最长路径，具有最大长 度的路径叫关键路径。
关键路径是由关键活动构成的，关键路径可能不唯一。
关键路径为源点到汇点的最长路径，这样转变为查找图中最长路径问题。
求一个AOE的关键路径 即 求AOE的中的关键活动
用边表示活动的网络(AOE网络)
如果在无有向环的带权有向图中, 用有向边表 示一个工程中的活动 (Activity), 用边上权值表 示活动持续时间 (Duration), 用顶点表示事件 (Event), 则这样的有向图叫做用边表示活动的 网络, 简称 AOE ( Activity On Edges ) 网络。
AOE网络在某些工程估算方面非常有用。例如，可以使人们了解：
完成整个工程至少需要多少时间(假设网络 中没有环)?
为缩短完成工程所需的时间, 应当加快哪些 活动?
从源点到各个顶点, 以至从源点到汇点的有向 路径可能不止一条。 这些路径的长度也可能 不同。 完成不同路径的活动所需的时间虽然 不同, 但只有各条路径上所有活动都完成了, 整 个工程才算完成。
因此, 完成整个工程所需的时间取决于从源点 到汇点的最长路径长度, 即在这条路径上所有 活动的持续时间之和。这条路径长度最长的路 径就叫做关键路径(Critical Path)。
要找出关键路径，必须找出关键活动, 即不按 期完成就会影响整个工程完成的活动。
关键路径上的所有活动都是关键活动。因此, 只要找到了关键活动, 就可以找到关键路径。 例如, 下图就是一个AOE网。
定义几个与计算关键活动有关的量
-
事件Vi 的最早可能开始时间Ve(i) 是从源点V0 到顶点Vi 的最长路径长度。
-
事件Vi 的最迟允许开始时间Vl[i] 是在保证汇点Vn-1 在Ve[n-1] 时刻完成的前提 下，事件Vi 的允许的最迟开始时间。
-
活动ak 的最早可能开始时间 e[k] 设活动ak 在边<Vi, Vj>上, 则e[k]是从源点V0 到 顶点Vi 的最长路径长度。因此, e[k] = Ve[i]。
-
活动ak 的最迟允许开始时间 l[k]，l[k]是在不会引起时间延误的前提下, 该活动 允许的最迟开始时间。 l[k] = Vl[j]-dur(<i, j>)。 其中, dur(<i, j>)是完成 ak 所需的时间。
-
时间余量 l[k]-e[k]
表示活动ak的最早可能开始时间和最迟允许 开始时间的时间余量。l[k] == e[k]表示活动 ak 是没有时间余量的关键活动。
为找出关键活动, 需要求各个活动的 e[k] 与 l[k]，以判别是否 l[k] == e[k]。
为求得e[k]与l[k], 需要先求得从源点V0到各个 顶点Vi 的Ve[i]和Vl[i]。
求Ve[i]的递推公式，从 Ve[0] = 0 开始，向前递推 ， Ve[j]=max{ Ve[i]+dur(< Vi , Vj>)}, < Vi, Vj > ∈S2, j = 1, 2, ... , n-1 。 S2 是所有指向Vj 的有向边<Vi,Vj>的集合。
从Vl[n-1] = Ve[n-1]开始，反向递推 Vl [j]=min{ Vl[k]-dur(< Vj , Vk>)}, < Vj, Vk > ∈S1, j = 1, 2, ... , n-1 。 S1 是所有指向Vj 的有向边<Vj,Vk>的集合。
这两个递推公式的计算必须分别在拓扑有序及 逆拓扑有序的前提下进行。
设活动ak (k=1, 2, …, e)在带权有向边< Vi, Vj > 上, 其持续时间用dur (<Vi,Vj>)表示, 则有
e[k] = Ve[i]；
l[k] = Vl[j]-dur(<Vi,Vj>)；k = 1, 2, …, e。 这样就得到计算关键路径的算法。
为了简化算法, 假定在求关键路径之前已经对 各顶点实现了拓扑排序, 并按拓扑有序的顺序 对各顶点重新进行了编号。
求关键路径的过程
（1）事件的最早开始和最迟开始时间
事件v的最早开始时间：规定源点事件的最早开始时间为0。定义图中任 一事件v的最早开始时间（early event） ee(v)等于x、y、z到v所有路径长度的 最大值：
事件v的最迟开始时间：定义在不影响整个工程进度的前提下，事件v必 须发生的时间称为v的最迟开始时间（late event） ，记作le(v)。le(v)应等于 ee(y)与v到汇点的最长路径长度之差：
（2）活动的最早开始时间和最迟开始时间
活动a的最早开始时间e(a)指该活动起点x事件的最早开始时间，即： e(a)=ee(x)
活动a的最迟开始时间l(a)指该活动终点y事件的最迟开始时间与该 活动所需时间之差，即： l(a)=le(y)-c
（3）求关键活动
对于每个活动a，求出d(a)=l(a)-e(a)，若d(a)为0，则称活动a为关键活动。对关键活动来说，不存在富余时间。
利用关键路径法求AOE网的各关键活动
template <class T, class E>
void CriticalPath(graph<T, E>& G) {
int i, j, k; E Ae, Al, dur;
int n = G.NumberOfVertices();
E *Ve = new E[n];
E *Vl = new E[n];
for (i = 0; i < n; i++) Ve[i] = 0;
for (i = 0; i < n; i++) { //正向计算Ve[]
j = G.getFirstNeighbor(i);
while (j != -1) {
dur = G.getWeight (i, j);
if (Ve[i]+dur > Ve[j]) Ve[j] = Ve[i]+dur;
j = G.getNextNeighbor(i, j); }
} Vl[n-1] = Ve[n-1];
for (j = n-2; j > 0; j--) { //逆向计算Vl[]
k = G.getFirstNrighbor (j);
while (k != -1) {
dur = G.getWeight (j, k);
if (Vl[k]-dur < Vl[j]) Vl[j] = Vl[k]-dur;
k = G.getNextNeighbor (j, k);
} }
for (i = 0; i < n; i++) { //求各活动的e, l
j = G.getFirstNeighbor (i);
while (j != -1) {
Ae = Ve[i];
Al = Vl[k]-G.getWeight(i, j);
if (Al == Ae)
cout << "<" << G.getValue(i) << "," << G.getValue(j) << “>”<< "是关键活动" << endl;
j = G.getNextNeighbor (i, j);
}
} delete [] Ve;
delete [] Vl;
};
注意
所有顶点按拓扑有序的次序编号。
仅计算 Ve[i] 和 Vl[i] 是不够的，还须计算 e[k] 和 l[k]。
不是任一关键活动加速一定能使整个工程提前。 想使整个工程提前，要考虑各个关键路径上所 有关键活动。
如果任一关键活动延迟，整个工程就要延迟。