图数据结构，参考并修改数据结构C++应用标准模板库（第二版）。
#ifndef GRAPH_CLASS
#define GRAPH_CLASS#include <iostream>
#include <fstream>
#include <set> // set class
#include <map> // ist classmap class
#include <vector> // vector class
#include <list> // list class
#include <stack> // stack class
#include <queue> // queue class
#include <functional> // less<T>
#include "d_except.h" // exception classes
#include "disjSets.h"#define INFINITY 0x7fffffffusing namespace std;/*
* 在建立邻接表或逆邻接表时，若输入的定点信息为顶点的编号，则建立邻接表的复杂度为O（n + e）,
* 否则， 需要通过查找才能找到定点在顶点表中的位置，时间复杂度为O(n*e).
* 在邻接表上容易找到顶点的下一个邻接顶点，也可以找到下一个邻接顶点。
* 但是要判定任意两个邻接顶点vi和vj是否链接，需要线性搜索vi或vj。* 对于任一顶点，重要的关键是在于能迅速找到与该顶点邻接的那些顶点所在的表（或者vector或者list），
* 所以两个基本选择是，或者使用一个map in which the keys are vectives and the values are adjacency lists,
* or to maintain each adjacency list as a data member of a vertex class.* 无向图的极大连通子图称为连通分量connected component；连通分量包含4个要点：1，连通分量应该是原图的子图2连通分量本身应该是连通的3极大顶点数：连通子图含有极大
* 顶点数，即再加入其他顶点将会导致子图不连通4极大边数：具有极大顶点数的连通子图包含依附于这些顶点的所有边。* 对于有向图来说，若图中任意一对顶点均有双向的路径，则称该有向图是强连通图。* 有向图的极大强连通子图称为强连通分量。* 如果无向连通图的一个网图，那么听他的所有生成树中必有一棵边的权值总和最小的生成树，我们成这棵生成树为最小生成树 Minimum Spanning Tree，MST。当然， 对于任意一个带权的连通网图来说
* 最小生成树也未必是唯一的。1
*/class neighbor
{
public:// index of destination vertex in the vectorint dest;// weight of this edgeint weight;neighbor(int d = 0, int c = 0) : dest(d), weight(c){ }friend bool operator<(const neighbor &lhs, const neighbor &rhs){return lhs.dest < rhs.dest;}friend bool operator==(const neighbor &lhs, const neighbor &rhs){return lhs.dest == rhs.dest;}
};// T is the type of vertex
template <class T>
class VertexInfo
{
public:VertexInfo() : inDegree(0), occupied(true) { }VertexInfo(typename map<T, int>::iterator iter): vtxMapLoc(iter), inDegree(0), occupied(true) { }enum vertexColor { WHITE, GRAY, BLACK };vertexColor color;// iterator pointing at a pair<T, int> object in the vertex map// 根据顶点在vector中的下标找到这个顶点后，用他的vtxMapLoc成员找到vtxMap中的对应的项typename map<T, int>::iterator vtxMapLoc;// set of adjacent vertex for the current vertex 当前顶点的邻接表set<neighbor> edges;int inDegree;bool occupied; // occupy flagint dataValue; // lowCost int parent; // keep track of path
};// priority queue data used in DijkstraPath() and Minimum Spanning Tree
class minInfo
{
public:int endV; // 终点顶点的下标int pathWeight; // 顶点的最小权(在Dijstra方法中代表该顶点到s_vertex的最短路径长度)friend bool operator<(const minInfo &lhs, const minInfo &rhs){return lhs.pathWeight < rhs.pathWeight;}
};// 边的集合
class Edge
{
public:Edge() = default;Edge(int s, int e, int w) : start(s), end(e), weight(w) { }friend bool operator<(const Edge &lhs, const Edge &rhs){return lhs.weight < rhs.weight;}// 通过重载==运算符可以判断两个边是否是重复的friend bool operator==(const Edge &lhs, const Edge &rhs){return (lhs.start == rhs.start &&lhs.end == rhs.end &&lhs.weight == rhs.weight);}
private:int start; // 边的起始顶点在vector vInfo中的indexint end; // 边的起终止点在vector vInfo中的indexint weight; // 边的权
};template<class T>
class Graph
{
public:Graph();// copy ctorGraph(const Graph<T> &g);Graph<T>& operator=(const Graph<T> &rhs);// perform the breadth-first traversal from sVertex and// return the set of visited verticesfriend set<T> bfs(Graph<T>& g, const T &sVertex);friend set<T> dfs(Graph<T> &g, const T &sVertex);friend int UnweightedshortestPath(Graph<T> &g, const T &sVertex, const T &eVertex, list<T> &path);friend int DijkstraPath(Graph<T> &g, const T &sVertex, const T &eVertex, list<T> &path);friend int DijkstraPQPath(Graph<T> &g, const T &sVertex, const T &eVertex, list<T> &path);friend int PrimMinSpanTree(Graph<T> &g, Graph<T> &MST);friend void KruskalMinSpanTree(Graph<T> &g, Graph<T> &MST);friend void Graph<T>::topologicalSort(Graph<T> g, list<T> &tList);vector<Edge> &Graph<T>::readGraphEdges();int numberOfVertices() const;int numberOfEdges() const;bool empty() const;// return the weight of the edge(v1, v2).// if the edge does not exits,return -1.// v1 and v2 are vertices in the Graph.if not the function// throws the graphError exceptionint &getWeight(const T &v1, const T &v2) const;void setWeight(const T &v1, const T &v2, int w);int inDegree(const T &v) const;int outDegree(const T &v) const;set<T> getNeighbors(const T &v) const;void insertEdge(const T &v1, const T &v2, int w);void insertVertex(const T &v);void eraseEdge(const T &v1, const T &v2);void eraseVertex(const T &v);// remove all the vertices and edges from the Graphvoid clear();//iterator begin();//iterator end();//const_iterator begin() const;//const_iterator end() const; // returns correspoding map iterator
private:typedef map<T, int> vertexMap;// store vertex in a map with its name as key and the index // of the corresponding vector as the valuevertexMap vtxMap;vector<VertexInfo<T> > vInfo;// current size of the Graphint numVertices;int numEdges;// availability stack for storing unused indices in vector vInfostack<int> availStack;// get the index of the vertex v use map vtxMapint getvInfoIndex(const T &v) const;int &getWeightByIndex(int pos1, int pos2);void insertEdgeByIndex(int pos1, int pos2, int weight);bool leftUnvisitVertex() const;int findMinDistanceVertex() const;
};// use vtxMap to obtain the index of v in vector vInfo
template<class T>
int Graph<T> ::getvInfoIndex(const T &v) const
{// 下标运算符会产生副作用map<T, int>::iterator iter = vtxMap.find(v);if (iter == vtxMap.end())return -1;elsereturn (*iter).second;
}template<class T>
Graph<T>::Graph() : numVertices(0), numEdges(0)
{}template<class T>
Graph<T>::Graph(const Graph<T> &g)
{*this = g;
}// overloaded assignment operator
template <typename T>
Graph<T>& Graph<T>::operator= (const Graph<T>& rhs)
{vertexMap::iterator mi;// can't copy a Graph to itselfif (this == &rhs)return *this;// copy rhs to current objectvtxMap = rhs.vtxMap;vInfo = rhs.vInfo;numVertices = rhs.numVertices;numEdges = rhs.numEdges;availStack = rhs.availStack;// update each vtxMapLoc value of objects in vInfo so it points// to a key-value pair in the copy of rhs.vtxMap and not rhs.vtxMapfor (mi = vtxMap.begin(); mi != vtxMap.end(); mi++)vInfo[(*mi).second].vtxMapLoc = mi;return *this;
}// 把无向图的所有边读取到vector中，然后在后续的方法中把vector读取到priority_queue中，buildHeap。
template<class T>
vector<Edge> &Graph<T>::readGraphEdges()
{int i;vector<Edge> ret;for (i = 0; i < vInfo.size(); ++i) {if (vInfo[i].occupied) {for (auto item : vInfo[i].edges) {// 如果在vector中还没有发现重复边，就把边push进vectorif(!find(ret.begin(), ret.end(), Edge(item.dest, i, item.weight)))ret.push_back(Edge(i, item.dest, item.weight));}}}return ret;
}template <typename T>
int Graph<T>::numberOfVertices() const
{return numVertices;
}template <typename T>
int Graph<T>::numberOfEdges() const
{return numEdges;
}template <typename T>
bool Graph<T>::empty() const
{return numVertices == 0;
}
template<class T>
int &Graph<T>::getWeightByIndex(int pos1, int pos2)
{if (pos1 != -1 && pos2 != -1) {neighbor tmp(pos2);auto sIter = vInfo[pos1].edges.find(tmp);if (sIter != vInfo[pos1].edges.end())return (*sIter).weight;elsereturn = 1; // "v1 don't have adjacent vertex v2 "}throw graphError("vertex not in the Graph"); // don't have vertex v1
}
// return the weight of the edge(v1, v2)
// if the edge doesnot exist, return -1
template<class T>
int &Graph<T>::getWeight(const T &v1, const T &v2) const
{int pos1 = getvInfoIndex(v1);int pos2 = getvInfoIndex(v2);getWeightByIndex(pos1, pos2);
}template<class T>
void Graph<T>::setWeight(const T &v1, const T &v2, int w)
{getWeight(v1, v2) = w;
}template<class T>
int Graph<T>::inDegree(const T &v) const
{int pos = getvInfoIndex(v);if (pos != -1)return vInfo.inDegree;elsethrow graphError("Graph inDegree(): vertex not in the Graph");
}// outDegree is easy to obtain, just scan the set of the corresponding vertex
// and inDegree is not easy to obtain, so it is stored through private data member
template<class T>
int Graph<T>::outDegree(const T &v) const
{int pos = getvInfoIndex(v);if (pos != -1)return vInfo[pos].edges.size();elsethrow graphError("Graph inDegree(): vertex not in the Graph");
}// v的邻接表的每一个顶点找到下标对应的vector中的vtxMapLoc迭代器，然后在map中取pair first成员
template<class T>
set<T> Graph<T>::getNeighbors(const T &v) const
{set<T> adjVertices;int pos = getvInfoIndex(v);if (pos == -1)throw graphError("Graph getNeighbors(): vertex not in the Graph");for (const auto i : vInfo[pos].edges)adjVertices.insert((*vInfo[i.dest].vtxMapLoc).first);return adjVertices;
}template<class T>
void Graph<T>::insertEdgeByIndex(int pos1, int pos2, int weight)
{// set 的插入操作可能导致失败，因为set不允许重复关键字// pair<set<neighbor>::iterator, bool> 是iter的类型auto iter = vInfo[pos1].edges.insert(neighbor(pos2, weight));if (iter.second) {vInfo[pos2].inDegree++;numEdges++;}
}template<class T>
void Graph<T>::insertEdge(const T &v1, const T &v2, int w)
{// obtain the vInfo indicesint pos1 = getvInfoIndex(v1);int pos2 = getvInfoIndex(v2);// check for an errorif (pos1 == -1 || pos2 == -1)// if v1 or v2 not in list of vertices, throw an exceptionthrow graphError("Graph insertEdge(): vertex not in the Graph");else if (pos1 == pos2)// we do not allow self-loopsthrow graphError("Graph insertEdge(): self-loops are not allowed");insertEdgeByIndex(pos1, pos2, w);
}template<class T>
void Graph<T>::insertVertex(const T &v)
{auto result = vtxMap.insert(make_pair(v, 0));if (result.second) {if (!availStack.empty) {index = availStack.top();availStack.pop();// result 是一个pair，first成员是map的迭代器vInfo[index] = vertexInfo<T>(result.first);}else {vInfo.push_back(vertexInfo<T>(result.first));index = numVertices;}result.first->second = index;numVertices++;}elsethrow graphError("Graph insertVertex(): vertex already in the Graph");
}// erase edge (v1, v2) from the Graph
template<class T>
void Graph<T>::eraseEdge(const T &v1, const T &v2)
{// obtain the indices of v1 and v2 in vInfoint pos1 = getvInfoIndex(v1);int pos2 = getvInfoIndex(v2);// check for an errorif (pos1 == -1 || pos2 == -1)// if v1 or v2 not in list of vertices, throw an exceptionthrow graphError("Graph eraseEdge(): vertex not in the Graph");auto iter = vInfo[pos1].edges.find(neighbor(pos2));if (iter != vInfo[pos1].edges.end()) {erase(neighbor(pos2));vInfo[pos2].inDegree--;numEdges--;}elsethrow graphError("Graph eraseEdge(): vertex not in the Graph");
}template<class T>
void Graph<T>::eraseVertex(const T &v)
{vertexMap::iterator mIter;mIter = vtxMap.find(v);if (mIter == vtxMap.end())// if v not in list of vertices, throw an exceptionthrow graphError("Graph eraseVertex(): vertex not in the Graph");int pos = mIter->second;vtxMap.erase(mIter);/* 同样的方法* int num = vtxMap.erase(v)if(num == 0)throw graphError("Graph eraseVertex(): vertex not in the Graph");*/numVertices--;vInfo[pos].occupied = false;vInfo[pos].inDegree = 0;// push the index pos in the available stack for use if we insert a new vertexavailStack.push(pos);// cycle through vector vInfo to erase all the edge going to vertex vfor (auto i : vInfo)if (i.occupied)// set的erase方法返回删除的set中关键字key的个数，如果set中没有key，则返回0// 因为neighbor类定义了==运算符（定义为只要dest成员相同两个neighbor类就相同）// set的erase方法可以用一个迭代器或者一对迭代器或者一个关键字作为参数if (i.edges.erase(neighbor(pos)) == 1)numEdges--;// decrement numEdges by the number of edges for vertex vnumEdges -= vInfo[pos].edges.size();// clear the adjacent list (set) // and decrement all the adjacent vertex of v 's private member inDegreefor (auto i : vInfo[pos].edges)vInfo[i.dest].inDegree--;vInfo[pos].edges.clear();}template<class T>
bool Graph<T>::leftUnvisitVertex() const
{for (auto i : g.vInfo)if (i.occupied && i.color == vertexInfo<T>::WHITE)return true;return false;
}// find the shortest path veretx that is unvisited
template<class T>
int Graph<T>::findMinDistanceVertex() const
{int i;int minIndex;int minVal;bool minValFlag = false;for (i = 0; i < numVertices; ++i) {if (g.vInfo[i].color != vertexInfo<T>::WHITE)continue;if (!minValFlag) {minValFalg = true;minVal = g.vInfo[i].dataVal;continue;}if (g.vInfo[i].dataVal < minVal) {minVal = g.vInfo[i].dataVal;minIndex = i;}}return minIndex;
}template <typename T>
void Graph<T>::clear()
{vInfo.clear();vtxMap.clear();while (!availStack.empty)availStack.pop();numVertices = 0;numEdges = 0;
}/*
另一种Graph的clear的代码
// erase the Graph
template <typename T>
void Graph<T>::clear()
{
// clear the vertex list, vertex map and the
// availability stack
vInfo.erase(vInfo.begin(), vInfo.end());
vtxMap.erase(vtxMap.begin(), vtxMap.end());
while(!availStack.empty())
availStack.pop();// set the number of vertices and edges to 0
numVertices = 0;
numEdges = 0;
}
*/// each Graph iterator function returns
// the corresponding map iterator
/*
template <typename T>
Graph<T>::iterator Graph<T>::begin()
{
return Graph<T>::iterator(vtxMap.begin());
}template <typename T>
Graph<T>::iterator Graph<T>::end()
{
return Graph<T>::iterator(vtxMap.end());
}template <typename T>
Graph<T>::const_iterator Graph<T>::begin() const
{
return Graph<T>::iterator(vtxMap.begin());
}template <typename T>
Graph<T>::const_iterator Graph<T>::end() const
{
return Graph<T>::iterator(vtxMap.end());
}
*//*
* 遍历算法，对于BT的搜索算法，这些算法以各种方式访问节点并下降到其左右子树，访问
* 方式有前，中，后序搜索。从根开始，算法访问树的每个结点一次：从根到每个结点的路径是唯一的。
* 遍历图更复杂，图没有树根那样的顶点，该顶点可以定义到其他所有顶点的路径。
* 从任何一个初始顶点，都有可能不能访问图中的所有顶点。搜索算法只能确定图中可以从初始顶点到达的顶点。
* 而且图中任何两个结点之间都可能有边链接。* 在BT中我们最多有两个相邻的选择：从当前顶点开始，我们可以先到左边的子树，或者先到右边的子树
* 我们还可以选择在访问其中一个（或两个）子树之前或之后访问当前结点。In a binary tree, we only have up to two neighboring choices:
From the current vertex, we can go to the left subtree first or go to the right subtree first.
We also have option to visit the current vertex before or after visiting one of the (or both) subtree(s).This gives rise to the classics: pre-order (visit current vertex, visit its left subtree, visit its right subtree),
in-order (left, current, right),
and post-order (left, right, current) traversals.************************************************************************************************************************
The time complexity of DFS is O(V+E) because:
Each vertex is only visited once due to the fact that DFS will only recursively explore a vertex u if status[u] = unvisited — O(V).
Every time a vertex is visited, all its k neighbors are explored and therefore after all vertices are visited,
we have examined all E edges — (O(E) as the total number of neighbors of each vertex equals to E).*/// 适合于连通图，从搜索顶点sVertex可以到达任何一个顶点的图，否则如果在有向图中从一个顶点不能到达另一个顶点，则
// 另一个顶点不会被bfs遍历出来。 时间复杂度为O(V + E)。
#if defined CONNECTED_GRAPH
template<class T>
friend set<T> bfs(Graph<T>& g, const T& sVertex)
{queue<int> visitQueue;set<T> visitSet;int currVertex, neighborVertex;currVertex = g.getvInfoIndex(sVertex);// check for a nonexistent starting vertexif (currVertex == -1)throw graphError("Graph bfs(): vertex not in the Graph");for (auto i : g.vInfo)if (i.occupied)i.color = vertexInfo<T>::WHITE;visitQueue.push(currVertex);while (!visitQueue.empty()) {currVertex = visitQueue.front();visitQueue.pop();g.vInfo[currVertex].color = vertexInfo<T>::BLACK;visitSet.insert((*(g.vInfo[currVertex].vtxMapLoc)).first);for (auto i : g.vInfo[currVertex].edges) {neighborVertex = i.dest;if (g.vInfo[neighborVertex].color == vertexInfo<T>::WHITE) {g.vInfo[neighborVertex].color == vertexInfo<T>::GRAY;visitQueue.push(neighborVertex);}}}
}
#endiftemplate<class T>
set<T> bfs(Graph<T>& g, const T& sVertex)
{queue<int> visitQueue;set<T> visitSet;int currVertex, neighborVertex;currVertex = g.getvInfoIndex(sVertex);// check for a nonexistent starting vertexif (currVertex == -1)throw graphError("Graph bfs(): vertex not in the Graph");for (auto i : g.vInfo)if (i.occupied)i.color = vertexInfo<T>::WHITE;int leftNum = g.numVertices;while (visitSet.size() < leftNum) {visitQueue.push(currVertex);while (!visitQueue.empty()) { // queue每空一次，证明一个极大连通分量被遍历完毕，需要遍历下一个极大连通分量。currVertex = visitQueue.front();visitQueue.pop();g.vInfo[currVertex].color = vertexInfo<T>::BLACK;visitSet.insert((*(g.vInfo[currVertex].vtxMapLoc)).first);for (auto i : g.vInfo[currVertex].edges) {neighborVertex = i.dest;if (g.vInfo[neighborVertex].color == vertexInfo<T>::WHITE) {g.vInfo[neighborVertex].color == vertexInfo<T>::GRAY;visitQueue.push(neighborVertex);}}}for (auto i : vInfo) // 找到图中新的未访问的顶点，对于非连通图来说的。if (i.color == vertex<T>::WHITE) {currVertex = i;break;}}
}// 类似树的前序遍历
template<class T>
set<T> dfs(Graph<T> &g, const T &sVertex)
{stack<int> visitStack;set<T> visitSet;int currVertex;currVertex = g.getvInfoIndex(sVertex);if (currVertex == -1)throw graphError(Graph dfs() : vertex not int the graph);for (auto i : g.vInfo)if (i.occupied)i.color = vertexInfo<T>::WHITE;vector<vertexInfo> &vertex = g.vInfo;int leftNum = g.numVertices;bool find;while (visitSet.size() < leftNum) {if (vertex[currVertex].color == vertexInfo<T>::WHITE) {visitSet.insert(*(vertex[currVertex].vtxMapLoc).first);vertex[currVertex].color = vertexInfo<T>::BLACK;}find = false;// 如果当前顶点有未访问的邻接顶点，则把当前顶点push进去，然后再让curr指向邻接顶点for (auto i : vertex[currVertex].edges)if (vertex[i.dest].color == vertexInfo<T>::WHITE) {visitStack.push(currVertex);currVertex = i.dest;find = true;break;}// 如果当前顶点没有找尚未访问的邻接顶点if (!find) {currVertex = visitStack.top();visitStack.pop();}}
}// unweighted graph shortest path from s to e, and keep path in list path
// Weiss版本未使用FIFO，直接设置循环currDist从0开始到
template<class T>
int UnweightedshortestPath(Graph<T> &g, const T &sVertex, const T &eVertex, list<T> &path)
{queue<int> visitQueue;bool foundShortestPath = false;int pos_sVertex, pos_eVertex, currPos, neighborPos;for (int i = 0; i < g.vInfo.size(); ++i)if (g.vInfo[i].occupied)g.vInfo[i].color = vertexInfo<T>::WHITE;pos_sVertex = getvInfoIndex(sVertex);pos_eVertex = getvInfoIndex(eVertex);if (pos_sVertex == -1 || pos_eVertex == -1)throw garphError("graph ShortestPath(): vertex not in the graph");g.vInfo[pos_sVertex].parent = pos_sVertex;g.info[pos_sVertex].dataValue = 0;visitQueue.push(pos_sVertex);while (!visitQueue.empty() || !foundShortestPath) {currPos = visitQueue.top();visitQueue.pop();g.vInfo[currPos].color = VertexInfo<T>::BLACK;if (currPos == pos_eVertex)foundShortestPath = true;else {set<neighbor> &edgeSet = g.vInfo[currPos].edges;for (auto i : edgeSet) {neighborPos = i.dest;if (g.vInfo[neighborPos].color == vertexInfo<T>::WHITE) {visitQueue.push(neighborPos);g.vInfo[neighborPos].color = vertexInfo<T>::GRAY;g.vInfo[neighborPos].dataVal = g.vInfo[currPos].dataVal + 1;g.vINfo[neighborPos].parent = currPos;}}}}// clear path and find the sequence of vertices// from sVertex to eVertexpath.erase(path.begin(), path.end());if (foundShortestPath) {currPos = pos_eVertex;while (currPos != pos_sVertex) {path.push_front(*(g.vInfo[currPos].vtxMapLoc).first);currPos = g.vInfo[currPos].parent;}path.push_front(sVertex);returnValue = g.vInfo[pos_eVertex].dataValue;}elsereturn -1;return returnValue;
}/*
* DijKstra 算法使用贪婪策略分阶段解决问题。每个阶段，选择距离起点路径最短的顶点x，贪婪表示该策略试图
* 最大化其短期收益，即使发现新的节点之后需要改变原有决策时也是如此。* 单源最短路径：从一个源点到其他顶点的最短路径问题称为单源最短路径问题。* 每一对顶点之间的最短距离，可以每次以一个顶点为源点，调用V次DijKstra算法。这样，就可求每一对顶点
之间的最短路径。或者用Floyd算法。* 分析复杂度，如果使用顺序扫描顶点以找出最小值dv这种明显的算法，那么每一步将花费O（V）时间找到最小值，
* 从而整个算法过程中查找最小值将会费O（V方）时间。每次更新dw是常数时间（只需要扫描当前顶点的邻接表），
* 而每条边最多有一次更新，总计O（E）。因此，总的运行时间为O（E+ V方）。
* 如果图是稠密的，即边数E=O（V方），则该算法不仅简单而且实质上最优。因为它的运行时间与边数成线性关系。* 如果图是稀疏的，边数是O（V），那么这种算法很慢。在这种情况下，距离dv需要存储在优先队列中/
*/// 稠密图使用的直接顺序扫描dist的算法
template<class T>
int DijkstraPath(Graph<T> &g, const T &sVertex, const T &eVertex, list<T> &path)
{int pos_sVertex, pos_eVertex, currVertex， currNum = 0;bool foundShortestPath;pos_sVertex = getvInfoIndex(sVertex);pos_eVertex = getvInfoIndex(eVertex);if (pos_sVertex == -1 || pos_eVertex == -1)throw graphError("weighted graph Shortest():vertex not in the graph");// initializefor (auto i : g.vInfo) {if (i.occupied) {i.dataVal = INFINITY;i.parent = -1;i.color = vertexInfo<T>::WHITE;}}g.vInfo[pos_sVertex].dataVal = 0;while (!foundShortestPath || currNum < g.numVertices) {currVertex = findMinDistanceVertex(); // O(N) , 可以优化为logN，binaryHeapg.vInfo[currVertex].color = vertexInfo<T>::BLACK;currNum++;for (auto i : g.vInfo[currVertex].edges) {g.vInfo[i.dest].dataVal = (g.vInfo[i.dest].dataVal < g.vInfo[currVertex].dataVal + i.weight) ?g.vInfo[i.dest].dataVal : g.vInfo[currVertex].dataVal + i.weight;g.vInfo[i.dest].parent = currVertex;}}// clear path and find the sequence of vertices// from sVertex to eVertexpath.erase(path.begin(), path.end());if (foundShortestPath) {currPos = pos_eVertex;while (currPos != pos_sVertex) {path.push_front(*(g.vInfo[currPos].vtxMapLoc).first);currPos = g.vInfo[currPos].parent;}path.push_front(sVertex);returnValue = g.vInfo[pos_eVertex].dataValue;}elsereturn -1;return returnValue;
}// 使用PriorityQueue组织的稀疏图的Dijkstra算法， 找最小distance的算法更新为logV， 更新邻接顶点的算法也更新为logV。
// 总的O（V*logV + E*logV）。
// Dijkstra算法按阶段进行，每个阶段，选择一个unknown的顶点，它在所有unknown的顶点中具有最小的dv，同时声明从source到v的顶点被访问过，
// 阶段的其余部分更新v的邻接点的dv，如果小就更新，不小就不更新
template<class T>
int DijkstraPQPath(Graph<T> &g, const T &sVertex, const T &eVertex, list<T> &path)
{priority_queue<minInfo, less<minInfo> > minPathPQ;minInfo vertexData;bool foundMinPath = false;int pos_sVertex, pos_eVertex, currPos, destPos;// computed minimum weightint newMinWeight;int returnValue;// initialize all vertices to unmarked (WHITE) and dataValue// variables to INFfor (int i = 0; i < g.vInfo.size(); i++)if (g.vInfo[i].occupied) {g.vInfo[i].color = vertexInfo<T>::WHITE;g.vInfo[i].dataValue = INFINITY;}pos_sVertex = g.getvInfoIndex(sVertex);pos_eVertex = g.getvInfoIndex(eVertex);if (pos_sVertex == -1 || pos_eVertex == -1)throw graphError("graph minimumPath(): vertex not in the graph");// formulate initial priority queue entryvertexData.endV = pos_sVertex;// path weight from sVertex to sVertex is 0vertexData.pathWeight = 0;// update dataValue in vInfo and set sVertex as parentg.vInfo[pos_sVertex].dataValue = 0;g.vInfo[pos_sVertex].parent = pos_sVertex;// insert starting vertex into the priority queueminPathPQ.push(vertexData);while (!minPathPQ.empty()) {vertexData = minPath.top(); // 找出所有未访问的顶点中的最小距离 logNminPath.pop();currPos = vertexData.endV; // 检查currPos是否被访问过if (currPos == pos_eVertex) {foundMinPath = true;break;}if (g.vInfo[currPos].color != vertexInfo<T>::BLACK) {g.vInfo[currPos].color = vertexInfo<T>::BLACK;for (auto i : g.vInfo[currPos].edges) {destPos = i.dest;if (g.vInfo[destPos].color == vertexInfo<T>::WHITE) {// 更新邻接顶点中距离变小的顶点，并push进FIFO，以待下一次确定最小顶点// 每更新一个顶点的distance，需要push进FIFO，维持堆序需要logN。if (newMinWeight = (g.vInfo[currPos].dataVal + i.weight)< g.vInfo[destPos].dataVal) {vertexData.endV = destPos;vertexData.pathWeight = newMinWeight;g.vInfo[destPos].dataValue = newMinWeight;g.vInfo[destPos].parent = currPos;minPathPQ.push(vertexData);}}}}}// clear path and setup returnpath.erase(path.begin(), path.end());if (foundMinPath){currPos = pos_eVertex;while (currPos != pos_sVertex){path.push_front((*(g.vInfo[currPos].vtxMapLoc)).first);currPos = g.vInfo[currPos].parent;}path.push_front(sVertex);returnValue = g.vInfo[pos_eVertex].dataValue;}elsereturnValue = -1;return returnValue;
}/*
* 要求每一对顶点之间的最短距离，可以每次以一个顶点为源点，重复执行FD i就开始他算法|V|次。这样，便可求每一对顶点的最短路径。总的执行时间为O（V的3次方）。
介绍Floyd算法，时间复杂度为O（V的3次方），但形式上间接，优雅，而且对于比较稠密的图，运行效率更快。
* 对于稀疏图，更快的是运行|v|次用FIFO编码的Dijkstra算法。
*
*/// 由于生成的最小生成树不再能用list保存了，因为它不是一维线性结构，而是图，所以需要重新创建一个新的图MST
// Prim算法生成MST
template<class T>
int PrimMinSpanTree(Graph<T> &g, Graph<T> &MST)
{priority_queue<minInfo, less<minInfo>> minTreePQ;minInfo vertexData;int minSpanTreeSize = 0;int minSpanTreeWeight = 0;int pos_sVertex = -1; // index of a starting vertexint i;// initializefor (i = 0; i < g.vInfo.size(); ++i) {if (g.vInfo[i].occupied) {if (pos_sVertex == -1)pos_eVertex = i;g.vInfo[i].color = vertexInfo<T>::WHITE;g.vInfo[i].dataValue = INFINITY;}}g.vInfo[pos_sVertex].dataValue = 0;g.vInfo[pos_sVertex].parent = pos_sVertex;vertexData.endV = pos_sVertex;vertexData.pathWeight = 0;int nums = g.numVertices;minTreePQ.push(vertexData);while (minSpanTreeSize != nums) {vertexData = minTreePQ.top();minTreePQ.pop();currPos = vertexData.endV;if (g.vInfo[currPos].color == VertexInfo<T>::WHITE) {g.vInfo[currPos].color = VertexInfo<T>::BLACK;minSpanTreeWeight += vertexData.pathWeight;minSpanTreeSize++;for (auto i : g.vInfo[currPos].edges) {if (i.weight < g.vInfo[i.dest].dataValue) {g.vInfo[i.dest].dataValue = i.weight;g.vInfo[i.dest].parent = currPos;vertexData.endV = i.dest;vertexData.pathWeight = i.weight;minTreePQ.push(vertexData);}}}}MST.clear();for (i = 0; i < g.vInfo.size(); ++i)if (g.vInfo[i].occupied)MST.insertVertex(*(g.vInfo[i].vtxMapLoc).first);T vA, vB; // vertex in MST// 从pos_eVertex开始找各个顶点的父亲顶点for (i = pos_sVertex + 1; i < g.vInfo.size(); ++i) {if (g.vInfo[i].occupied) {parentPos = g.vInfo[i].parent;MST.insertEdgeByIndex(parentPos, i, int weight)vA = (*g.vInfo[parentPos].vtxMapLoc).first;vB = (*g.vInfo[i].vtxMapLoc).first;MST.insertEdge(vA, vB, g.getWeight(vA, vB));}}return minSpanTreeWeight;
}/* Kruskal 求MST，
* 我们用到的一个事实是：在算法实施的任一时刻，两个顶点属于同意集合当且当
* 他们在当前的生成森林中连通。
*/
template<class T>
void KruskalMinSpanTree(Graph<T> &g, Graph<T> &MST)
{typedef int setType;// 把graph的边集合读到vector graphEdges中。vector<Edge> graphEdges = g.readGraphEdges();priority_queue<Edge, less<Edge> > pq(graphEdges);int currNumEdges = 0;int expectNumEdges = g.numberOfVertices() - 1;int numSets = expectNumEdges + 1;DisjSets ds(numSets);MST.clear();for (i = 0; i < g.vInfo.size(); ++i)if (g.vInfo[i].occupied)MST.insertVertex(*(g.vInfo[i].vtxMapLoc).first);while (currNumEdges < expectNumEdges) {Edge e = pq.top();pq.pop();setType uSet = ds.find(e.start);setType vSet = ds.find(e.end);if (uSet != vSet) {MST.insertEdgeByIndex(e.start, e.end, getWeightByIndex(e.start, e.end));ds.union(uSet, vSet);}}
}/*
* 拓扑排序通过找到入度为0的顶点，然后递减他的所有邻接顶点的入度， 再重复进行这一过程。
* 如果图是稀疏的，我们就可以预知，在每次迭代期间只有少数顶点的入度被更新，虽然只有一小部分发生变化，但
* 在搜索入度为0的顶点时我们潜在的查看了所有的顶点。
* 执行topologicalSort会修改图，所以传递参数调用Graph的复制构造函数复制传递。
* 算法的时间复杂度为O(|V| + |E|),线性的。
*/
template<class T>
void Graph<T>::topologicalSort(Graph<T> g, list<T> &tList)
{int i, counter = 0;vector<vertexInfo> &vec = g.vInfo;queue<int> q; // 存储入度为0的顶点的下标for(i = 0; i < vec.size(); ++i) if(vec[i].occupied && vec[i].inDegree == 0)q.push(i);while(!q.empty()) {i = q.top();q.pop();tList.push_back(*(vec[i].vtxMapLoc).first);counter++;for(auto i : vec[i].edges)if(--vec[i.dest].inDegree == 0)q.push(i.dest);}if(counter != g.numberOfVertices())throw graphError("cycle exist!\n");
}#endif