数据结构中图的应用

1、 图在数据结构中应用十分广泛，对于图来说最重要的当然是算法，而且相当的一部分都是很专业的，一般的人几乎不会接触到；相对而言，结构就显得分量很轻。你可以看到关于图中元素的操作很少，远没有单链表那里列出的一大堆“接口”。一个结构如果复杂，那么能确切定义的操作就很有限。基本储存方法不管怎么说，还是先得把图存起来。不要看书上列出了好多方法，根本只有一个邻接矩阵。如果矩阵是稀疏的，那就可以用十字链表来储存矩阵（见前面的稀疏矩阵（十字链表）。如果我们只关系行的关系，那么就是邻接表（出边表）；反之，只关心列的关系，就是逆邻接表（入边表）。下面给出两种储存方法的实现。#ifndef Graphmem_H#de

2、fine 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 AdjMatrixfriend class Network<name, dist, AdjMatrix<name, dist> >public:A

3、djMatrix() : vNum(0), eNum(0)vertex = new namemaxV; edge = new dist*maxV;for (int i = 0; i < maxV; i+) edgei = new distmaxV;AdjMatrix()for (int i = 0; i < maxV; i+) delete edgei;delete edge; delete vertex;bool insertV(name v)if (find(v) return false;vertexvNum = v;for (int i = 0; i < maxV;

4、i+) edgevNumi = 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 (edgeij != NoEdge) return false;edgeij = cost; eNum+; return true;name& getV(int n) return vertexn; /没有越界检查int nextV(int m, int n)/返回m号顶点的第n号顶点后第一

5、个邻接顶点号，无返回-1for (int i = n + 1; i < vNum; i+) if (edgemi != 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 = vertexi) return true;return false;bool find(const name& v, int& i)for (i = 0;

6、 i < vNum; i+) if (v = vertexi) return true;return false;template <class name, class dist>class LinkedListfriend class Network<name, dist, LinkedList<name, dist> >public:LinkedList() : vNum(0), eNum(0) LinkedList()for (int i = 0; i < vNum; i+) delete verticesi.e;bool insertV(

7、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 = verticesi.e->begin(

8、);iter != verticesi.e->end() && iter->vID < j; iter+);if (iter = verticesi.e->end()verticesi.e->push_back(edge(j, cost); eNum+; return true;if (iter->vID = j) return false;verticesi.e->insert(iter, edge(j, cost); eNum+; return true;name& getV(int n) return verticesn.

9、v; /没有越界检查int nextV(int m, int n)/返回m号顶点的第n号顶点后第一个邻接顶点号，无返回-1for (list<edge>:iterator iter = verticesm.e->begin();iter != verticesm.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 = vertice

10、si.v) return true;return false;bool find(const name& v, int& i)for (i = 0; i < vNum; i+) if (v = verticesi.v) return true;return false;struct edgeedge() edge(int vID, dist cost) : vID(vID), cost(cost) int vID;dist cost;struct vertexvertex() vertex(name v, list<edge>* e) : v(v), e(e)

11、 name v;list<edge>* e;int vNum, eNum;vector<vertex> vertices;#endif这个实现是很简陋的，但应该能满足后面的讲解了。现在这个还什么都不能做，不要急，在下篇将讲述图的DFS和BFSDFS和BFS对于非线性的结构，遍历都会首先成为一个问题。和二叉树的遍历一样，图也有深度优先搜索（DFS）和广度优先搜索（BFS）两种。不同的是，图中每个顶点没有了祖先和子孙的关系，因此，前序、中序、后序不再有意义了。仿照二叉树的遍历，很容易就能完成DFS和BFS，只是要注意图中可能有回路，因此，必须对访问过的顶点做标记。 最基本的

12、有向带权网#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) re

13、turn 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(na

14、me v) cout << v; private: mem data; ; #endif 你可以看到，这是在以mem方式储存的data上面加了一层外壳。在图这里，逻辑上分有向、无向，带权、不带权；储存结构上有邻接矩阵和邻接表。也就是说分开来有8个类。为了最大限度的复用代码，继承关系就非常复杂了。但是，多重继承是件很讨厌的事，什么覆盖啊，还有什么虚拟继承，我可不想花大量篇幅讲语言特性。于是，我将储存方式作为第三个模板参数，这样一来就省得涉及虚拟继承了，只是这样一来这个Network的实例化就很麻烦了，不过这可以通过typedef或者外壳类来解决，我就不写了。反正只是为了让大家明白，真

15、正要用的时候，最好是写专门的类，比如无向无权邻接矩阵图，不要搞的继承关系乱七八糟。 DFS和BFS的实现public: void DFS(void(*visit)(name v) = print) visited = new boolvNum(); for (int i = 0; i < vNum(); i+) visitedi = false; DFS(0, visit); delete visited; protected: void DFS(int i, void(*visit)(name v) = print) visit(getV(i); visitedi = true; fo

16、r (int n = nextV(i); n != -1; n = nextV(i, n) if (!visitedn) DFS(n, visit); public: void BFS(int i = 0, void(*visit)(name v) = print)/n没有越界检查 visited = new boolvNum(); queue<int> a; int n; for (n = 0; n < vNum(); n+) visitedn = false; visitedi = true; while (i != -1)/这个判断可能是无用的 visit(getV(i

17、); for (n = nextV(i); n != -1; n = nextV(i, n) if (!visitedn) a.push(n); visitedn = true; if (a.empty() break; i = a.front(); a.pop(); delete visited; DFS和BFS函数很难写得像树的遍历方法那么通用，这在后面就会看到，虽然我们使用了DFS和BFS的思想，但是上面的函数却不能直接使用。因为树的信息主要在节点上，而图的边上还有信息。 测试程序#include <iostream> using namespace std; #includ

18、e "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'

19、;, 3); cout << "DFS: " a.DFS(); cout << endl; cout << "BFS: " a.BFS(); cout << endl; return 0; 老实说，这个类用起来真的不是很方便。不过能说明问题就好。 无向图要是在纸上随便画画，或者只是对图做点示范性的说明，大多数人都会选择无向图。然而在计算机中，无向图却是按照有向图的方法来储存的存两条有向边。实际上，当我们说到无向的时候，只是忽略方向在纸上画一条线，难不成那线“嗖”的就出现了，不是从一头到另一头画出来的？ 无向

20、图有几个特有的概念，连通分量、关节点、最小生成树。下面将分别介绍，在此之前，先完成无向图类的基本操作。无向图类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

21、, mem>:insertE(v1, v2, cost)return Network<name, dist, mem>:insertE(v2, v1, cost);return false;仅仅是添加边的时候，再添加一条反向边，很简单。连通分量这是无向图特有的，有向图可要复杂多了（强、单、弱连通），原因就是无向图的边怎么走都行，有向图的边好像掉下无底深渊就再也爬不上来了。有了DFS，求连通分量的算法就变得非常简单了对每个没有访问的顶点调用DFS就可以了。void components()visited = new boolvNum(); int i, j = 0;for (i

22、 = 0; i < vNum(); i+) visitedi = false;cout << "Components:" << endl;for (i = 0; i < vNum(); i+)if (!visitedi) cout << '(' << +j << ')' DFS(i); cout << endl; delete visited;关节点下定义是人们认识事物的一个方法，因为概念使得人们能够区分事物关于这个还有个绝对的运动和相对的静止的哲学观点（河水

23、总在流，但是长江还叫长江，记得那个著名的“不可能踏进同一条河里”吗？）因此，能否有个准确的概念往往是一门学科发展程度的标志，而能否下一个准确的定义反映了一个人的思维能力。说这么多废话，原因只有一个，我没搞清楚什么叫“关节点”参考书有限，不能仔细的考究了，如有误解，还望指正。严版是这么说的：如果删除某个顶点，将图的一个连通分量分割成两个或两个以上的连通分量，称该顶点为关节点。虽然没有提到图必须是无向的，但是提到了连通分量已经默认是无向图了。殷版是这么说的：在一个无向连通图中，（余下同严版）。问题出来了，非连通图是否可以讨论含有关节点？我们是否可以说某个连通分量中含有关节点？遗憾的是，严版留下这个

24、问题之后，在后面给出的算法是按照连通图给的，这样当图非连通时结果就是错的。殷版更是滑头，只输出重连通分量，不输出关节点，自己虽然假定图是连通的，同样没有连通判断。翻翻离散数学吧，结果没找到什么“关节点”，只有“割点”，是这样的：一个无向连通图，如果删除某个顶点后，变为非连通图，该顶点称为割点。权当“割点”就是“关节点”，那么算法至少也要先判断是否连通吧？可是书上都直接当连通的了关于算法不再细说，书上都有。下面的示例，能输出每个连通分量的“关节点”（是不是可以这样叫，我也不清楚）。dfn储存的是每个顶点的访问序号，low是深度优先生成树上每个非叶子顶点的子女通过回边所能到达的顶点最小的访问序号。

25、把指向双亲的边也当成回边并不影响判断，因此不必特意区分，殷版显式区分了，属于画蛇添足。这样一来，if (lown >= dfni) cout << getV(i);这个输出关节点的判断中的>=就显得很尴尬了，因为只能等于不可能大于。还要注意的是，生成树的根（DFS的起始点）是单独判断的。void articul()dfn = new intvNum(); low = new intvNum(); int i, j = 0, n;for(i = 0; i < vNum(); i+) dfni = lowi = 0;/初始化for (i = 0; i < vNu

26、m(); i+)if (!dfni)cout << '(' << +j << ')' dfni = lowi = count = 1;if (n = nextV(i) != -1) articul(n); bool out = false;/访问树根while (n = nextV(i, n) != -1)if (dfnn) continue;if (!out) cout << getV(i); out = true; /树根有不只一个子女articul(n);/访问其他子女cout << endl;d

27、elete dfn; delete low;private:void articul(int i)dfni = lowi = +count;for (int n = nextV(i); n != -1; n = nextV(i, n)if (!dfnn)articul(n);if (lown < lowi) lowi = lown;if (lown >= dfni) cout << getV(i);/这里只可能else if (dfnn < lowi) lowi = dfnn;/回边判断int *dfn, *low, count; 最小生成树说人是最难伺候的，真是

28、一点不假。上面刚刚为了“提高可靠性”添加了几条多余的边，这会儿又来想办法怎么能以最小的代价把所有的顶点都连起来。可能正是人的这种精神才使得人类能够进步吧看着现在3GHz的CPU真是眼红啊，我还在受500MHz的煎熬，然后再想想8086 正如图的基本元素是顶点和边，从这两个方向出发，就能得到两个算法Kruskal算法（从边出发）、Prim算法（从顶点出发）。据说还有别的方法，恕我参考资料有限，不能详查。 最小生成树的储存显然用常用的树的储存方法来储存没有必要，虽然名曰“树”，实际上，这里谁是谁的“祖先”、“子孙”并不重要。因此，用如下的MSTedge结构数组来储存就可以了。 template &

29、lt;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 = (cons

30、t MSTedge& v2) return (cost = v2.cost); ; Kruskal算法最小生成树直白的讲就是，挑选N1条不产生回路最短的边。Kruskal算法算是最直接的表达了这个思想在剩余边中挑选一条最短的边，看是否产生回路，是放弃，不是选定然后重复这个步骤。说起来倒是很简单，做起来就不那么容易了判断是否产生回路需要并查集，在剩余边中找一条最短的边需要最小堆（并不需要对所有边排序，所以堆是最佳选择）。 Kruskal算法的复杂度是O(eloge)，当e接近N2时，可以看到这个算法不如O(N2)的Prim算法，因此，他适合于稀疏图。而作为稀疏图，通常用邻接表来储存比较好

31、。另外，对于邻接矩阵储存的图，Kruskal算法比Prim算法占不到什么便宜（初始还要扫描N2条“边”）。因此，最好把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;

32、 i < vNum; i+) for (iter = verticesi.e->begin(); iter != verticesi.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)

33、; al = E.top(); l+; E.pop(); return l; 下面是堆和并查集的实现 #ifndef Heap_H #define Heap_H #include <vector> using namespace std; #define minchild(i) (heapi*2+1<heapi*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)

34、; const T& top() return heap0; void pop() heap0 = heap.back(); heap.pop_back(); FilterDown(0); private: void FilterUp(int i) for (int j = (i - 1) / 2; j >= 0 && heapj > heapi; i = j, j = (i - 1) / 2) si, heapj); void FilterDown(int i) for (int j = minchild(i); j < heap.size() &a

35、mp;& heapj < heapi; i = j, j = minchild(i) si, heapj); vector<T> heap; ; #endif #ifndef MFSets_H #define MFSets_H class MFSets public: MFSets(int maxsize) : size(maxsize) parent = new intsize + 1; for (int i = 0; i <= size; i+) parenti = -1; MFSets() delete parent; void merge(int roo

36、t1, int root2)/root1!=root2 parentroot2 = root1; int find(int n) if (parentn < 0) return n; return find(parentn); private: int size; int* parent; ; #endif Prim算法如果从顶点入手，就能得到另一种方法。从只含有一个顶点的集合开始，寻找集合外面的顶点到这个集合里的顶点最近的一条边，然后将这个顶点加入集合，修改因为这个顶点的加入而使得集合外面的顶点到集合里的顶点的最短距离产生变化的分量。因为需要对每个顶点扫描，邻接矩阵储存的图是最合适Pr

37、im算法的。 template <class name, class dist> int AdjMatrix<name, dist>:MinSpanTree(MSTedge<dist>* a) dist* lowC = new distvNum; int* nearV = new intvNum; int i, j, k; for (i = 0; i < vNum; i+) lowCi = edge0i; nearVi = 0; nearV0 = -1; for (k = 0; k < vNum-1; k+)/Prim Start for (i

38、= 1, j = 0; i < vNum; i+) if (nearVi != -1 && lowCi < lowCj) j = i;/find low cost ak = MSTedge<dist>(nearVj, j, lowCj); nearVj = -1; /insert MST if (ak.cost = NoEdge) return k - 1;/no edge then return for (i = 1; i < vNum; i+)/modify low cost if (nearVi != -1 && edgeij

39、 < lowCi) lowCi = edgeij; nearVi = j; return k; 【附注】这里需要说明一下，对于edgeII这样的是应该是0呢还是NoEdge呢？显然0合理，但是不好用。并且，从有权图无权图统一的角度来说，是NoEdge更好。因此，在我的有权图的邻接矩阵中，主对角线上的元素是NoEdge，而不是书上的0。 测试程序储存和操作分离，没想到得到了一个有趣的结果对于最后的无向图而言，最小生成树的算法对外表现不知道是采用了那个算法。 template <class name, class dist, class mem> bool Graph<na

40、me, 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;/不够N1条边，不是生成树 for (int i = 0; i < n; i+) cout << '(' << getV(ai.v1) << ',' << get

41、V(ai.v2) << ')' << ai.cost << ' ' sum += ai.cost; cout << endl << "MinCost: " << sum << endl; delete a; return true; 最后的测试图的数据取自殷版（C+）不知是这组数据好是怎么的，殷版居然原封不动的照抄了数据结构算法与应用-C+语言描述（中文译名） #include <iostream> using namespace std; #in

42、clude "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

43、', '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

44、', 18); a.insertE('E', 'G', 24); a.MinSpanTree(); return 0; 最短路径最短路径恐怕是图的各种算法中最能吸引初学者眼球的了在地图上找一条最短的路或许每个人都曾经尝试过。下面我们用计算机来完成我们曾经的“愿望”。在图的算法中有个有趣的现象，就是问题的规模越大，算法就越简单。图是个复杂的结构，对于一个特定问题，求解特定顶点的结果都会受到其他顶点的影响就好比一堆互相碰撞的球体，要求解特定球体的状态，就必须考虑其他球体的状态。既然每个顶点都要扫描，如果对所有的顶点都求解，那么算法就非常的简单无非是遍历吗。然

45、而，当我们降低问题规模，那很自然的，我们希望算法的规模也降低如果不降低，不是杀鸡用牛刀？但是，正是由于图的复杂性，使得这种降低不容易达到，因此，为了降低算法的规模，使得算法就复杂了。在下面的介绍中，清楚了印证了上面的结论。人的认知过程是从简单到复杂，虽然表面看上去，求每对顶点之间的最短路径要比特定顶点到其他顶点之间的最短路径复杂，但是，就像上面说的，本质上，前者更为简单。下面的介绍没有考虑历史因素（就是指哪个算法先提出来），也没有考虑算法提出者的真实想法（究竟是谁参考了或是没参考谁），只是从算法本身之间的联系来做一个阐述，如有疏漏，敬请原谅。准备工作一路走下来，图类已经很“臃肿”了，为了更清晰

46、的说明问题，需要“重起炉灶另开张”，同时也是为了使算法和储存方法分开，以便于复用。首先要为基本图类添加几个接口。template <class name, class dist, class mem>class Networkpublic: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;

47、 ;template <class name, class dist>class AdjMatrixpublic:dist& getE(int m, int n) return edgemn; ;template <class name, class dist>class Linkpublic:dist& getE(int m, int n)for (list<edge>:iterator iter = verticesm.e->begin();iter != verticesm.e->end() && iter-

48、>vID < n; iter+);if (iter = verticesm.e->end() return NoEdge;if (iter->vID = n) return iter->cost;return NoEdge;然后就是为了最短路径算法“量身定做”的“算法类”。求某个图的最短路径时，将图绑定到算法上，例如这样：Network<char, int, Link<char, int> > a(100);/插入点、边Weight<char, int, Link<char, int> > b(&a);#in

49、clude "Network.h"template <class name, class dist, class mem>class Weightpublic:Weight(Network<name, dist, mem>* G) : G(G), all(false), N(G->vNum()length = new dist*N; path = new int*N;shortest = new boolN; int i, j;for (i = 0; i < N; i+)lengthi = new distN; pathi = new i

50、ntN;for (i = 0; i < N; i+)shortesti = false;for (j = 0; j < N; j+)lengthij = G->getE(i, j);if (lengthij != G->NoEdge() pathij = i;else pathij = -1;Weight()for (int i = 0; i < N; i+) delete lengthi; delete pathi; delete length; delete path; delete shortest;private:void print(int i, int

51、 j)if (pathij = -1) cout << "No Path" << endl; return;cout << "Shortest Path: " out(i, j); cout << G->getV(j) << endl;cout << "Path Length: " << lengthij << endl;void out(int i, int j)if (pathij != i) out(i, pathij);cou

52、t << G->getV(pathij) << "->"dist* length; int* path; bool* shortest; bool all; int N;Network<name, dist, mem>* G;发现有了构造函数真好，算法的结果数组的初始化和算法本身分开了，这样一来，算法的基本步骤就很容易看清楚了。所有顶点之间的最短路径（Floyed算法）从v1到v2的路径要么是v1->v2，要么中间经过了若干顶点。显然我们要求的是这些路径中最短的一条。这样一来，问题就很好解决了最初都是源点到目的点，然后依

53、次添加顶点，使得路径逐渐缩短，顶点都添加完了，算法就结束了。void AllShortestPath()/Folyedif (all) return;for (int k = 0; k < N; k+)shortestk = true;for (int i = 0; i < N; i+)for (int j = 0; j < N; j+)if (lengthik + lengthkj < lengthij)lengthij = lengthik + lengthkj;pathij = pathkj;all = true;单源最短路径（Dijkstra算法）仿照上面的Fl

54、oyed算法，很容易的，我们能得出下面的算法：void ShortestPath(int v1)/Bellman-Fordfor (int k = 2; k < N; k+)for (int i = 0; i < N; i+)for (int j = 0; j < N; j+)if (lengthv1j + lengthji < lengthv1i)lengthv1i = lengthv1j + lengthji;pathv1i = j;这就是Bellman-Ford算法，可以看到，采用Floyed算法的思想，不能使算法的时间复杂度从O(n3)降到预期的O(n2)，只是

55、空间复杂度从O(n2)降到了O(n)，但这也是应该的，因为只需要原来结果数组中的一行。因此，我并不觉得这个算法是解决“边上权值为任意值的单源最短路径问题”而专门提出来的，是Dijkstra算法的“推广”版本，他只是Floyed算法的退化版本。显然，Floyed算法是经过N次N2条边迭代而产生最短路径的；如果我们想把时间复杂度从O(n3) 降到预期的O(n2)，就必须把N次迭代的N2条边变为N条边，也就是说每次参与迭代的只有一条边问题是如何找到这条边。先看看边的权值非负的情况。假设从顶点0出发，到各个顶点的距离是a1,a2，那么，这其中的最短距离an必定是从0到n号顶点的最短距离。这是因为，如果

56、an不是从0到n号顶点的最短距离，那么必然是中间经过了某个顶点；但现在边的权值非负，一个比现在这条边还长的边再加上另一条非负的边，是不可能比这条边短的。从这个原理出发，就能得出Dijkstra算法，注意，这个和Prim算法极其相似，不知道谁参考了谁；但这也是难免的事情，因为他们的原理是一样的。void ShortestPath(const name& vex1, const name& vex2)/Dijkstraint v1 = G->find(vex1); int v2 = G->find(vex2);if (shortestv1) print(v1, v2);

57、 return; bool* S = new boolN; int i, j, k;for (i = 0; i < N; i+) Si = false; Sv1 = true;for (i = 0; i < N - 1; i+)/Dijkstra Start, like Prim?for (j = 0, k = v1; j < N; j+)if (!Sj && lengthv1j < lengthv1k) k = j;Sk = true;for (j = 0; j < N; j+)if (!Sj && lengthv1k + lengthkj < lengthv1j)lengthv1j = lengthv1k + lengthkj