# 数据结构学习（C++）——图【3】（无向图）（下） (转)

### 最小生成树的储存

template

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算法

{

MinHeap > E; int i, j, k, l = 0;

MFSets V(vNum); list::iterator iter;

for (i = 0; i < vNum; i++)

for (iter = vertices[i].e->begin(); iter != vertices[i].e->end(); iter++)

E.insert(MSTedge(i, iter->vID, iter->cost));//建立边的堆XML:namespace prefix = o ns = "urn:schemas-microsoft-com:Office:office" />

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

using namespace std;

#define minchild(i) (heap[i*2+1]

template

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 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算法

{

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

bool Graph::MinSpanTree()

{

MSTedge* a = new MSTedge[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;

}

#include

using namespace std;

#include "Graph.h"

int main()

{

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;

}

• 博文量
3983
• 访问量
7384473