和图相关的算法有：最小生成子树，最短路径，拓扑排序。
这里仅介绍最小生成树和最短路径，拓扑排序暂时省略。
最小生成子树（minimum spanning tree)
最小生成子树：构造一颗树，这棵树连接所有点，这些边权重纸盒最小。
比如一个图是这样：
msp1
它的最小生成树是这样:
msp2
构造最小生成树有两种方法：Prim算法和kruskal算法。
Prim算法：
- 输入：一个加权连通图，其中顶点集合为V，边集合为E；
- 初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；
- 重复下列操作，直到Vnew = V：
- 在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
- 将v加入集合Vnew中，将<u, v>边加入集合Enew中；
- 输出：使用集合Vnew和Enew来描述所得到的最小生成树。
实现：
class GraphUtil {
public:
class MinimumSpanningTree {
public:
static int Prim(const Graph &g, int start, std::vector<std::pair<int, int>> &paths);
static void test(Graph &g); // test function
struct PrimHelperEdge {
int adjVertex = -1; // the vertex that makes minimum weight with this node
int cost2Added = 0; // minimum weight from this to the vertexes in added set. if this belongs to added set, cost2Added = 0;
};
protected:
static int Prim_nextMinEdge(std::vector<PrimHelperEdge> &closest);
};
static const int MAX_INT; // = std::numeric_limits<int>::max() / 2;
};
// .cpp
const int GraphUtil::MAX_INT = std::numeric_limits<int>::max() / 2;
int GraphUtil::MinimumSpanningTree::Prim(const Graph &g, int start, std::vector<std::pair<int, int>> &paths) {
const int N = g.GetNumberOfNodes();
if (N <= 1) {
return 0;
}
vector<PrimHelperEdge> closestEdges(N);
int max_int = MAX_INT;
for (int i = 0; i < N; i++) {
closestEdges[i].adjVertex = start;
int w = g.GetWeightForEdge(start, i);
if (w) {
closestEdges[i].cost2Added = w;
} else {
closestEdges[i].cost2Added = max_int;
}
}
closestEdges[start].cost2Added = 0;
int totWeight = 0;
for (int i = 0; i < N - 1; i++) {
int k = Prim_nextMinEdge(closestEdges);
int x = closestEdges[k].adjVertex;
paths.emplace_back(x, k);
totWeight += closestEdges[k].cost2Added;
closestEdges[k].cost2Added = 0; // add k to the added set
auto it = g.CreateSpIteratorForNode(k); // edges connected with k
while (it->HasNext()) { // update u, that u connects with k and u doesn't belong to added set
auto e = it->Next();
int y = e.y;
if (e.weight > 0 && e.weight < closestEdges[y].cost2Added) {
closestEdges[y].cost2Added = e.weight;
closestEdges[y].adjVertex = k;
}
}
}
return totWeight;
}
int GraphUtil::MinimumSpanningTree::Prim_nextMinEdge(vector<GraphUtil::MinimumSpanningTree::PrimHelperEdge> &closest) {
int mn = MAX_INT;
int k = -1;
for (int i = 0; i < closest.size(); i++) {
if (closest[i].cost2Added > 0 && closest[i].cost2Added < mn) {
mn = closest[i].cost2Added;
k = i;
}
}
return k;
}
void GraphUtil::MinimumSpanningTree::test(Graph &g) {
vector<pair<int, int>> paths;
int tot = MinimumSpanningTree::Prim(g, 1, paths);
auto print = [](int sum, vector<pair<int, int>> &p) {
cout << "min wieght: " << sum << endl;
for (auto &e: p) {
cout << "(" << e.first << ", " << e.second << ") ";
}
cout << endl;
};
print(tot, paths);
paths.clear();
tot = MinimumSpanningTree::Kruskal_ShortestPath(g, paths);
print(tot, paths);
}
其中paths[i] 为一个pair<int, int>，paths中的一个元素p表示， p.first到p.second这条边是在最小生成子树中。
时间复杂度为O(n2)
kruskal算法
- 先选取权重最小的边；
- 选取一条权重最小的边（没有被选过的），如果这条边不会构成一个环路，则把这条边加入已经选好的集合中；否则舍弃这条边。选取下一条权重最小的边。
- 直至所有的点都被连通且无环路。
实现:
class MinimumSpanningTree {
public:
static int Prim(const Graph &g, int start, std::vector<std::pair<int, int>> &paths);
// helper function to determine if two nodes belong to same subgraph
static void MergeUnion(std::vector<int> &unionVec, int root, int root2);
// help function
static int FindRoot(const std::vector<int> &unionVec, int x);
struct KruskalCmp {
bool operator()(const Graph::Edge &e1, const Graph::Edge &e2) {
return e1.weight >= e2.weight;
}
};
};
// .cpp
int GraphUtil::MinimumSpanningTree::Kruskal_ShortestPath(const Graph &g, std::vector<std::pair<int, int>> &paths) {
const int N = g.GetNumberOfNodes(); // construct heap
if (N <= 1) {
return 0;
}
priority_queue<Graph::Edge, vector<Graph::Edge>, KruskalCmp> q;
for (int i = 0; i < N; i++) {
auto p = g.CreateSpIteratorForNode(i);
while (p->HasNext()) {
auto e = p->Next();
if (e.x < e.y) {
q.push(e);
}
}
}
vector<int> unionVec(N);
for (int i = 0; i < N; i++) {
unionVec[i] = -1;
}
int tot = 0;
while (!q.empty()) {
auto e = q.top();
q.pop();
auto r1 = FindRoot(unionVec, e.x);
auto r2 = FindRoot(unionVec, e.y);
if (r1 != r2) { // won't make a cycle
tot += e.weight;
MergeUnion(unionVec, r1, r2);
paths.emplace_back(e.x, e.y);
}
}
return tot;
}
int GraphUtil::MinimumSpanningTree::FindRoot(const std::vector<int> &unionVec, int x) {
while (unionVec[x] >= 0) {
x = unionVec[x];
}
return x;
}
void GraphUtil::MinimumSpanningTree::MergeUnion(std::vector<int> &unionVec, int root, int root2) {
unionVec[root2] = root;
}
时间复杂度为O(eloge). loge来自从优先队列中选取一条边。
注意：里面的MergeUnion和FindRoot可以用来判断一个两个数是否属于一个集合，以及合并两个集合。
最短路径
最短路径也有两种算法：Dijkstra算法和Floyd算法。
Dijkstra算法
- 初始集合V2，仅包括起始点
- 从V中选取距离集合V2最近的点（距离V2最近的点：意思是距离V2中某一点最近）
- 直至选到终点
class GraphUtil {
public:
class ShortestPath {
public:
static void test(const Graph &g, int start, int end);
static int Dijkstra(const Graph &g, int start, int end, std::vector<int> &paths);
protected:
static int DjNextMin(const std::vector<std::pair<int, int>> &d, const std::vector<int> &found);
static void BuildDjPath(const std::vector<int> &d, int start, int end, std::vector<int> &paths);
};
};
// .cpp
int GraphUtil::ShortestPath::Dijkstra(const Graph &g, int start, int end, vector<int> &paths) {
const int N = g.GetNumberOfNodes();
if (N <= 1) {
return 0;
}
// first is distance, second is the vertex that connects to this node in dj graph
pair<int, int> initValue(MAX_INT, -1);
vector<pair<int, int>> d(N, initValue); // all initialized to a big integer
vector<int> found(N, 0);
vector<int> djTmpPath(N, -1);
found[start] = 1;
{
auto it = g.CreateSpIteratorForNode(start);
while (it->HasNext()) {
auto e = it->Next();
d[e.y].first = e.weight;
d[e.y].second = start;
}
}
for (int i = 0; i < N; i++) {
int k = DjNextMin(d, found);
if (k == -1) { // no nodes anymore
break;
}
found[k] = 1;
djTmpPath[k] = d[k].second;
auto it2 = g.CreateSpIteratorForNode(k);
while (it2->HasNext()) { // update it's adjacent nodes
auto e = it2->Next();
if (d[e.y].first > (d[k].first + e.weight)) {
d[e.y].first = d[k].first + e.weight; // start -> e.y will pass node k. It's weight is d[k].first + e.weight
d[e.y].second = k;
}
}
}
if (d[end].first != MAX_INT) {
BuildDjPath(djTmpPath, start, end, paths); // prevent infinte loop
}
return d[end].first;
}
// find the next vertex that has min length to the found set
int GraphUtil::ShortestPath::DjNextMin(const std::vector<std::pair<int, int>> &d, const std::vector<int> &found) {
int min_value = MAX_INT;
int k = -1;
for (int i = 0; i < d.size(); i++) {
if (!found[i] && d[i].first < min_value) {
min_value = d[i].first;
k = i;
}
}
return k;
}
void GraphUtil::ShortestPath::BuildDjPath(const std::vector<int> &d, int start, int end,
std::vector<int> &paths) {
paths.clear();
int i = end;
while (i != -1) {
paths.push_back(i);
i = d[i];
}
std::reverse(paths.begin(), paths.end());
}
void GraphUtil::ShortestPath::test(const Graph &g, int start, int end) {
vector<int> paths;
cout << "dj shortest path: " << Dijkstra(g, start, end, paths) << endl;
for (auto i: paths) {
cout << i << " ";
}
cout << endl;
vector<vector<int>> pathMat, mat;
Floyd_ShortestPath(g, mat, pathMat);
paths.clear();
cout << "floyd shorted path: " << mat[start][end] << endl;
Floyd_GetPath(pathMat, start, end, paths);
for (auto i: paths) {
cout << i << " ";
}
}
Floyd算法
算法的核心思想是:
点i到j的最短距离，要么经过k，要么不经过k。
mat[i][j]表示i到k的最短距离: mat[i][j] = min {mat[i][k] + mat[k][j]}, 其中顶点i属于V。
class ShortestPath {
public:
using FloyMat = std::vector<std::vector<int>>;
static void Floyd_ShortestPath(const Graph &g, GraphUtil::ShortestPath::FloyMat &mat,
GraphUtil::ShortestPath::FloyMat &path);
static void Floyd_GetPath(const FloyMat &pathMat, int start, int end, std::vector<int> &paths);
};
// .cpp
void GraphUtil::ShortestPath::Floyd_ShortestPath(const Graph &g, GraphUtil::ShortestPath::FloyMat &mat,
GraphUtil::ShortestPath::FloyMat &path) {
if (g.GetNumberOfNodes() < 1) {
return;
}
const int N = g.GetNumberOfNodes();
mat.resize(N, vector<int>(N, MAX_INT));
path.resize(N, vector<int>(N, -1)); // path[i][j] = k, means i -> j will pass k
for (int i = 0; i < N; i++) {
auto it = g.CreateSpIteratorForNode(i);
while (it->HasNext()) {
auto e = it->Next();
mat[i][e.y] = e.weight;
path[i][e.y] = e.y;
}
}
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
if ((mat[j][i] + mat[i][k]) < mat[j][k]) {
mat[j][k] = mat[j][i] + mat[i][k];
path[j][k] = i;
}
}
}
}
}
void GraphUtil::ShortestPath::Floyd_GetPath(const GraphUtil::ShortestPath::FloyMat &pathMat, int start, int end,
vector<int> &paths) {
paths.clear();
int i = end;
while (i != -1) {
paths.push_back(i);
if (i == pathMat[start][i]) {
break;
}
i = pathMat[start][i];
}
paths.push_back(start);
std::reverse(paths.begin(), paths.end());
}
应该注意以上这些算法中路径的保存。
