数据结构学习C++――图(4&5&总结&后记)

　　

　　

数据结构学习（C++）――图【4】（最短路径） happycock（原作）

　　

要害字 数据结构 最短路径

　　

　　

最短路径恐怕是图的各种算法中最能吸引初学者眼球的了――在地图上找一条最短的路或许每个人都曾经尝试过。下面我们用计算机来完成我们曾经的“愿望”。

　　

　　

在图的算法中有个有趣的现象，就是问题的规模越大，算法就越简单。图是个复杂的结构，对于一个特定问题，求解特定顶点的结果都会受到其他顶点的影响――就好比一堆互相碰撞的球体，要求解特定球体的状态，就必须考虑其他球体的状态。既然每个顶点都要扫描，假如对所有的顶点都求解，那么算法就非常的简单――无非是遍历吗。然而，当我们降低问题规模，那很自然的，我们希望算法的规模也降低――假如不降低，不是杀鸡用牛刀？但是，正是由于图的复杂性，使得这种降低不轻易达到，因此，为了降低算法的规模，使得算法就复杂了。

　　

　　

在下面的介绍中，清楚了印证了上面的结论。人的认知过程是从简单到复杂，虽然表面看上去，求每对顶点之间的最短路径要比特定顶点到其他顶点之间的最短路径复杂，但是，就像上面说的，本质上，前者更为简单。下面的介绍没有考虑历史因素（就是指哪个算法先提出来），也没有考虑算法提出者的真实想法（究竟是谁参考了或是没参考谁），只是从算法本身之间的联系来做一个阐述，如有疏漏，敬请原谅。

　　

　　

预备工作

　　

一路走下来，图类已经很“臃肿”了，为了更清楚的说明问题，需要“重起炉灶另开张”，同时也是为了使算法和储存方法分开，以便于复用。

　　

　　

首先要为基本图类添加几个接口。

　　

　　

template

　　

class Network

　　

{

　　

public:

　　

int find(const name& v)

　　

dist& getE(int m, int n)

　　

const dist& NoEdge()

　　

};

　　

　　

template

　　

class AdjMatrix

　　

{

　　

public:

　　

dist& getE(int m, int n)

　　

};

　　

　　

template

　　

class Link

　　

{

　　

public:

　　

dist& getE(int m, int n)

　　

{

　　

for (list::iterator iter = vertices[m].e->begin();

　　

iter != vertices[m].e->end() && iter->vID end()) return NoEdge;

　　

if (iter->vID == n) return iter->cost;

　　

return NoEdge;

　　

}

　　

};

　　

　　

然后就是为了最短路径算法“量身定做”的“算法类”。求某个图的最短路径时，将图绑定到算法上，例如这样：

　　

　　

Network > a(100);

　　

//插入点、边……

　　

Weight > b(&a);

　　

　　

#include "Network.h"

　　

template

　　

class Weight

　　

{

　　

public:

　　

Weight(Network* 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 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; 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

　　

cout << "Path Length: " << length[i][j] << endl;

　　

}

　　

　　

void out(int i, int j)

　　

{

　　

if (path[i][j] != i) out(i, path[i][j]);

　　

cout

　　

}

　　

dist** length; int** path; bool* shortest; bool all; int N;

　　

Network* 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] find(vex1); int v2 = G->find(vex2);

　　

if (shortest[v1])

　　

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] ::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 ActivityNetwork

　　

{

　　

public:

　　

ActivityNetwork(Network >* G) : G(G), N(G->vNum()), outCriAct(CA)

　　

{

　　

count = new int[N]; result = new int[N];

　　

}

　　

　　

~ActivityNetwork()

　　

{

　　

delete []count; delete []result;

　　

}

　　

const vector& outCriAct;

　　

const int* out;

　　

private:

　　

void initialize()

　　

{

　　

for (int j = 0; j < N; j++) count[j] = 0;

　　

for (int i = 0; i vID]++;

　　

}

　　

out = result;

　　

}

　　

Network >* G;

　　

vector CA;

　　

int N, *count, *result;

　　

};

　　

　　

因为AOV和AOE的边都不会太多（想象一下边多的情况，那事件就都是鸡毛蒜皮了），所以储存结构直接选择了邻接表。并且为了体现邻接表的优势，需要直接操作私有数据，因此要把这个类声明为Link类和Network类的友元，另外由于这个类在后面，所以需要前视声明。具体如下：

　　

　　

template class ActivityNetwork;

　　

template class Link

　　

;

　　

template class Network

　　

;

　　

　　

拓扑排序

　　

　　

这个算法很精巧，避免了对已经排好序的顶点的再次扫描，另外，殷版上用计数数组来充当栈的方法也很巧妙。算法的说明参阅相关的教科书，不再赘述。

　　

　　

bool TopoSort()

　　

{

　　

initialize(); int i, top = -1;

　　

for (i = 0; i < N; i++) if (!count[i])

　　

for (i = 0; i vID])

　　

}

　　

return true;

　　

}

　　

　　

由于public数据成员out和private数据成员result指向同一个数组，在类的外面可以通过out来得到排序结果，只是不能改变（当然，非要改变const数据也不是没有办法）。下面是测试程序，数据来自殷版：

　　

　　

#include

　　

using namespace std;

　　

#include "ActivityNetwork.h"

　　

int main()

　　

{

　　

Network > 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);

　　

ActivityNetwork 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 cost>Ve[iter->vID]) Ve[iter->vID]= Ve[result[i]] + iter->cost;

　　

　　

for (i = 0; i = 0; i--)//按逆拓扑顺序计算Vl

　　

for (iter = begin(result[i]); iter != end(result[i]); iter++)

　　

if (Vl[iter->vID]-iter->cost vID] - iter->cost;

　　

　　

for (i = 0; i vID] - iter->cost) CA.push_back(CriAct(i, iter->vID));

　　

　　

return true;

　　

}

　　

　　

同样的在类的外面可以通过outCriAct得到结果，是一个const引用。如下的测试程序，数据来自殷版：

　　

　　

#include

　　

using namespace std;

　　

#include "ActivityNetwork.h"

　　

int main()

　　

{

　　

Network > 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);

　　

ActivityNetwork b(&a);

　　

　　

if (b.CriPath())

　　

for (int j = 0; j < b.outCriAct.size(); j++)

　　

cout <<'<'<' << ' ';

　　

return 0;

　　

}

　　

　　

　　

　　

数据结构学习（C++）――图（总结） happycock（原作）

　　

要害字 图

　　

　　

以上就是现在的教科书里面，图的全部内容了。写完之后，茫茫然，不知道学完之后有什么用……就像我在开篇写的，图的应用太广泛了，以至于现在觉得图“没什么用”――很希奇的逻辑，只有仔细体味才能觉察到写教科书的人的无奈。

　　

　　

不同于前面的链表和树，在图这里，储存方法不是重点，我们更多的注重力放在了算法上。我在写程序的时候，也尽量做到了算法和储存方法无关。然而算法实际上就是现实问题的抽象，假如我们的常识所不及，我们也就没有办法来介绍算法，反过来说，几乎遇不到的问题，我们也不会对它的算法感爱好。

　　

　　

因此，在图的算法里面，由铺设管道引出了最小生成树，由提高通信、交通网络可靠性引出了关节点和重连通分量，由地图寻径引出了最短路径，由工程预算引出了要害路径。这些恐怕是我们能够理解的全部了，假如再来一个电气网络计算，没点物理知识恐怕是要完。

　　

　　

但即使这样，上面的各个算法仍然离我们很远，我们大多数人恐怕永远都不会知道管道是怎么铺的。我想，这里面除了最短路径能引起大多数人的爱好之外，其他的就只能走马观花的看看罢了。这也使得图的学习很像“聋子的耳朵”，真正接触到图的用途的人不多，并且即使用到图，也仅仅是个别的算法。

　　

　　

正像数据结构教学的通病一样，学无所用经常导致学无所成，前面的链表、树好歹还能做点什么东西出来，到了图这里，除了做个导游系统，我们也做不出别的什么了。写到这里很无奈，但我也只能是无奈……

　　

　　

那么，学完了图，我们应该把握什么呢，是上面零散的算法吗？我的看法是，不是。我觉得我们更应该知道那些算法是怎么“创造”出来的，假如碰到了类似的问题，能不能“派生”出新的算法。因此，我觉得《数据结构算法与应用-C++语言描述》这本书，将图的最小生成树、最短路径、拓扑排序算法放到了贪婪算法里讲解，是一种更为合理的安排。

　　

　　

最后对在学习图时像我一样茫然的人深表同情。

　　

　　

　　

　　

　　

数据结构学习（C++）――后记 happycock（原作）

　　

要害字 数据结构

　　

　　

这回真的是后记了，也就是到了这些文章结束的时候了。虽然还有排序和查找两大算法系没有讲，但是对于“数据结构”而言，上面应该是全部了。并且这些文章加在一起已经很长了，每次打开Word来编辑，跳到末页总是不那么顺畅，是到了结束的时候了。对于那两大算法系，我预备另外再开一个系列，姑且就叫做《数据结构学习（C++）续》吧。忽然发现，在安排文章结构上不知不觉的受了《计算机编程艺术》的影响了。

　　

　　

我的参考书主要是三本，《数据结构（用面向对象方法与C++描述）》（殷人昆等），《数据结构（C语言版）》（严蔚敏、吴伟民），《数据结构算法与应用-C++语言描述》（中译名，具体信息可查china-pub）。

　　

　　

能写完这些文章，首先要感谢C++语言，假如让我拿C来写，没准中途就放弃了。前不久还看到有人争论数据结构用什么语言描述最合适，有人还在坚持用C最好，按照他的看法，汇编没准是最好的（有爱好可以看看《计算机编程艺术》是拿什么语言写的）。从ADT的思想来看，C是不合适的，因为C要把数据和数据上的操作封装在一起非常的麻烦，并且只有利用文件来组织这种关系，而对于初学者来说，多模块编译链接本身就是一个很玄的事，当年学C语言的时候这部分都没敢看。而C++的类能非常完美的表达ADT的思想，并且模板、重载、继续能更清楚的表述数据结构之间的联系。关于C++在解决问题上比C的优势，可以看看《C++沉思录》，有非常有说服力的例子，当然，从运行效率来说，C要强于C++。

　　

　　

然而当选用了C++之后，有件事就非常尴尬了，就是STL。常用的数据结构、算法都已经作为C++标准的一部分了，我就看到一本书是用STL来描述数据结构的（只看到了书名，没看到内容）。前面的三部分，线性表在STL里全部都有现成的（变长数组、链表、队列、栈），二叉搜索树在SGI－STL里有红黑树的实现，只有图标准库没有提供，但是图最重要的是一堆算法。排序、查找在STL里也有现成的。

　　

　　

这让我想起了“程序员＝民工”的论调，的确，现在的语言、开发工具在给程序员提供了便利的同时，也限制了程序员的思维，养成了他们的惰性。现在编程就是在Framework里面改写若干的函数，在我们感到这种方式的便利的同时，也越来越感到自己力量的渺小。也许人就是种希奇的动物。

　　

　　

或许数据结构这门课程根本就不是让你把握那些链表、树是如何实现的。开设这门课第一个目的是让你懂得“数据结构＋算法＝程序”，第二个目的是培养数据抽象的能力。当这两个目的达到的同时，你也就具备了解决现实未知问题的能力，遗憾的是，大多数连把握已有的数据结构的目标都没达到。出于这个原因，我总是建议你看看《计算机编程艺术》，这部有无数赞誉的巨著。最好不要买纸版的，弄个电子版就行了，纸版的恐怕会吓得你不敢看，^_^。正如盖茨说的，这本书很有趣，假如你不把它当成参考书，你一定会有新的体会。

　　

　　

所有的源程序都已打包，MyDS是线性链式结构，MyTree是树结构，Graph是图结构。加上这系列的WORD文档，打成一个zip包，初步计划放到C++中国联盟的FTP上，下面是论坛的网址http://www.cppcn.com/bbs/

　　

　　

要想学好数据结构，最好亲自把所有的算法完成一遍，从这个角度说，我的源程序有负面作用。我的初衷是使那些照书调不出来的不会因为写不出程序而影响了学习的信心，究竟书上的错漏在所难免，对自学的人和在照本宣科老师手下饱受煎熬的人来说，我的源程序应该能起到预期的作用。

　　

　　

本系列到此结束，续篇再见吧。