数据结构学习(C++)之图

副标题#e#

图的应用恐怕是所有数据布局中最宽泛的了，但这也注定了在讲“数据布局的图”的时候没什么好讲的——关于图的最重要的是算法，并且相当的一部门都是很专业的，一般的人险些不会打仗到；相对而言，布局就显得分量很轻。你可以看到关于图中元素的操纵很少，远没有单链表哪里列出的一大堆“接口”。——一个布局假如巨大，那么能确切界说的操纵就很有限。

根基储存要领

不管怎么说，照旧先得把图存起来。不要看书上列出了许多几何要领，基础只有一个——连接矩阵。假如矩阵是稀疏的，那就可以用十字链表来储存矩阵（见前面的《稀疏矩阵（十字链表）》）。假如我们只干系行的干系，那么就是连接表（出边表）；反之，只体贴列的干系，就是逆连接表（入边表）。

下面给出两种储存要领的实现。

#ifndef Graphmem_H #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 Network<name, dist, AdjMatrix<name, 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 Network<name, dist, LinkedList<name, 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 list<edge>)); 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 (list<edge>::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 (list<edge>::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, list<edge>* e) : v(v), e(e) {} name v; list<edge>* e; }; int vNum, eNum; vector<vertex> vertices; }; #endif

这个实现是很简略的，但应该能满意后头的讲授了。此刻这个还什么都不能做，不要急，在下篇将报告图的DFS和BFS。

#p#副标题#e#

DFS和BFS

#p#分页标题#e#

对付非线性的布局，遍历城市首先成为一个问题。和二叉树的遍历一样，图也有深度优先搜索（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可能外壳类来办理，我就不写了。横竖只是为了让各人大白，真正要用的时候，最好是写专门的类，好比无向无权连接矩阵图，不要搞的担任干系参差不齐。

#p#副标题#e#

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()]; queue<int> 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() { Network<char, int, LinkedList<char, 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; }

诚恳说，这个类用起来真的不是很利便。不外能说明问题就好。

#p#副标题#e#

无向图

要是在纸上随便画画，可能只是对图做点示范性的说明，大大都人城市选择无向图。然而在计较机中，无向图却是凭据有向图的要领来储存的——存两条有向边。实际上，当我们说到无向的时候，只是忽略偏向——在纸上画一条线，难不成那线“嗖”的就呈现了，不是从一头到另一头画出来的？无向图有几个特有的观念，连通分量、枢纽点、最小生成树。下面将别离先容，在此之前，先完成无向图类的根基操纵。

无向图类

template <class name, class dist, class mem> class Graph : public Network<name, dist, mem> { public: Graph() {} Graph(dist maxdist) : Network<name, dist, mem> (maxdist) {} bool insertE(name v1, name v2, dist cost) { if (Network<name, dist, mem>::insertE(v1, v2, cost)) return Network<name, dist, mem>::insertE(v2, v1, cost); return false; } };

仅仅是添加边的时候，再添加一条反向边，很简朴。

连通分量

#p#分页标题#e#

这是无向图特有的，有向图可要巨大多了（强、单、弱连通），原因就是无向图的边怎么走都行，有向图的边仿佛掉下无底深渊就再也爬不上来了。有了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; }

枢纽点

#p#副标题#e#

下界说是人们认识事物的一个要领，因为观念使得人们可以或许区分事物——关于这个尚有个绝对的举动和相对的静止的哲学概念（河水总在流，可是长江还叫长江，记得谁人著名的“不行能踏进同一条河里”吗？）因此，可否有个精确的观念往往是一门学科成长水平的符号，而可否下一个精确的界说反应了一小我私家的思维本领。说这么多空话，原因只有一个，我没搞清楚什么叫“枢纽点”——参考书有限，不能仔细的讲求了，如有误解，还望指正。

严版是这么说的：假如删除某个极点，将图的一个连通分量支解成两个或两个以上的连通分量，称该极点为枢纽点。——固然没有提到图必需是无向的，可是提到了连通分量已经默认是无向图了。

殷版是这么说的：在一个无向连通图中，……（余下同严版）。

问题出来了，非连通图是否可以接头含有枢纽点？我们是否可以说某个连通分量中含有枢纽点？遗憾的是，严版留下这个问题之后，在后头给出的算法是凭据连通图给的，这样当图非连通时功效就是错的。殷版更是滑头，只输出重连通分量，不输出枢纽点，本身固然假定图是连通的，同样没有连通判定。

翻翻离散数学吧，功效没找到什么“枢纽点”，只有“割点”，是这样的：一个无向连通图，假如删除某个极点后，变为非连通图，该极点称为割点。权当“割点”就是“枢纽点”，那么算法至少也要先判定是否连通吧？但是书上都直接当连通的了……

关于算法不再细说，书上都有。下面的示例，能输出每个连通分量的“枢纽点”（是不是可以这样叫，我也不清楚）。dfn储存的是每个极点的会见序号，low是深度优先生成树上每个非叶子极点的后世通过回边所能达到的极点最小的会见序号。把指向双亲的边也当成回边并不影响判定，因此不必特意区分，殷版显式区分了，属于多此一举。这样一来，if (low[n] >= dfn[i]) cout << getV(i);这个输出枢纽点的判定中的>=就显得很难过了，因为只能便是不行能大于。还要留意的是，生成树的根（DFS的起始点）是单独判定的。

#p#副标题#e#

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……

#p#分页标题#e#

正如图的根基元素是极点和边，从这两个偏向出发，就能获得两个算法——Kruskal算法（从边出发）、Prim算法（从极点出发）。听说尚有此外要领，恕我参考资料有限，不能详查。

#p#副标题#e#

最小生成树的储存

显然用常用的树的储存要领来储存没有须要，固然名曰“树”，实际上，这里谁是谁的“祖先”、“子孙”并不重要。因此，用如下的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 Link<name, dist>::MinSpanTree(MSTedge<dist>* a) { MinHeap<MSTedge<dist> > E; int i, j, k, l = 0; MFSets V(vNum); list<edge>::iterator iter; for (i = 0; i < vNum; i++) for (iter = vertices[i].e->begin(); iter != vertices[i].e->end(); iter++) E.insert(MSTedge<dist>(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; }

下面是堆和并查集的实现

#p#副标题#e#

#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]);

}

vector<T> 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算法的。

#p#副标题#e#

template <class name, class dist> int AdjMatrix<name, dist>::MinSpanTree(MSTedge<dist>* 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] = MSTedge<dist>(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;

}

#p#分页标题#e#

【附注】这里需要说明一下，对付edge[I][I]这样的是应该是0呢照旧NoEdge呢？显然0公道，可是欠好用。而且，从有权图无权图统一的角度来说，是NoEdge更好。因此，在我的有权图的连接矩阵中，主对角线上的元素是NoEdge，而不是书上的0。

测试措施

储存和操纵疏散，没想到获得了一个有趣的功效——对付最后的无向图而言，最小生成树的算法对外表示不知道是回收了谁人算法。

template <class name, class dist, class mem> bool Graph<name, dist, mem>::MinSpanTree() { MSTedge<dist>* a = new MSTedge<dist>[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++语言描写》（中文译名）

#p#副标题#e#

#include <iostream>

using namespace std;

#include "Graph.h"

int main()

{

Graph<char, int, AdjMatrix<char, 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;

}

最短路径

最短路径恐怕是图的各类算法中最能吸引初学者眼球的了——在舆图上找一条最短的路或者每小我私家都曾经实验过。下面我们用计较机来完成我们曾经的“愿望”。

在图的算法中有个有趣的现象，就是问题的局限越大，算法就越简朴。图是个巨大的布局，对付一个特定问题，求解特定极点的功效城市受到其他极点的影响——就比如一堆相互碰撞的球体，要求解特定球体的状态，就必需思量其他球体的状态。既然每个极点都要扫描，假如对所有的极点都求解，那么算法就很是的简朴——无非是遍历吗。然而，当我们低落问题局限，那很自然的，我们但愿算法的局限也低落——假如不低落，不是杀鸡用牛刀？可是，正是由于图的巨大性，使得这种低落不容易到达，因此，为了低落算法的局限，使得算法就巨大了。

#p#副标题#e#

在下面的先容中，清楚了印证了上面的结论。人的认知进程是从简朴到巨大，固然外貌看上去，求每对极点之间的最短路径要比特定极点到其他极点之间的最短路径巨大，可是，就像上面说的，本质上，前者更为简朴。下面的先容没有思量汗青因素（就是指哪个算法先提出来），也没有思量算法提出者的真实想法（毕竟是谁参考了或是没参考谁），只是从算法自己之间的接洽来做一个叙述，如有疏漏，敬请原谅。

筹备事情

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

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

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 (list<edge>::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; } };

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

#p#分页标题#e#

#p#副标题#e#

Network<char, int, Link<char, int> > a(100);

//插入点、边……

Weight<char, int, Link<char, int> > b(&a);

#include "Network.h"

template <class name, class dist, class mem>

class Weight

{

public:

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

Network<name, dist, mem>* G;

};

发明有告终构函数真好，算法的功效数组的初始化和算法自己分隔了，这样一来，算法的根基步调就很容易看清楚了。

#p#副标题#e#

所有极点之间的最短路径（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算法的退化版本。

#p#副标题#e#

显然，Floyed算法是颠末N次N2条边迭代而发生最短路径的；假如我们想把时间巨大度从O(n3) 降到预期的O(n2)，就必需把N次迭代的N2条边变为N条边，也就是说每次参加迭代的只有一条边——问题是如何找到这条边。

先看看边的权值非负的环境。假设从极点0出发，到各个极点的间隔是a1,a2……，那么，这个中的最短间隔an肯定是从0到n号极点的最短间隔。这是因为，假如an不是从0到n号极点的最短间隔，那么一定是中间颠末尾某个极点；但此刻边的权值非负，一个比此刻这条边还长的边再加上另一条非负的边，是不行能比这条边短的。从这个道理出发，就能得出Dijkstra算法，留意，这个和Prim算法极其相似，不知道谁参考了谁；但这也是不免的工作，因为他们的道理是一样的。

#p#分页标题#e#

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)。不外，何须让边的权值为负值呢？照旧那句话，公道的并欠好用。

#p#副标题#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算法，也能带来效率的晋升。

#p#分页标题#e#

可是，每一步的进化实际上都陪伴着附加条件的引入。从Floyed到Dijkstra是边上的权值非负，假如这个条件不创立，那么就只能退化成Bellman-Ford算法。从Dijkstra到A*是别的的判定准则的引入（本文中是两点之间直线最短），假如这个条件不创立，同样的，只能回收不完整的Dijkstra（求到目标极点竣事算法）。

#p#副标题#e#

勾当网络（AOV、AOE）

这部门是和工程相关的，也就是说，当AOV、AOE很巨大的时候，才气显示出这部门的代价——简朴的话，手工都要比措施快，输入数据那段时间手工功效就出来了。我也没什么例子好举，总给我一种没底气的感受，勉为其难的把措施写完就算完事吧。和前边的对比，这部门专业了一点，换而言之，不是每小我私家都感乐趣，不想看就跳已往吧。

筹备事情

勾当网络主要有两个算法，拓扑排序和求要害路径，后者以前者为基本。模拟上篇，别的结构一个“算法类”，需要算法时，将图绑定到算法上。

#include "Network.h" #define iterator list<Link<name, 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(Network<name, dist, Link<name, dist> >* G) : G(G), N(G->vNum()), outCriAct(CA) { count = new int[N]; result = new int[N]; } ~ActivityNetwork() { delete []count; delete []result; } const vector<CriAct>& 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; } Network<name, dist, Link<name, dist> >* G; vector<CriAct> CA; int N, *count, *result; };

因为AOV和AOE的边都不会太多（想象一下边多的环境，那事件就都是鸡毛蒜皮了），所以储存布局直接选择了连接表。而且为了浮现连接表的优势，需要直接操纵私有数据，因此要把这个类声明为Link类和Network类的友元，别的由于这个类在后头，所以需要前视声明。详细如下：

#p#副标题#e#

template <class name, class dist> class ActivityNetwork;

template <class name, class dist> class Link

{friend class ActivityNetwork<name, dist>;};

template <class name, class dist, class mem> class Network

{ friend class ActivityNetwork<name, 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() { Network<int, int, Link<int, 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); ActivityNetwork<int, int> b(&a); if (b.TopoSort()) for (int i = 0; i < a.vNum(); i++) cout << b.out[i] << ' '; return 0; }

要害路径

#p#副标题#e#

有了拓扑排序的功效，这个措施就较量好写了，那些所谓的“能力”就不消了，如下的措施，很直白，算法说明请参考教科书。

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->cost>Ve[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引用。如下的测试措施，数据来自殷版：

#p#分页标题#e#

#include <iostream> using namespace std; #include "ActivityNetwork.h" int main() { Network<int, int, Link<int, 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); ActivityNetwork<int, 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++语言描写》这本书，将图的最小生成树、最短路径、拓扑排序算法放到了贪婪算法里讲授，是一种更为公道的布置。

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

关键字：