数据结构学习(C++)之图
2016-02-19 20:55
给自己一点时间接受自己,爱自己，趁着下午茶的时间来学习图老师推荐的数据结构学习(C++)之图，过去的都会过去，迎接崭新的开始，释放更美好的自己。
#define Graphmem_H#include vector
#include list
using namespace std;template class name, class dist, class mem class Network;const int maxV = 20;//最大节点数
template class name, class dist
class AdjMatrix
{
friend class Networkname, dist, AdjMatrixname, dist ;
public:
AdjMatrix() : vNum(0), eNum(0)
{
vertex = new name[maxV]; edge = new dist*[maxV];
for (int i = 0; i maxV; i++) edge[i] = new dist[maxV];
}
~AdjMatrix()
{
for (int i = 0; i maxV; i++) delete []edge[i];
delete []edge; delete []vertex;
}
bool insertV(name v)
{
if (find(v)) return false;
vertex[vNum] = v;
for (int i = 0; i maxV; i++) edge[vNum][i] = NoEdge;
vNum++; return true;
}
bool insertE(name v1, name v2, dist cost)
{
int i, j;
if (v1 == v2 !find(v1, i) !find(v2, j)) return false;
if (edge[i][j] != NoEdge) return false;
edge[i][j] = cost; eNum++; return true;
}
name& getV(int n) { return vertex[n]; } //没有越界检查
int nextV(int m, int n)//返回m号顶点的第n号顶点后第一个邻接顶点号，无返回-1
{
for (int i = n + 1; i vNum; i++) if (edge[m][i] != NoEdge) return i;
return -1;
}
private:
int vNum, eNum;
dist NoEdge, **edge; name *vertex;
bool find(const name& v)
{
for (int i = 0; i vNum; i++) if (v == vertex[i]) return true;
return false;
}
bool find(const name& v, int& i)
{
for (i = 0; i vNum; i++) if (v == vertex[i]) return true;
return false;
}
};template class name, class dist
class LinkedList
{
friend class Networkname, dist, LinkedListname, dist ;
public:
LinkedList() : vNum(0), eNum(0) {}
~LinkedList()
{
for (int i = 0; i vNum; i++) delete vertices[i].e;
}
bool insertV(name v)
{
if (find(v)) return false;
vertices.push_back(vertex(v, new listedge));
vNum++; return true;
}
bool insertE(const name& v1, const name& v2, const dist& cost)
{
int i, j;
if (v1 == v2 !find(v1, i) !find(v2, j)) return false;
for (listedge::iterator iter = vertices[i].e-begin();
iter != vertices[i].e-end() && iter-vID j; iter++);
if (iter == vertices[i].e-end())
{
vertices[i].e-push_back(edge(j, cost)); eNum++; return true;
}
if (iter-vID == j) return false;
vertices[i].e-insert(iter, edge(j, cost)); eNum++; return true;
}
name& getV(int n) { return vertices[n].v; } //没有越界检查
int nextV(int m, int n)//返回m号顶点的第n号顶点后第一个邻接顶点号，无返回-1
{
for (listedge::iterator iter = vertices[m].e-begin();
iter != vertices[m].e-end(); iter++) if (iter-vID n) return iter-vID;
return -1;
}private:
bool find(const name& v)
{
for (int i = 0; i vNum; i++) if (v == vertices[i].v) return true;
return false;
}
bool find(const name& v, int& i)
{
for (i = 0; i vNum; i++) if (v == vertices[i].v) return true;
return false;
}
strUCt edge
{
edge() {}
edge(int vID, dist cost) : vID(vID), cost(cost) {}
int vID;
dist cost;
};
struct vertex
{
vertex() {}
vertex(name v, listedge* e) : v(v), e(e) {}
name v;
listedge* e;
};
int vNum, eNum;
vectorvertex vertices;
};#endif 这个实现是很简陋的，但应该能满足后面的讲解了。现在这个还什么都不能做，不要急，在下篇将讲述图的DFS和BFS。 更多内容请看C/C++技术专题 数据结构 数据结构教程专题，或 DFS和BFS 对于非线性的结构，遍历都会首先成为一个问题。和二叉树的遍历一样，图也有深度优先搜索（DFS）和广度优先搜索（BFS）两种。不同的是，图中每个顶点没有了祖先和子孙的关系，因此，前序、中序、后序不再有意义了。
仿照二叉树的遍历，很轻易就能完成DFS和BFS，只是要注重图中可能有回路，因此，必须对访问过的顶点做标记。 最基本的有向带权网#ifndef Graph_H
#define Graph_H #include iostream
#include queue
using namespace std;
#include "Graphmem.h" template class name, class dist, class mem
class Network
{
public:
Network() {}
Network(dist maxdist) { data.NoEdge = maxdist; }
~Network() {}
bool insertV(name v) { return data.insertV(v); }
bool insertE(name v1, name v2, dist cost) { return data.insertE(v1, v2, cost); }
name& getV(int n) { return data.getV(n); }
int nextV(int m, int n = -1) { return data.nextV(m, n); }
int vNum() { return data.vNum; }
int eNum() { return data.eNum; }
protected:
bool* visited;
static void print(name v) { cout v; }
private:
mem data;
};
#endif 你可以看到，这是在以mem方式储存的data上面加了一层外壳。在图这里，逻辑上分有向、无向，带权、不带权；储存结构上有邻接矩阵和邻接表。也就是说分开来有8个类。为了最大限度的复用代码，继续关系就非常复杂了。但是，多重继续是件很讨厌的事，什么覆盖啊，还有什么虚拟继续，我可不想花大量篇幅讲语言特性。于是，我将储存方式作为第三个模板参数，这样一来就省得涉及虚拟继续了，只是这样一来这个Network的实例化就很麻烦了，不过这可以通过typedef或者外壳类来解决，我就不写了。反正只是为了让大家明白，真正要用的时候，最好是写专门的类，比如无向无权邻接矩阵图，不要搞的继续关系乱七八糟。 DFS和BFS的实现public:
void DFS(void(*visit)(name v) = print)
{
visited = new bool[vNum()];
for (int i = 0; i vNum(); i++) visited[i] = false;
DFS(0, visit);
delete []visited;
}
protected:
void DFS(int i, void(*visit)(name v) = print)
{
visit(getV(i)); visited[i] = true;
for (int n = nextV(i); n != -1; n = nextV(i, n))
if (!visited[n]) DFS(n, visit);
}
public:
void BFS(int i = 0, void(*visit)(name v) = print)//n没有越界检查
{
visited = new bool[vNum()]; queueint a; int n;
for (n = 0; n vNum(); n++) visited[n] = false;
visited[i] = true;
while (i != -1)//这个判定可能是无用的
{
visit(getV(i));
for (n = nextV(i); n != -1; n = nextV(i, n))
if (!visited[n]) { a.push(n); visited[n] = true; }
if (a.empty()) break;
i = a.front(); a.pop();
}
delete []visited;
} DFS和BFS函数很难写得像树的遍历方法那么通用，这在后面就会看到，虽然我们使用了DFS和BFS的思想，但是上面的函数却不能直接使用。因为树的信息主要在节点上，而图的边上还有信息。 测试程序#include iostream
using namespace std;
#include "Graph.h"
int main()
{
Networkchar, int, LinkedListchar, int a;
a.insertV('A'); a.insertV('B');
a.insertV('C'); a.insertV('D');
a.insertE('A', 'B', 1); a.insertE('A', 'C', 2);
a.insertE('B', 'D', 3);
cout "DFS: "; a.DFS(); cout endl;
cout "BFS: "; a.BFS(); cout endl;
return 0;
} 老实说，这个类用起来真的不是很方便。不过能说明问题就好。 更多内容请看C/C++技术专题 数据结构 数据结构教程专题，或 无向图 要是在纸上随便画画，或者只是对图做点示范性的说明，大多数人都会选择无向图。然而在计算机中，无向图却是按照有向图的方法来储存的——存两条有向边。
实际上，当我们说到无向的时候，只是忽略方向——在纸上画一条线，难不成那线“嗖”的就出现了，不是从一头到另一头画出来的？ 无向图有几个特有的概念，连通分量、关节点、最小生成树。下面将分别介绍，在此之前，先完成无向图类的基本操作。 无向图类template class name, class dist, class mem
class Graph : public Networkname, dist, mem
{
public:
Graph() {}
Graph(dist maxdist) : Networkname, dist, mem (maxdist) {}
bool insertE(name v1, name v2, dist cost)
{
if (Networkname, dist, mem::insertE(v1, v2, cost))
return Networkname, dist, mem::insertE(v2, v1, cost);
return false;
}
}; 仅仅是添加边的时候，再添加一条反向边，很简单。 连通分量 这是无向图特有的，有向图可要复杂多了（强、单、弱连通），原因就是无向图的边怎么走都行，有向图的边似乎掉下无底深渊就再也爬不上来了。有了DFS，求连通分量的算法就变得非常简单了——对每个没有访问的顶点调用DFS就可以了。void components()
{
visited = new bool[vNum()]; int i, j = 0;
for (i = 0; i vNum(); i++) visited[i] = false;
cout "Components:" endl;
for (i = 0; i vNum(); i++)
{
if (!visited[i]) { cout '(' ++j ')'; DFS(i); cout endl; }
}
delete []visited;
} 关节点 下定义是人们熟悉事物的一个方法，因为概念使得人们能够区分事物——关于这个还有个绝对的运动和相对的静止的哲学观点（河水总在流，但是长江还叫长江，记得那个闻名的“不可能踏进同一条河里”吗？）因此，能否有个准确的概念往往是一门学科发展程度的标志，而能否下一个准确的定义反映了一个人的思维能力。说这么多废话，原因只有一个，我没搞清楚什么叫“关节点”——参考书有限，不能仔细的考究了，如有误解，还望指正。 严版是这么说的：假如删除某个顶点，将图的一个连通分量分割成两个或两个以上的连通分量，称该顶点为关节点。——虽然没有提到图必须是无向的，但是提到了连通分量已经默认是无向图了。
殷版是这么说的：在一个无向连通图中，……（余下同严版）。 问题出来了，非连通图是否可以讨论含有关节点？我们是否可以说某个连通分量中含有关节点？遗憾的是，严版留下这个问题之后，在后面给出的算法是按照连通图给的，这样当图非连通时结果就是错的。殷版更是滑头，只输出重连通分量，不输出关节点，自己虽然假定图是连通的，同样没有连通判定。 翻翻离散数学吧，结果没找到什么“关节点”，只有“割点”，是这样的：一个无向连通图，假如删除某个顶点后，变为非连通图，该顶点称为割点。权当“割点”就是“关节点”，那么算法至少也要先判定是否连通吧？可是书上都直接当连通的了…… 关于算法不再细说，书上都有。下面的示例，能输出每个连通分量的“关节点”（是不是可以这样叫，我也不清楚）。dfn储存的是每个顶点的访问序号，low是深度优先生成树上每个非叶子顶点的子女通过回边所能到达的顶点最小的访问序号。把指向双亲的边也当成回边并不影响判定，因此不必特意区分，殷版显式区分了，属于画蛇添足。这样一来，if (low[n] = dfn[i]) cout getV(i);这个输出关节点的判定中的=就显得很尴尬了，因为只能等于不可能大于。还要注重的是，生成树的根（DFS的起始点）是单独判定的。void articul()
{
dfn = new int[vNum()]; low = new int[vNum()]; int i, j = 0, n;
for(i = 0; i vNum(); i++) dfn[i] = low[i] = 0;//初始化
for (i = 0; i vNum(); i++)
{
if (!dfn[i])
{
cout '(' ++j ')'; dfn[i] = low[i] = count = 1;
if ((n = nextV(i)) != -1) articul(n); bool out = false;//访问树根
while ((n = nextV(i, n)) != -1)
{
if (dfn[n]) continue;
if (!out) { cout getV(i); out = true; }//树根有不只一个子女
articul(n);//访问其他子女
}
cout endl;
}
}
delete []dfn; delete []low;
}private:
void articul(int i)
{
dfn[i] = low[i] = ++count;
for (int n = nextV(i); n != -1; n = nextV(i, n))
{
if (!dfn[n])
{
articul(n);
if (low[n] low[i]) low[i] = low[n];
if (low[n] = dfn[i]) cout getV(i);//这里只可能＝
}
else if (dfn[n] low[i]) low[i] = dfn[n];//回边判定
}
}
int *dfn, *low, count;
说人是最难伺候的，真是一点不假。上面刚刚为了“提高可靠性”添加了几条多余的边，这会儿又来想办法怎么能以最小的代价把所有的顶点都连起来。 可能正是人的这种精神才使得人类能够进步吧——看着现在3GHz的CPU真是眼红啊，我还在受500MHz的煎熬，然后再想想8086…… 正如图的基本元素是顶点和边，从这两个方向出发，就能得到两个算法——Kruskal算法（从边出发）、Prim算法（从顶点出发）。据说还有别的方法，恕我参考资料有限，不能详查。 最小生成树的储存 显然用常用的树的储存方法来储存没有必要，虽然名曰“树”，实际上，这里谁是谁的“祖先”、“子孙”并不重要。因此，用如下的MSTedge结构数组来储存就可以了。 template class dist
class MSTedge
{
public:
MSTedge() {}
MSTedge(int v1, int v2, dist cost) : v1(v1), v2(v2), cost(cost) {}
int v1, v2;
dist cost;
bool operator (const MSTedge& v2) { return (cost v2.cost); }
bool operator (const MSTedge& v2) { return (cost v2.cost); }
bool operator == (const MSTedge& v2) { return (cost == v2.cost); }
}; Kruskal算法 最小生成树直白的讲就是，挑选N－1条不产生回路最短的边。Kruskal算法算是最直接的表达了这个思想——在剩余边中挑选一条最短的边，看是否产生回路，是放弃，不是选定然后重复这个步骤。说起来倒是很简单，做起来就不那么轻易了——判定是否产生回路需要并查集，在剩余边中找一条最短的边需要最小堆（并不需要对所有边排序，所以堆是最佳选择）。 Kruskal算法的复杂度是O(eloge)，当e接近N^2时，可以看到这个算法不如O(N^2)的Prim算法，因此，他适合于稀疏图。而作为稀疏图，通常用邻接表来储存比较好。另外，对于邻接矩阵储存的图，Kruskal算法比Prim算法占不到什么便宜（初始还要扫描N^2条“边”）。因此，最好把Kruskal算法放在Link类里面。 template class name, class dist int Linkname, dist::MinSpanTree(MSTedgedist* a)
{
MinHeapMSTedgedist E; int i, j, k, l = 0;
MFSets V(vNum); listedge::iterator iter;
for (i = 0; i vNum; i++)
for (iter = vertices[i].e-begin(); iter != vertices[i].e-end(); iter++)
E.insert(MSTedgedist(i, iter-vID, iter-cost));//建立边的堆
for (i = 0; i eNum && l vNum; i++)//Kruskal Start
{
j = V.find(E.top().v1); k = V.find(E.top().v2);
if (j != k) { V.merge(j, k); a[l] = E.top(); l++; }
E.pop();
}
return l;
} 下面是堆和并查集的实现 #ifndef Heap_H
#define Heap_H
#include vector
using namespace std;
#define minchild(i) (heap[i*2+1]heap[i*2+2]？i*2+1:i*2+2)
template class T
class MinHeap
{
public:
void insert(const T& x) { heap.push_back(x); FilterUp(heap.size()-1); }
const T& top() { return heap[0]; }
void pop() { heap[0] = heap.back(); heap.pop_back(); FilterDown(0); }
private:
void FilterUp(int i)
{
for (int j = (i - 1) / 2; j = 0 && heap[j] heap[i]; i = j, j = (i - 1) / 2)
swap(heap[i], heap[j]);
}
void FilterDown(int i)
{
for (int j = minchild(i); j heap.size() && heap[j] heap[i]; i = j, j = minchild(i))
swap(heap[i], heap[j]);
}
vectorT heap;
};
#endif #ifndef MFSets_H
#define MFSets_H
class MFSets
{
public:
MFSets(int maxsize) : size(maxsize)
{
parent = new int[size + 1];
for (int i = 0; i = size; i++) parent[i] = -1;
}
~MFSets() { delete []parent; }
void merge(int root1, int root2)//root1!=root2
{
parent[root2] = root1;
}
int find(int n)
{
if (parent[n] 0) return n;
return find(parent[n]);
}
private:
int size;
int* parent;
};
#endif Prim算法 假如从顶点入手，就能得到另一种方法。从只含有一个顶点的集合开始，寻找集合外面的顶点到这个集合里的顶点最近的一条边，然后将这个顶点加入集合，修改因为这个顶点的加入而使得集合外面的顶点到集合里的顶点的最短距离产生变化的分量。因为需要对每个顶点扫描，邻接矩阵储存的图是最合适Prim算法的。 template class name, class dist int AdjMatrixname, dist::MinSpanTree(MSTedgedist* a)
{
dist* lowC = new dist[vNum]; int* nearV = new int[vNum];
int i, j, k;
for (i = 0; i vNum; i++) { lowC[i] = edge[0][i]; nearV[i] = 0; } nearV[0] = -1;
for (k = 0; k vNum-1; k++)//Prim Start
{
for (i = 1, j = 0; i vNum; i++)
if (nearV[i] != -1 && lowC[i] lowC[j]) j = i;//find low cost
a[k] = MSTedgedist(nearV[j], j, lowC[j]); nearV[j] = -1; //insert MST
if (a[k].cost == NoEdge) return k - 1;//no edge then return
for (i = 1; i vNum; i++)//modify low cost
if (nearV[i] != -1 && edge[i][j] lowC[i]) { lowC[i] = edge[i][j]; nearV[i] = j; }
}
return k;
} 这里需要说明一下，对于edge[I][I]这样的是应该是0呢还是NoEdge呢？显然0合理，但是不好用。并且，从有权图无权图统一的角度来说，是NoEdge更好。因此，在我的有权图的邻接矩阵中，主对角线上的元素是NoEdge，而不是书上的0。 测试程序 储存和操作分离，没想到得到了一个有趣的结果——对于最后的无向图而言，最小生成树的算法对外表现不知道是采用了那个算法。 template class name, class dist, class mem
bool Graphname, dist, mem::MinSpanTree()
{
MSTedgedist* a = new MSTedgedist[vNum() - 1];
int n = data.MinSpanTree(a); dist sum = dist();
if (n vNum() - 1) return false;//不够N－1条边，不是生成树
for (int i = 0; i n; i++)
{
cout '(' getV(a[i].v1) ',' getV(a[i].v2) ')' a[i].cost ' ';
sum += a[i].cost;
}
cout endl "MinCost: " sum endl;
delete []a;
return true;
} 最后的测试图的数据取自殷版（C++）——不知是这组数据好是怎么的，殷版居然原封不动的照抄了《数据结构算法与应用-C++语言描述》（中文译名） #include iostream
using namespace std;
#include "Graph.h"
int main()
{
Graphchar, int, AdjMatrixchar, int a(100);//改为Link储存为Kruskal算法
a.insertV('A'); a.insertV('B');
a.insertV('C'); a.insertV('D');
a.insertV('E'); a.insertV('F');
a.insertV('G');
a.insertE('A', 'B', 28); a.insertE('A', 'F', 10);
a.insertE('B', 'C', 16); a.insertE('C', 'D', 12);
a.insertE('D', 'E', 22); a.insertE('B', 'G', 14);
a.insertE('E', 'F', 25); a.insertE('D', 'G', 18);
a.insertE('E', 'G', 24);
a.MinSpanTree();
return 0;
} 最短路径恐怕是图的各种算法中最能吸引初学者眼球的了——在地图上找一条最短的路或许每个人都曾经尝试过。下面我们用计算机来完成我们曾经的“愿望”。
在图的算法中有个有趣的现象，就是问题的规模越大，算法就越简单。图是个复杂的结构，对于一个特定问题，求解特定顶点的结果都会受到其他顶点的影响——就好比一堆互相碰撞的球体，要求解特定球体的状态，就必须考虑其他球体的状态。既然每个顶点都要扫描，假如对所有的顶点都求解，那么算法就非常的简单——无非是遍历吗。然而，当我们降低问题规模，那很自然的，我们希望算法的规模也降低——假如不降低，不是杀鸡用牛刀？但是，正是由于图的复杂性，使得这种降低不轻易达到，因此，为了降低算法的规模，使得算法就复杂了。 在下面的介绍中，清楚了印证了上面的结论。人的认知过程是从简单到复杂，虽然表面看上去，求每对顶点之间的最短路径要比特定顶点到其他顶点之间的最短路径复杂，但是，就像上面说的，本质上，前者更为简单。下面的介绍没有考虑历史因素（就是指哪个算法先提出来），也没有考虑算法提出者的真实想法（究竟是谁参考了或是没参考谁），只是从算法本身之间的联系来做一个阐述，如有疏漏，敬请原谅。 预备工作 一路走下来，图类已经很“臃肿”了，为了更清楚的说明问题，需要“重起炉灶另开张”，同时也是为了使算法和储存方法分开，以便于复用。 首先要为基本图类添加几个接口。template class name, class dist, class mem
class Network
{
public:
int find(const name& v) { int n; if (!data.find(v, n)) return -1; return n; }
dist& getE(int m, int n) { return data.getE(m, n); }
const dist& NoEdge() { return data.NoEdge; }
};
template class name, class dist
class AdjMatrix
{
public:
dist& getE(int m, int n) { return edge[m][n]; }
};
template class name, class dist
class Link
{
public:
dist& getE(int m, int n)
{
for (listedge::iterator iter = vertices[m].e-begin();
iter != vertices[m].e-end() && iter-vID n; iter++);
if (iter == vertices[m].e-end()) return NoEdge;
if (iter-vID == n) return iter-cost;
return NoEdge;
}
}; 然后就是为了最短路径算法“量身定做”的“算法类”。求某个图的最短路径时，将图绑定到算法上，例如这样：Networkchar, int, Linkchar, int a(100);
//插入点、边……
Weightchar, int, Linkchar, int b(&a);#include "Network.h"
template class name, class dist, class mem
class Weight
{
public:
Weight(Networkname, dist, mem* G) : G(G), all(false), N(G-vNum())
{
length = new dist*[N]; path = new int*[N];
shortest = new bool[N]; int i, j;
for (i = 0; i N; i++)
{
length[i] = new dist[N]; path[i] = new int[N];
}
for (i = 0; i N; i++)
{
shortest[i] = false;
for (j = 0; j N; j++)
{
length[i][j] = G-getE(i, j);
if (length[i][j] != G-NoEdge()) path[i][j] = i;
else path[i][j] = -1;
}
}
}
~Weight()
{
for (int i = 0; i N; i++) { delete []length[i]; delete []path[i]; }
delete []length; delete []path; delete []shortest;
}
private:
void print(int i, int j)
{
if (path[i][j] == -1) cout "No Path" endl; return;
cout "Shortest Path: "; out(i, j); cout G-getV(j) endl;
cout "Path Length: " length[i][j] endl;
}
void out(int i, int j)
{
if (path[i][j] != i) out(i, path[i][j]);
cout G-getV(path[i][j]) "-";
}
dist** length; int** path; bool* shortest; bool all; int N;
Networkname, dist, mem* G;
}; 发现有了构造函数真好，算法的结果数组的初始化和算法本身分开了，这样一来，算法的基本步骤就很轻易看清楚了。 所有顶点之间的最短路径（Floyed算法） 从v1到v2的路径要么是v1-v2，要么中间经过了若干顶点。显然我们要求的是这些路径中最短的一条。这样一来，问题就很好解决了——最初都是源点到目的点，然后依次添加顶点，使得路径逐渐缩短，顶点都添加完了，算法就结束了。void AllShortestPath()//Folyed
{
if (all) return;
for (int k = 0; k N; k++)
{
shortest[k] = true;
for (int i = 0; i N; i++)
for (int j = 0; j N; j++)
if (length[i][k] + length[k][j] length[i][j])
{
length[i][j] = length[i][k] + length[k][j];
path[i][j] = path[k][j];
}
}
all = true;
} 单源最短路径（Dijkstra算法） 仿照上面的Floyed算法，很轻易的，我们能得出下面的算法：void ShortestPath(int v1)
{
//Bellman-Ford
for (int k = 2; k N; k++)
for (int i = 0; i N; i++)
for (int j = 0; j N; j++)
if (length[v1][j] + length[j][i] length[v1][i])
{
length[v1][i] = length[v1][j] + length[j][i];
path[v1][i] = j;
}
} 这就是Bellman-Ford算法，可以看到，采用Floyed算法的思想，不能使算法的时间复杂度从O(n3)降到预期的O(n2)，只是空间复杂度从O(n2)降到了O(n)，但这也是应该的，因为只需要原来结果数组中的一行。因此，我并不觉得这个算法是解决“边上权值为任意值的单源最短路径问题”而专门提出来的，是Dijkstra算法的“推广”版本，他只是Floyed算法的退化版本。 显然，Floyed算法是经过N次N2条边迭代而产生最短路径的；假如我们想把时间复杂度从O(n3) 降到预期的O(n2)，就必须把N次迭代的N2条边变为N条边，也就是说每次参与迭代的只有一条边——问题是如何找到这条边。 先看看边的权值非负的情况。假设从顶点0出发，到各个顶点的距离是a1,a2……，那么，这其中的最短距离an必定是从0到n号顶点的最短距离。这是因为，假如an不是从0到n号顶点的最短距离，那么必然是中间经过了某个顶点；但现在边的权值非负，一个比现在这条边还长的边再加上另一条非负的边，是不可能比这条边短的。从这个原理出发，就能得出Dijkstra算法，注重，这个和Prim算法极其相似，不知道谁参考了谁；但这也是难免的事情，因为他们的原理是一样的。void ShortestPath(const name& vex1, const name& vex2)//Dijkstra
{
int v1 = G-find(vex1); int v2 = G-find(vex2);
if (shortest[v1]) { print(v1, v2); return; }
bool* S = new bool[N]; int i, j, k;
for (i = 0; i N; i++) S[i] = false; S[v1] = true;
for (i = 0; i N - 1; i++)//Dijkstra Start, like Prim？
{
for (j = 0, k = v1; j N; j++)
if (!S[j] && length[v1][j] length[v1][k]) k = j;
S[k] = true;
for (j = 0; j N; j++)
if (!S[j] && length[v1][k] + length[k][j] length[v1][j])
{
length[v1][j] = length[v1][k] + length[k][j];
path[v1][j] = k;
}
}
shortest[v1] = true; print(v1, v2);
} 假如边的权值有负值，那么上面的原则不再适用，连带的，Dijkstra算法也就不再适用了。这时候，没办法，只有接受O(n3) Bellman-Ford算法了，虽然他可以降低为O(n*e)。不过，何必让边的权值为负值呢？还是那句话，合理的并不好用。 特定两个顶点之间的最短路径（A*算法） 其实这才是我们最关心的问题，我们只是想知道从甲地到乙地怎么走最近，并不想知道别的——甲地到丙地怎么走关我什么事？自然的，我们希望这个算法的时间复杂度为O(n)，但是，正像从Floyed算法到Dijkstra算法的变化一样，并不是很轻易达到这个目标的。 让我们先来看看Dijkstra算法求特定两个顶点之间的最短路径的时间复杂度究竟是多少。显然，在上面的void ShortestPath(const name& vex1, const name& vex2)中，当S[v2]==true时，算法就可以中止了。假设两个顶点之间直接的路径是他们之间的路径最短的（不需要经过其他中间顶点），并且这个路径长度是源点到所有目的点的最短路径中最短的，那么第一次迭代的时候，就可以得到结果了。也就是说是O(n)。然而当两个顶点的最短路径需要经过其他顶点，或者路径长度不是源点到未求出最短路径的目的点的最短路径中最短的，那就要再进行若干次迭代，对应的，时间复杂度就变为O(2n)、O(3n)……到了最后才求出来（迭代了N－1次）的就是O(n2)。 很明显的，迭代次数是有下限的，最短路径上要经过多少个顶点，至少就要迭代多少次，我们只能使得最终的迭代次数接近最少需要的次数。假如再要减低算法的时间复杂度，我们只能想办法把搜索范围的O(n)变为O(1)，这样，即使迭代了N－1次才得到结果，那时间复杂度仍为O(n)。但这个想法实现起来却是困难重重。 仍然看Dijkstra算法，第一步要寻找S中的顶点到S外面顶点中最短的一条路径，这个min运算使用基于比较的方法的时间复杂度下限是O(longN)（使用败者树），然后需要扫描结果数组的每个分量进行修改，这里的时间复杂度就只能是O(n)了。原始的Dijkstra算法达不到预期的目的。 现在让我们给图添加一个附加条件——两点之间直线最短，就是说假如v1和v2之间有直通的路径（不经过其他顶点），那么这条路径就是他们之间的最短路径。这样一来，假如求的是v1能够直接到达的顶点的最短路径，时间复杂度就是O(1)了，显然比原来最好的O(n)（这里实际上是O(logN)）提高了效率。 这个变化的产生，是因为我们添加了“两点之间直线最短”这样的附加条件，实际上就是引入一个判定准则，把原来盲目的O(n)搜索降到了O(1)。这个思想就是A*算法的思想。关于A*算法更深入的介绍，恕本人资料有限，不能满足大家了。有爱好的可以到网上查查，这方面的中文资料实在太少了，大家做好看E文的预备吧。 不同于现有的教科书，我把求最短路径的算法的介绍顺序改成了上面的样子。我认为这个顺序才真正反映了问题的本质——当减低问题规模时，为了降低算法的时间复杂度，应该想办法缩小搜索范围。而缩小搜索范围，都用到了一个思想——尽可能的向接近最后结果的方向搜索，这就是贪婪算法的应用。 假如反向看一遍算法的演化，我们还能得出新的结论。Dijkstra算法实际上不用做n2次搜索、比较和修改，当求出最短路径的顶点后，搜索范围已经被缩小了，只是限于储存结构，这种范围的缩小并没有体现出来。假如我们使得这种范围缩小直接体现出来，那么，用n次Dijkstra算法代替Floyed算法就能带来效率上的提升。A*算法也是如此，假如用求n点的A*算法来代替Dijkstra算法，也能带来效率的提升。 但是，每一步的进化实际上都伴随着附加条件的引入。从Floyed到Dijkstra是边上的权值非负，假如这个条件不成立，那么就只能退化成Bellman-Ford算法。从Dijkstra到A*是另外的判定准则的引入（本文中是两点之间直线最短），假如这个条件不成立，同样的，只能采用不完整的Dijkstra（求到目的顶点结束算法）。
这部分是和工程相关的，也就是说，当AOV、AOE很复杂的时候，才能显示出这部分的价值——简单的话，手工都要比程序快，输入数据那段时间手工结果就出来了。我也没什么例子好举，总给我一种没底气的感觉，勉为其难的把程序写完就算完事吧。和前边的相比，这部分专业了一点，换而言之，不是每个人都感爱好，不想看就跳过去吧。 预备工作 活动网络主要有两个算法，拓扑排序和求要害路径，后者以前者为基础。仿照上篇，另外构造一个“算法类”，需要算法时，将图绑定到算法上。 #include "Network.h"
#define iterator listLinkname, dist::edge::iterator
#define begin(i) G-data.vertices[i].e-begin()
#define end(i) G-data.vertices[i].e-end()
struct CriAct
{
CriAct() {}
CriAct(int source, int dest) : s(source), d(dest) {}
int s, d;
};
template class name, class dist
class ActivityNetwork
{
public:
ActivityNetwork(Networkname, dist, Linkname, dist * G) : G(G), N(G-vNum()), outCriAct(CA)
{
count = new int[N]; result = new int[N];
}
~ActivityNetwork()
{
delete []count; delete []result;
}
const vectorCriAct& outCriAct;
const int* out;
private:
void initialize()
{
for (int j = 0; j N; j++) count[j] = 0;
for (int i = 0; i N; i++)
{
for (iterator iter = begin(i); iter != end(i); iter++) count[iter-vID]++;
}
out = result;
}
Networkname, dist, Linkname, dist * G;
vectorCriAct CA;
int N, *count, *result;
}; 因为AOV和AOE的边都不会太多（想象一下边多的情况，那事件就都是鸡毛蒜皮了），所以储存结构直接选择了邻接表。并且为了体现邻接表的优势，需要直接操作私有数据，因此要把这个类声明为Link类和Network类的友元，另外由于这个类在后面，所以需要前视声明。具体如下： template class name, class dist class ActivityNetwork;
template class name, class dist class Link
{friend class ActivityNetworkname, dist;};
template class name, class dist, class mem class Network
{ friend class ActivityNetworkname, dist;}; 拓扑排序 这个算法很精巧，避免了对已经排好序的顶点的再次扫描，另外，殷版上用计数数组来充当栈的方法也很巧妙。算法的说明参阅相关的教科书，不再赘述。 bool TopoSort()
{
initialize(); int i, top = -1;
for (i = 0; i N; i++) if (!count[i]) { count[i] = top; top = i; }
for (i = 0; i N; i++) //TopoSort Start
{
if (top == -1) return false;
result[i] = top; top = count[top];
for (iterator iter = begin(result[i]); iter != end(result[i]); iter++)
if (!--count[iter-vID]) { count[iter-vID] = top; top = iter-vID; }
}
return true;
} 由于public数据成员out和private数据成员result指向同一个数组，在类的外面可以通过out来得到排序结果，只是不能改变（当然，非要改变const数据也不是没有办法）。下面是测试程序，数据来自殷版： #include iostream
using namespace std;
#include "ActivityNetwork.h"
int main()
{
Networkint, int, Linkint, int a;
a.insertV(0);a.insertV(1);a.insertV(2);a.insertV(3);a.insertV(4);a.insertV(5);
a.insertE(0,3,1);a.insertE(0,1,1);a.insertE(1,5,1);a.insertE(2,1,1);
a.insertE(2,5,1);a.insertE(4,0,1);a.insertE(4,1,1);a.insertE(4,5,1);
ActivityNetworkint, int b(&a);
if (b.TopoSort()) for (int i = 0; i a.vNum(); i++) cout b.out[i] ' ';
return 0;
} 要害路径 有了拓扑排序的结果，这个程序就比较好写了，那些所谓的“技巧”就不用了，如下的程序，很直白，算法说明请参考教科书。 bool CriPath()
{
if (!TopoSort()) return false; int i; iterator iter; CA.clear();
dist* Ve = new dist[N]; dist* Vl = new dist[N];//Ve最早开始时间，Vl最迟开始时间
for (i = 0; i N; i++) Ve[i] = 0;//Ve初始化
for (i = 0; i N; i++)//按拓扑顺序计算Ve
for (iter = begin(result[i]); iter != end(result[i]); iter++)
if (Ve[result[i]]+iter-costVe[iter-vID]) Ve[iter-vID]= Ve[result[i]] + iter-cost;
for (i = 0; i N; i++) Vl[i] = Ve[N - 1];//Vl初始化
for (i = N - 2; i = 0; i--)//按逆拓扑顺序计算Vl
for (iter = begin(result[i]); iter != end(result[i]); iter++)
if (Vl[iter-vID]-iter-cost Vl[result[i]]) Vl[result[i]] = Vl[iter-vID] - iter-cost;
for (i = 0; i N; i++)//计算各个活动的最早开始时间和最迟开始时间
for (iter = begin(i); iter != end(i); iter++)
if (Ve[i] == Vl[iter-vID] - iter-cost) CA.push_back(CriAct(i, iter-vID));
return true;
} 同样的在类的外面可以通过outCriAct得到结果，是一个const引用。如下的测试程序，数据来自殷版： #include iostream
using namespace std;
#include "ActivityNetwork.h"
int main()
{
Networkint, int, Linkint, int a;
a.insertV(0);a.insertV(1);a.insertV(2);a.insertV(3);a.insertV(4);
a.insertV(5); a.insertV(6);a.insertV(7);a.insertV(8);
a.insertE(0,1,6);a.insertE(0,2,4);a.insertE(0,3,5);
a.insertE(1,4,1);a.insertE(2,4,1);a.insertE(3,5,2);
a.insertE(4,6,9);a.insertE(4,7,7);a.insertE(5,7,4);
a.insertE(6,8,2);a.insertE(7,8,4);
ActivityNetworkint, int b(&a);
if (b.CriPath())
for (int j = 0; j b.outCriAct.size(); j++)
cout ''a.getV(b.outCriAct[j].s) ',' a.getV(b.outCriAct[j].d) '' ' ';
return 0;
} 总结 不同于前面的链表和树，在图这里，储存方法不是重点，我们更多的注重力放在了算法上。我在写程序的时候，也尽量做到了算法和储存方法无关。然而算法实际上就是现实问题的抽象，假如我们的常识所不及，我们也就没有办法来介绍算法，反过来说，几乎遇不到的问题，我们也不会对它的算法感爱好。 因此，在图的算法里面，由铺设管道引出了最小生成树，由提高通信、交通网络可靠性引出了关节点和重连通分量，由地图寻径引出了最短路径，由工程预算引出了要害路径。这些恐怕是我们能够理解的全部了，假如再来一个电气网络计算，没点物理知识恐怕是要完。 但即使这样，上面的各个算法仍然离我们很远，我们大多数人恐怕永远都不会知道管道是怎么铺的。我想，这里面除了最短路径能引起大多数人的爱好之外，其他的就只能走马观花的看看罢了。这也使得图的学习很像“聋子的耳朵”，真正接触到图的用途的人不多，并且即使用到图，也仅仅是个别的算法。 正像数据结构教学的通病一样，学无所用经常导致学无所成，前面的链表、树好歹还能做点什么东西出来，到了图这里，除了做个导游系统，我们也做不出别的什么了。写到这里很无奈，但我也只能是无奈…… 那么，学完了图，我们应该把握什么呢，是上面零散的算法吗？我的看法是，不是。我觉得我们更应该知道那些算法是怎么“创造”出来的，假如碰到了类似的问题，能不能“派生”出新的算法。因此，我觉得《数据结构算法与应用-C++语言描述》这本书，将图的最小生成树、最短路径、拓扑排序算法放到了贪婪算法里讲解，是一种更为合理的安排。 最后对在学习图时像我一样茫然的人深表同情。
