1381人阅读
数据结构（21）
#ifndef __GRAPH__
#define __GRAPH__
#include &iostream&
#include &queue&
class DisjointS
template &class TypeOfEdge&
class Graph {
virtual bool insert(int u, int v, TypeOfEdge weight) = 0;
virtual bool remove(int u, int v) = 0;
virtual bool modify(int u, int v, TypeOfEdge weight) = 0;
virtual bool exist(int u, int v) const = 0;
virtual int numOfVer() const {}
virtual int numOfEdge() const {}
protected:
//有向加权图的邻接表实现
//作为无权图使用时，可将weight置1，权值一样
//作为无向图使用时，插入和删除时需将两个方向的边均插入或删除，修改weight时同样
template &class TypeOfVer, class TypeOfEdge&
class AdjListGraph : public Graph&TypeOfEdge&{
//这里为了方便，所有成员函数写成内联函数的形式
//构造一个只有结点没有边的图
AdjListGraph(int v, const TypeOfVer *d, bool isWeightedFlag, bool isDirectedFlag){
edges = 0;
isWeighted = isWeightedF
isDirected = isDirectedF
verList = new VerNode[vers];
for (int i = 0; i & ++i) {
verList[i].ver = d[i];
~AdjListGraph(){
for (int i = 0; i & ++i) {
EdgeNode *p, *
p = verList[i].
while (p != NULL){
delete [] verL
bool insert(int u, int v, TypeOfEdge weight = 0) {
if (u & 0 || u & vers - 1 || v & 0 || v & vers - 1)
if (exist(u, v))
verList[u].head = new EdgeNode(v, weight, verList[u].head);
if (!isDirected)
verList[v].head = new EdgeNode(u, weight, verList[v].head);
bool remove(int u, int v) {
bool flag = removeCore(u, v);
if (!isDirected)
flag &= removeCore(v, u);
bool removeCore(int u, int v) {
if (u & 0 || u & vers - 1 || v & 0 || v & vers - 1)
EdgeNode *p = verList[u].
if (p == NULL){
//删除结点为头结点
if (p-&end == v){
verList[u].head = p-&
//找到删除结点或找不到
EdgeNode *pre =
while (p != NULL && p-&end != v) {
if (p == NULL){
pre-&next = p-&
bool modify(int u, int v, TypeOfEdge weight) {
bool flag = modifyCore(u, v, weight);
if (!isDirected)
flag &= modifyCore(v, u, weight);
bool modifyCore(int u, int v, TypeOfEdge weight) {
EdgeNode *p = verList[u].
while (p != NULL && p-&end != v) {
if (p == NULL) {
p-&weight =
bool exist(int u, int v) const {
EdgeNode *p = verList[u].
while (p != NULL && p-&end != v) {
if (p == NULL) {
//深度优先遍历
void dfs(int startVer = 0) const {
bool *visited = new bool[vers];
for (int i = 0; i & ++i)
visited[i] =
int j = 0;
for (int i = startV i & vers + startV ++i){
if (visited[j])
dfsCore(j, visited);
cout && //每一行为一棵深度优先生成树
//广度优先遍历
void bfs(int startVer = 0) const {
bool *visited = new bool[vers];
for (int i = 0; i & ++i)
visited[i] =
queue&int&
int j = 0;
for (int i = startV i & vers + startV ++i){
if (visited[j])
q.push(j);
while (!q.empty()) {
//访问当前结点
int v = q.front();
if (visited[v])
cout && verList[v].ver && '\t';
visited[v] =
//当前结点的后继结点放入队列
EdgeNode *p = verList[v].
while (p != NULL) {
if (!visited[p-&end]) {
q.push(p-&end);
cout && //每一行为一棵广度优先生成树
//欧拉回路
void eulerCircuit(TypeOfVer start) {
if (edges == 0)
for (int i = 0; i & ++i) {
int degree = 0;
EdgeNode *p = verList[i].
while (p != NULL) {
//度数为0或奇数，不存在欧拉回路
if ((degree == 0) || (degree & 0x1))
//找到起始点序号
int iStart = 0;
for (iStart = 0; iStart & ++iStart){
if (verList[iStart].ver == start)
if (iStart == vers)
//保存一个备份
VerNode *tmp = clone();
//找到第一条路径(起点所有的边已被访问)
EulerNode *beg, *
eulerCircuitCore(iStart, beg, end);
EulerNode *p, *
while (true) {
while (p != NULL) {
if (verList[p-&nodeNum].head != NULL)
if (p == NULL)
//从某一个未访问的边开始找一条路径
EulerNode *begTmp, *endT
eulerCircuitCore(p-&nodeNum, begTmp, endTmp);
pre-&next = begT
endTmp-&next = p-&
//恢复原图
delete [] verL
while (p != NULL) {
cout && verList[p-&nodeNum].ver && '\t';
//拓扑排序
void topologySort() const {
//计算入度
int *inDegree = new int[vers];
memset(inDegree, 0, vers * sizeof(int));
for (int i = 0; i & ++i){
EdgeNode *p = verList[i].
while (p != NULL) {
++inDegree[p-&end];
//入度为0的放入队列
queue&int&
for (int i = 0; i & ++i){
if (inDegree[i] == 0)
q.push(i);
while (!q.empty()) {
int v = q.front();
cout && verList[v].ver && '\t';
//入度减1, 为0的放入队列
EdgeNode *p = verList[v].
while (p != NULL) {
--inDegree[p-&end];
if (inDegree[p-&end] == 0) {
q.push(p-&end);
//kruskal算法求最小生成树( 时间复杂度O(|E|log|E|) )
void kruskal() const {
priority_queue&Edge, deque&Edge&, greater&Edge&&
//priority_queue&Edge, deque&Edge&, compEdgeGreater&
//priority_queue&Edge&
//默认最大堆
DisjointSet ds(vers);
//所有边放入优先级队列
for (int i = 0; i & ++i) {
EdgeNode *p = verList[i].
while (p != NULL) {
if (i & p-&end) { //只添加一次
Edge edge(i, p-&end, p-&weight);
pq.push(edge);
//合并生成最小生成树
int count = 0;
while (count & vers - 1) {
Edge edge = pq.top();
int u = ds.find(edge.beg);
int v = ds.find(edge.end);
if (u != v) {
ds.unionTwoSet(u, v);
cout && &(& && verList[edge.beg].ver && &,& && verList[edge.end].ver && &)\t&;
//prim算法求最小生成树( 时间复杂度O(|V^2|) )
void prim(TypeOfEdge noEdge) const {
//顶点集合V, 最小生成树结点集合U, 剩余结点V-U
bool *flag = new bool[vers];
//结点在U中为true
TypeOfEdge *lowCost = new TypeOfEdge[vers]; //U中结点到结点i的最小权值, 当i在U中时lowCost为noEdge, 当i在V-U中时lowCost为有限值
int *startNode = new int[vers];
//U中结点startNode[i]到结点i的权值是lowCost[i]
for (int i = 0; i & ++i) {
lowCost[i] = noE
int start = 0;
int current =
//current是即将加入到U中的结点
for (int i = 1; i & ++i) {
EdgeNode *p = verList[current].
while (p != NULL) {
if (!flag[p-&end] && p-&weight & lowCost[p-&end]) { //结点p-&end不在U中, 并且结点p-&end到结点current的距离小于结点p-&end到U中已有点的最小距离
lowCost[p-&end] = p-&
startNode[p-&end] =
//current加入U
flag[current] =
//寻找V-U中到V-U的最小距离点
TypeOfEdge min = noE
bool tflag =
for (int j = 0; j & ++j) {
if (lowCost[j] & min) {
min = lowCost[j];
//取V-U中到U的最小距离点作为下一个计算点
if (!tflag) {
//在V-U中随意取一个点，与上面的方法结果一致
cout && &(& && verList[startNode[current]].ver && &,& && verList[current].ver && &)\t&;
lowCost[current] = noE
delete [] lowC
delete [] startN
//非加权图的单源最短路径( bfs算法, 时间复杂度为|V|和|E|中的较小者, 即O(|V| + |E|) )
void unweightedShortDistance(TypeOfVer start, TypeOfEdge noEdge) const {
//找到起始点序号
int iStart = 0;
for (iStart = 0; iStart & ++iStart) {
if (verList[iStart].ver == start)
if (iStart == vers)
TypeOfEdge *distance = new TypeOfEdge[vers];
int *prev = new int[vers];
for (int i = 0; i & ++i) {
distance[i] = noE
distance[iStart] = 0;
prev[iStart] = iS
queue&int&
q.push(iStart);
while (!q.empty()) {
int u = q.front();
EdgeNode *p = verList[u].
while (p != NULL) {
if (distance[p-&end] == noEdge) {
distance[p-&end] = distance[u] + 1;
prev[p-&end] =
q.push(p-&end);
for (int i = 0; i & ++i) {
cout && &the path from & && start && & to &
&& verList[i].ver && &: &;
printPath(iStart, i, prev);
//加权图的单源最短路径(dijkstra算法与prim算法有些类似, 时间复杂度O(|V^2|) )
void dijkstra(TypeOfVer start, TypeOfEdge noEdge) const {
//找到起始点序号
int iStart = 0;
for (iStart = 0; iStart & ++iStart) {
if (verList[iStart].ver == start)
if (iStart == vers)
//顶点集合V, 已经找到最短路径的顶点集合U, 剩余结点V-U
TypeOfEdge *distance = new TypeOfEdge[vers];
//结点i到起始点的最短距离
bool *konwn = new bool[vers];
//结点在U中为true
int *prev = new int[vers];
//结点i的前继结点
for (int i = 0; i & ++i) {
distance[i] = noE
konwn[i] =
distance[iStart] = 0;
prev[iStart] = iS
int current = iS
for (int i = 1; i & ++i) {
//寻找V-U中到U中的最小距离点
TypeOfEdge min = noE
for (int j = 0; j & ++j) {
if (!konwn[j] && distance[j] & min) {
min = distance[j];
konwn[current] =
EdgeNode *p = verList[current].
while (p != NULL) {
if (!konwn[p-&end] && min + p-&weight & distance[p-&end]) {
distance[p-&end] = min + p-&
prev[p-&end] =
for (int i = 0; i & ++i) {
cout && &the path from & && start && & to &
&& verList[i].ver && &: &;
printPath(iStart, i, prev);
cout && &\twith length: & && distance[i] &&
//带负权值图的单源最短路径(可以有环, 但不能有负环, 时间复杂度O(|V||E|) )
void weightedNegative(TypeOfVer start, TypeOfEdge noEdge) const {
//找到起始点序号
int iStart = 0;
for (iStart = 0; iStart & ++iStart) {
if (verList[iStart].ver == start)
if (iStart == vers)
TypeOfEdge *distance = new TypeOfEdge[vers];
int *prev = new int[vers];
for (int i = 0; i & ++i) {
distance[i] = noE
distance[iStart] = 0;
prev[iStart] = iS
queue&int&
q.push(iStart);
while (!q.empty()) {
int u = q.front();
EdgeNode *p = verList[u].
while (p != NULL) {
if (distance[u] + p-&weight & distance[p-&end]) {
distance[p-&end] = distance[u] + p-&
prev[p-&end] =
q.push(p-&end);
for (int i = 0; i & ++i) {
cout && &the path from & && start && & to &
&& verList[i].ver && &: &;
printPath(iStart, i, prev);
cout && &\twith length: & && distance[i] &&
struct EdgeNode {
EdgeNode *
EdgeNode(int e, TypeOfEdge w, EdgeNode *n = NULL):end(e), weight(w), next(n) {}
struct VerNode {
EdgeNode *
VerNode(EdgeNode *h = NULL):head(h){}
VerNode(TypeOfVer v, EdgeNode *h = NULL):ver(v), head(h){}
VerNode *verL
void dfsCore(int start, bool *visited) const {
cout && verList[start].ver && '\t';
visited[start] =
EdgeNode *p = verList[start].
while (p != NULL) {
if (!visited[p-&end])
dfsCore(p-&end, visited);
struct EulerNode {
EulerNode *
EulerNode(int num, EulerNode *n = NULL):nodeNum(num), next(n) {}
VerNode *clone() const {
VerNode *tmp = new VerNode[vers];
for (int i = 0; i & ++i){
tmp[i].ver = verList[i].
EdgeNode *p = verList[i].
while (p != NULL) {
tmp[i].head = new EdgeNode(p-&end, p-&weight, tmp[i].head);
void eulerCircuitCore(int start, EulerNode *&beg, EulerNode *&end) {
beg = end = new EulerNode(start);
while (verList[start].head != NULL) {
int nextNodeNum = verList[start].head-&
remove(start, nextNodeNum);
//remove(nextNodeNum, start);
end-&next = new EulerNode(nextNodeNum);
end = end-&
start = nextNodeN
struct Edge {
Edge(int b, int e, TypeOfEdge w):beg(b), end(e),weight(w) {}
bool operator&(const Edge &right) const {
return weight & right.
struct compEdgeGreater {
bool operator()(Edge first, Edge second) {
return first.weight & second.
void printPath(int start, int end, int *prev) const {
if (start == end) {
cout && verList[start].
printPath(start, prev[end], prev);
cout && &-& && verList[end].
//有向加权图的邻接矩阵实现
//作为无权图使用时，可将weight置1，权值一样
//作为无向图使用时，插入和删除时需将两个方向的边均插入或删除，修改weight时同样
template &class TypeOfVer, class TypeOfEdge&
class AdjMatrixGraph : public Graph&TypeOfEdge&{
//这里为了方便，所有成员函数写成内联函数的形式
AdjMatrixGraph(int v, const TypeOfVer *d, TypeOfEdge noEdgeFlag, bool isWeightedFlag, bool isDirectedFlag) {
edges = 0;
noEdge = noEdgeF
isWeighted = isWeightedF
isDirected = isDirectedF
ver = new TypeOfVer[vers];
for (int i = 0; i & ++i) {
ver[i] = d[i];
edge = new TypeOfEdge *[vers];
for (int i = 0; i & ++i) {
edge[i] = new TypeOfEdge[vers];
for (int j = 0; j & ++j) {
edge[i][j] = noE
edge[i][i] = 0;
~AdjMatrixGraph() {
for (int i = 0; i & ++i) {
delete [] edge[i];
bool insert(int u, int v, TypeOfEdge w) {
if (u & 0 || u & vers - 1 || v & 0 || v & vers - 1)
if (exist(u, v))
edge[u][v] =
if (!isDirected)
edge[v][u] =
bool remove(int u, int v) {
if (u & 0 || u & vers - 1 || v & 0 || v & vers - 1)
if (!exist(u, v))
edge[u][v] = noE
if (!isDirected)
edge[v][u] = noE
bool modify(int u, int v, TypeOfEdge w) {
if (u & 0 || u & vers - 1 || v & 0 || v & vers - 1)
if (!exist(u, v))
edge[u][v] =
if (!isDirected)
edge[v][u] =
bool exist(int u, int v) const {
if (u & 0 || u & vers - 1 || v & 0 || v & vers - 1)
if (edge[u][v] == noEdge)
//所有顶点对的最短路径( 时间复杂度O(|V^3|) )
void floyd() const {
TypeOfEdge **d = new TypeOfEdge *[vers];
int **prev = new int *[vers];
for (int i = 0; i & ++i) {
d[i] = new TypeOfEdge[vers];
prev[i] = new int[vers];
for (int j = 0; j & ++j) {
d[i][j] = edge[i][j];
prev[i][j] = (edge[i][j] != noEdge) ? i : -1;
for (int k = 0; k & ++k) {
for (int i = 0; i & ++i) {
for (int j = 0; j & ++j) {
if (d[i][k] + d[k][j] & d[i][j]) {
d[i][j] = d[i][k] + d[k][j];
prev[i][j] = prev[k][j];
for (int i = 0; i & ++i) {
for (int j = 0; j & ++j) {
cout && &the path from & && ver[i] && & to & && ver[j] && &: &;
printPath(i, j, prev);
cout && &\twith length: & && d[i][j]&&
//cout && &最短路径& &&
//for (int i = 0; i & ++i) {
for (int j = 0; j & ++j) {
cout && prev[i][j] && &\t&;
//cout && &长度& &&
//for (int i = 0; i & ++i) {
for (int j = 0; j & ++j) {
cout && d[i][j] && &\t&;
TypeOfEdge **
TypeOfVer *
TypeOfEdge noE
void printPath(int start, int end, int **prev) const {
if (start == end) {
cout && ver[start];
printPath(start, prev[start][end], prev);
cout && &-& && ver[end];
//不相交集(并查集)
class DisjointSet {
DisjointSet(int n) {
parent = new int[n];
for (int i = 0; i & ++i) {
parent[i] = -1;
~DisjointSet(){
int find(int x) {
if (parent[x] & 0)
return parent[x] = find(parent[x]);
void unionTwoSet(int root1, int root2){
if (root1 == root2)
if (parent[root1] & parent[root2]) {
//root1规模小
parent[root2] += parent[root1];
parent[root1] = root2;
parent[root1] += parent[root2];
parent[root2] = root1;
#include &graph.h&
#include &iostream&
int main() {
//有向图的遍历
cout && &有向图的遍历:& &&
AdjListGraph&char, int& g(7, &0123456&, true, true);
//adjListGraph&char, int& g(7, &1234567&, true, true);
//adjListGraph&char, int& g(7, &abcdefg&, true, true);
g.insert(4, 5, 1);
g.insert(4, 6, 1);
g.insert(6, 5, 1);
g.insert(5, 1, 1);
g.insert(6, 3, 1);
g.insert(1, 3, 1);
g.insert(0, 1, 1);
g.insert(3, 2, 1);
g.insert(1, 2, 1);
g.insert(3, 0, 1);
g.insert(2, 0, 1);
//无向图的欧拉回路
cout && &无向图的欧拉回路:& &&
AdjListGraph&char, int& eulerGraph(6, &012345&, true, false);
eulerGraph.insert(0, 1, 1);
eulerGraph.insert(0, 2, 1);
eulerGraph.insert(1, 2, 1);
eulerGraph.insert(2, 3, 1);
eulerGraph.insert(1, 4, 1);
eulerGraph.insert(1, 3, 1);
eulerGraph.insert(2, 4, 1);
eulerGraph.insert(3, 4, 1);
eulerGraph.insert(3, 5, 1);
eulerGraph.insert(4, 5, 1);
eulerGraph.eulerCircuit('5');
//有向无环图的拓扑排序
cout && &有向无环图的拓扑排序:& &&
AdjListGraph&char, int& topologyGraph(7, &0123456&, true, true);
topologyGraph.insert(0, 1, 1);
topologyGraph.insert(0, 2, 1);
topologyGraph.insert(1, 3, 1);
topologyGraph.insert(1, 4, 1);
topologyGraph.insert(1, 5, 1);
topologyGraph.insert(2, 4, 1);
topologyGraph.insert(2, 6, 1);
topologyGraph.insert(4, 5, 1);
topologyGraph.insert(4, 6, 1);
topologyGraph.insert(5, 3, 1);
topologyGraph.topologySort();
//无向图的最小生成树
cout && &最小生成树:& &&
//AdjListGraph&char, int& minimumSpanningTree(6, &012345&, true, false);
AdjListGraph&char, int& minimumSpanningTree(6, &123456&, true, false);
minimumSpanningTree.insert(0, 3, 5);
minimumSpanningTree.insert(3, 5, 2);
minimumSpanningTree.insert(4, 5, 6);
minimumSpanningTree.insert(1, 4, 3);
minimumSpanningTree.insert(0, 1, 6);
minimumSpanningTree.insert(0, 2, 1);
minimumSpanningTree.insert(1, 2, 5);
minimumSpanningTree.insert(2, 3, 5);
minimumSpanningTree.insert(2, 4, 6);
minimumSpanningTree.insert(2, 5, 4);
minimumSpanningTree.kruskal();
minimumSpanningTree.prim(INT_MAX);
//有向图的单源最短路径
cout && &单源最短路径:& &&
AdjListGraph&char, int& singleSourceShortestPath(7, &0123456&, true, true);
singleSourceShortestPath.insert(0, 1, 2);
singleSourceShortestPath.insert(1, 4, 10);
singleSourceShortestPath.insert(4, 6, 6);
singleSourceShortestPath.insert(6, 5, 1);
singleSourceShortestPath.insert(2, 0, 4);
singleSourceShortestPath.insert(2, 5, 5);
singleSourceShortestPath.insert(0, 3, 1);
singleSourceShortestPath.insert(1, 3, 3);
singleSourceShortestPath.insert(3, 2, 2);
singleSourceShortestPath.insert(3, 4, 2);
singleSourceShortestPath.insert(3, 5, 8);
singleSourceShortestPath.insert(3, 6, 4);
cout && &非加权图& &&
singleSourceShortestPath.unweightedShortDistance('2', INT_MAX);
cout && &加权图& &&
//singleSourceShortestPath.dijkstra('1', INT_MAX);
singleSourceShortestPath.dijkstra('2', INT_MAX);
//有向带负权值图的单源最短路径
AdjListGraph&char, int& singleSourceShortestPathWeightedNegative(7, &0123456&, true, true);
singleSourceShortestPathWeightedNegative.insert(0, 1, 2);
singleSourceShortestPathWeightedNegative.insert(1, 4, 10);
singleSourceShortestPathWeightedNegative.insert(4, 6, 6);
singleSourceShortestPathWeightedNegative.insert(6, 5, 1);
singleSourceShortestPathWeightedNegative.insert(2, 0, 4);
singleSourceShortestPathWeightedNegative.insert(2, 5, 3);
singleSourceShortestPathWeightedNegative.insert(0, 3, 1);
singleSourceShortestPathWeightedNegative.insert(1, 3, 3);
singleSourceShortestPathWeightedNegative.insert(3, 2, 2);
singleSourceShortestPathWeightedNegative.insert(3, 4, 2);
singleSourceShortestPathWeightedNegative.insert(3, 5, -8);
singleSourceShortestPathWeightedNegative.insert(3, 6, 4);
cout && &带负权值图& &&
singleSourceShortestPathWeightedNegative.weightedNegative('2', INT_MAX);
//有向图所有顶点对的最短路径
cout && &所有顶点对的最短路径:& &&
AdjMatrixGraph&char, int& allVertexPairShortestPath(3, &012&, INT_MAX, true, true);
allVertexPairShortestPath.insert(0, 1, 8);
allVertexPairShortestPath.insert(1, 0, 3);
allVertexPairShortestPath.insert(0, 2, 5);
allVertexPairShortestPath.insert(2, 0, 6);
allVertexPairShortestPath.insert(2, 1, 2);
allVertexPairShortestPath.floyd();
int ttt = 0;
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：12168次
排名：千里之外
原创：48篇
转载：12篇
(4)(5)(1)(8)(27)(8)(5)(3)　　这篇文章是对《算法导论》上Prim算法求无向连通图最小生成树的一个总结，其中有关于我的一点点小看法。　　最小生成树的具体问题可以用下面的语言阐述：　　　　输入：一个无向带权图G=(V,E)，对于每一条边(u, v)属于E，都有一个权值w。　　　　输出：这个图的最小生成树，即一棵连接所有顶点的树，且这棵树中的边的权值的和最小。　　举例如下，求下图的最小生成树：　　这个问题是求解一个最优解的过程。那么怎样才算最优呢？　　首先我们考虑最优子结构：如果一个问题的最优解中包含了子问题的最优解，则该问题具有最优子结构。　　最小生成树是满足最优子结构的，下面会给出证明：　　最优子结构描述：假设我们已经得到了一个图的最小生成树(MST) T，(u, v)是这棵树中的任意一条边。如图所示：　　　　现在我们把这条边移除，就得到了两科子树T1和T2，如图：&　　　　T1是图G1=(V1, E1)的最小生成树，G1是由T1的顶点导出的图G的子图，E1={(x, y)&E, x, y &V1}　　　　同理可得T2是图G2=(V2, E2)的最小生成树，G2是由T2的顶点导出的图G的子图，E2={(x, y)&E, x, y &V2}　　现在我们来证明上述结论：使用剪贴法。w(T)表示T树的权值和。　　　　首先权值关系满足：w(T) = w(u, v)+w(T1)+w(T2)　　　　假设存在一棵树T1'比T1更适合图G1，那么就存在T'={(u,v)}UT1'UT2'，那么T'就会比T更适合图G，这与T是最优解相矛盾。得证。　　因此最小生成树具有最优子结构，那么它是否还具有重叠子问题性质呢？我们可以发现，不管删除那条边，上述的最优子结构性质都满足，都可以同样求解，因此是满足重叠子问题性质的。　　考虑到这，我们可能会想：那就说明最小生成树可以用动态规划来做咯？对，可以，但是它的代价是很高的。　　我们还能发现，它还有个更强大的性质：贪心选择性质。因而可用贪心算法完成。　　贪心算法特点：一个局部最优解也是全局最优解。　　最小生成树的贪心选择性质：令T为图G的最小生成树，另A&V，假设边(u, v)&E是连接着A到A的补集（也就是V-A)的最小权值边，那么(u, v)属于最小生成树。　　证明：假设(u, v)&T， 使用剪贴法。现在对下图进行分析，图中A的点用空心点表示，V-A的点用实心点表示：　　在T树中，考虑从u到v的一条简单路径（注意现在(u, v)不在T中），根据树的性质，它是唯一的。　 &&现在把(u, v)和这条路上中的第一条连接A和V-A的边交换，即画红杠的那条边，边(u, v)是连接A和V-A的权值最小边，那我们就得到了一棵更小的树，这就与T是最小　　生成树矛盾。得证。　　现在呢，我们来看看Prim的思想：Prim算法的特点是集合E中的边总是形成单棵树。树从任意根顶点s开始，并逐渐形成，直至该树覆盖了V中所有顶点。每次添加到树中的边都是使树的权值尽可能小的边。因而上述策略是&贪心&的。　　算法的输入是无向连通图G=(V, E)和待生成的最小生成树的根r。在算法的执行过程中，不在树中的所有顶点都放在一个基于key域的最小优先级队列Q中。对每个顶点v来说，key[v]是所有将v与树中某一顶点相连的边中的最小权值；按规定如果不存在这样的边，则key[v]=&。　　实现Prim算法的伪代码如下所示：　　MST-PRIM(G, w, r)　　　　for each u&V　　　　　　do key[u] &&&　　　　　　　 &parent[u]& NIL　　　　key[r] & 0　　　　Q & V　　　　while Q &&　　　　　　do u & EXTRACT-MIN(Q)　　　　　　　　for each v&Adj[u]　　　　　　　　　　do if v&Q and w(u, v) & key[v]　　　　　　　　　　　　then parent[v] & u　　　　　　　　　　　　　　 &key[v] & w(u, v)　　　　其工作流程为：　　　　　　（1）首先进行初始化操作，将所有顶点入优先队列，队列的优先级为权值越小优先级越高　　　　　　（2）取队列顶端的点u，找到所有与它相邻且不在树中的顶点v，如果w(u, v) & key[v]，说明这条边比之前的更优，加入到树中，即更改父节点和key值。这中间还　　　　隐含着更新Q的操作（降key值）　　　　　　（3）重复2操作，直至队列空为止。　　　　　　（4）最后我们就得到了两个数组，key[v]表示树中连接v顶点的最小权值边的权值，parent[v]表示v的父结点。　　　　现在呢，我们发现一个问题，这里要用到优先队列来实现这个算法，而且每次搜索邻接表都要进行队列更新的操作。　　　　　　不管用什么方法，总共用时为O(V*T(EXTRACTION)+E*T(DECREASE))　　　　　　（1）如果用数组来实现，总时间复杂度为O(V2)　　　　　　（2）如果用二叉堆来实现，总时间复杂度为O(ElogV)　　　　　　（3）如果使用斐波那契堆，总时间复杂度为O(E+VlogV)　　　　上面的三种方法，越往下时间复杂度越好，但是实现难度越高，而且每次对最小优先队列的更新是非常麻烦的，那么，有没有一种方法，可以不更新优先队列也达到同样的　　效果呢？　　　　答案是：有。　　　　其实只需要简单的操作就可以达到。首次只将根结点入队列。第一次循环，取出队列顶结点，将其退队列，之后找到队列顶的结点的所有相邻顶点，若有更新，则更新它们的key值后，再将它们压入队列。重复操作直至队列空为止。因为对树的更新是局部的，所以只需将相邻顶点key值更新即可。push操作的复杂度为O(logV)，而且省去了之前将所有顶点入队列的时间，因而总复杂度为O(ElogV)。　　具体实现代码，优先队列可以用STL实现：　　
1 #include &iostream&
2 #include &cstdio&
3 #include &vector&
4 #include &queue&
5 using namespace
7 #define maxn 100
//最大顶点个数
//顶点数，边数
10 struct arcnode
//边结点 11 { 12
//与表头结点相邻的顶点编号 13
//连接两顶点的边的权值 14
arcnode * //指向下一相邻接点 15
arcnode() {} 16
arcnode(int v,int w):vertex(v),weight(w),next(NULL) {} 17 }; 18
19 struct vernode
//顶点结点，为每一条邻接表的表头结点 20 { 21
//当前定点编号 22
//与该顶点相连的第一个顶点组成的边 23 }Ver[maxn]; 24
25 void Init()
//建立图的邻接表需要先初始化，建立顶点结点 26 { 27
for(int i = 1; i &= i++) 28
Ver[i].vex = 30
Ver[i].firarc = NULL; 31
34 void Insert(int a, int b, int w)
//插入以a为起点，b为终点，权为w的边 35 { 36
arcnode * q = new arcnode(b, w); 37
if(Ver[a].firarc == NULL) 38
Ver[a].firarc = 39
arcnode * p = Ver[a]. 42
q-&next = 43
Ver[a].firarc = 44
47 struct node
//保存key值的结点 48 { 49
friend bool operator&(node a, node b)
//自定义优先级，key小的优先 52
return a.key & b. 54
} 55 }; 56
57 #define INF 9999
//权值上限 58 int parent[maxn];
//每个结点的父节点 59 bool visited[maxn]; //是否已经加入树种 60 node vx[maxn];
//保存每个结点与其父节点连接边的权值 61 priority_queue&node& //优先队列stl实现 62 void Prim(int s)
//s表示根结点 63 { 64
for(int i = 1; i &= i++) //初始化 65
vx[i].v = 67
vx[i].key = INF; 68
parent[i] = -1; 69
visited[i] = false; 70
vx[s].key = 0; 72
q.push(vx[s]); 73
while(!q.empty()) 74
node nd = q.top();
//取队首，记得赶紧pop掉 76
visited[nd.v] = true; 77
q.pop(); 78
arcnode * p = Ver[nd.v]. 79
while(p != NULL)
//找到所有相邻结点，若未访问，则入队列 80
if(!visited[p-&vertex] && p-&weight & vx[p-&vertex].key) 82
parent[p-&vertex] = nd.v; 84
vx[p-&vertex].key = p-& 85
vx[p-&vertex].v = p-& 86
q.push(vx[p-&vertex]); 87
p = p-& 89
94 int main() 95 { 96
int a, b ,w; 97
cout && "输入n和m: "; 98
cin && n && 99
Init();100
cout && "输入所有的边:" &&101
while(m--)102
cin && a && b &&104
Insert(a, b, w);105
Insert(b, a, w);106
Prim(1);108
cout && "输出所有结点的父结点:" &&109
for(int i = 1; i &= i++)110
cout && parent[i] && " ";111
cout &&112
cout && "最小生成树权值为：";113
int cnt = 0;114
for(int i = 1; i &= i++)115
cnt += vx[i].116
cout && cnt &&117
return 0;118 }运行结果如下（基于第一个例子）：&望支持，谢谢。&
最新教程周点击榜
微信扫一扫