图论练习题主要包括： 1. dfs 2. bfs 3. kruskal 4. prim 5. dijsktra
/************************************************************************* > File Name: graph.cpp > Author: Yuji CAO > Mail: yujicao@amazon.com > Created Time: 2016年08月13日 星期六 20时53分41秒 ************************************************************************/ #include<iostream> #include<vector> #include<unordered_map> #include<unordered_set> #include<sstream> #include<list> #include<queue> #include<stack> #include<string> #include<utility> #include<algorithm> #include<fstream> using namespace std; class UnionFind { public: UnionFind(int n) { s.resize(n); for (int i = 0; i < n; ++i) { s[i] = i; } } void uni(int t1, int t2) { int r1 = find(t1); int r2 = find(t2); if (r1 != r2) { s[r2] = r1; } } int find(int t) { if (s[t] == t) return t; s[t] = find(s[t]); return s[t]; } void print() { for (int i = 0; i < s.size(); ++i) { cout<<i<<"\t"; } cout<<endl; for (int i = 0; i < s.size(); ++i) { cout<<s[i]<<"\t"; } cout<<endl; } private: vector<int> s; }; namespace graph { struct G { vector<int> getAdj(int cur) { if (nodes.find(cur) != nodes.end()) return nodes[cur]; else { vector<int> a; return a; } } void setAdj(int from, vector<int>& adjs) { nodes[from] = adjs; } int size() { return (int)nodes.size(); } private: unordered_map<int,vector<int> > nodes; }; struct GWeight { GWeight(int n) { matrix.resize(n); for (int i = 0; i < n; ++i) { matrix[i].resize(n); } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (i == j) matrix[i][j] = 0; else matrix[i][j] = numeric_limits<int>::max(); } } } int getWeight(int i, int j) { return matrix[i][j]; } int setWeight(int i, int j, int w) { matrix[i][j] = w; } int size() { return (int) matrix.size(); } private: vector<vector<int> > matrix; }; static GWeight fromFile2(string file) { ifstream stream; stream.open(file, ios::in); char buffer[1024]; int n; stream>>n; GWeight g(n); int i = 0; int j = 0; stream.getline(buffer, 1024); while(stream.getline(buffer, 1024)) { string buf(buffer); int pre = -1; for (int k = 0; k < buf.size(); ++k) { if (buf[k] == ',') { /* 0 1 2 3 4 5 6 a b , c d e , */ int len = k - 1 - pre; string word = buf.substr(pre + 1, len); int w = atoi(word.c_str()); pre = k; if (word == "#") { w = numeric_limits<int>::max(); } g.setWeight(i, j++ % n, w); } } i++; } stream.close(); return g; } static G fromFile(string file) { G g; ifstream stream; stream.open(file, ios::in); char buffer[1024]; while(stream.getline(buffer,1024)) { string buf(buffer); int pre = -1; int index = -1; vector<int> adjs; for (int i = 0; i < buf.size(); ++i) { if (buf[i] == ',') { int len = i - 1 - pre; string word = buf.substr(pre + 1, len); int wordInt = atoi(word.c_str()); if (index == -1) { index = wordInt; } else { adjs.push_back(wordInt); } pre = i; } } g.setAdj(index, adjs); } stream.close(); return g; }; /* * 0 * | * 1---2---3--- * | | \ * 4---5---6----7 * 1->2,4 * 2->1,3,5 * 3->2,7 * 4->1,5 * 5->2,4,6 * 6->5,7 * 7->3,6 * * 0->0 0 * 0->1 1 * 0->2 2 * 0->3 3 * 0->4 2 * 0->5 3 * 0->6 4 * 0->7 4 * bfs * 0,1,2,4,3,5,7,6 * dfs * 0,1,2,3,7,6,5,4 */ namespace mst { struct Edge { int from; int to; int w; Edge():from(-1),to(-1),w(numeric_limits<int>::max()){} Edge(int from, int to, int w) : from(from), to(to), w(w){} bool operator < (const Edge& r) const { return this->w > r.w; } Edge& operator=(const Edge& r) { from = r.from; to = r.to; w = r.w; return *this; } string toString() { stringstream ss; ss<<"[from:"<<from <<",to:"<<to <<",w:"<<w<<"]"; return ss.str(); } }; }; namespace ssp { struct Dist { int to; int dist; Dist(int to, int dist):to(to), dist(dist){} bool operator < (const Dist& r) const { return dist > r.dist; } }; }; class Graph { public: vector<int> bfs(G& g, int s, vector<int>& dist) { dist.resize(g.size()); for (int i = 0; i < g.size(); ++i) { dist[i] = 0; } vector<int> ans; queue<int> q; q.push(s); ans.push_back(s); unordered_set<int> visited; visited.insert(s); while(!q.empty()) { int f = q.front(); q.pop(); vector<int> adjs = g.getAdj(f); for (auto adj : adjs) { if (visited.find(adj) == visited.end()) { ans.push_back(adj); visited.insert(adj); q.push(adj); dist[adj] = 1 + dist[f]; } } } return ans; } vector<vector<int> > dfs(G& g) { vector<vector<int> > ans; unordered_set<int> visited; for (int i = 0; i < g.size(); ++i) { vector<int> ansEle; if (visited.find(i) == visited.end()) { dfsInner(g, i, ansEle, visited); ans.push_back(ansEle); } } return ans; } vector<mst::Edge> spanningTree(GWeight& g, bool k = false) { if (k)return kruskal(g); return prim(g); } vector<int> shortestPath(GWeight& g, int s) { return dijkstra(g, s); } void shortestPathOfAll(const G& g) { } private: void dfsInner(G& g, int s, vector<int>& ans, unordered_set<int>& visited) { visited.insert(s); ans.push_back(s); vector<int> adjs = g.getAdj(s); for (auto adj : adjs) { if (visited.find(adj) == visited.end()) { dfsInner(g, adj, ans, visited); } } } vector<mst::Edge> kruskal(GWeight& g) { UnionFind uf(g.size()); priority_queue<mst::Edge> q; for (int i = 0; i < g.size(); ++i) { for (int j = 0; j < g.size(); ++j) { if (g.getWeight(i, j) != numeric_limits<int>::max()) { mst::Edge e (i, j , g.getWeight(i, j)); q.push(e); } } } vector<mst::Edge> ans; while (!q.empty()) { mst::Edge e = q.top(); if (uf.find(e.from) != uf.find(e.to)) { ans.push_back(e); uf.uni(e.from, e.to); } q.pop(); } return ans; } //prim int extractMin(vector<mst::Edge>& d, unordered_set<int>& visited, int n) { int ans = -1; int min = numeric_limits<int>::max(); for (int i = 0; i < n; ++i) { if(visited.find(i) != visited.end()) continue; if (min > d[i].w) { min = d[i].w; ans = i; } } return ans; } vector<mst::Edge> prim(GWeight& g) { unordered_set<int> visited; vector<mst::Edge> dd; dd.resize(g.size()); mst::Edge edge(0,0,0); dd[0] = edge; vector<mst::Edge> ans; for (int i = 0; i < g.size(); ++i) { int v = extractMin(dd, visited, g.size()); if (!(dd[v].to == v && v == 0)) { ans.push_back(dd[v]); } visited.insert(v); for (int u = 0; u < g.size(); ++u) { if (g.getWeight(v, u) < dd[u].w) { int d = g.getWeight(v,u); mst::Edge e(v, u, d); dd[u] = e; } } } return ans; } //dijkstra void init(GWeight& g, int s, priority_queue<ssp::Dist>& q, vector<int>& dist) { dist.resize(g.size()); for (int i = 0; i < g.size(); ++i) { int m = numeric_limits<int>::max(); if (i == s) { ssp::Dist d(i, 0); d.dist = 0; q.push(d); m = 0; } dist[i] = m; } } vector<int> dijkstra(GWeight& g, int s) { vector<int> dist; priority_queue<ssp::Dist> queue; init(g, s, queue, dist); unordered_set<int> visited; visited.insert(0); for (int i = 0; i < g.size(); ++i) { ssp::Dist top = queue.top(); queue.pop(); int f = top.to; visited.insert(top.to); for (int j = 0; j < g.size(); ++j) { int v = g.getWeight(f, j); if (visited.find(j) != visited.end()) continue; if (v == numeric_limits<int>::max()) continue; if (dist[j] > v + dist[f]) { dist[j] = v + dist[f]; ssp::Dist d(j, dist[j]); queue.push(d); } } } return dist; } }; /* class DirectGraph { public: vector<int> topologicalSort(G& g) { vector<int> ans; for (int i = 0; i < g.size(); ++i) { if () } return ans; } void shortestPath(G& g) { return; } vector<vector<int> > strongConnectedComponent(G& g) { vector<vector<int> > ans; return ans; } }; class DAG { public: void shortestPath(const G& g, int s) { } void longestPath(const G& g, int s) { } }; */ }; int main() { graph::G g = graph::fromFile("./g.txt"); graph::Graph gOpt; cout<<"breadth first search"<<endl; vector<int> dist; vector<int> ans = gOpt.bfs(g, 0, dist); for (int i = 0; i < dist.size(); ++i) { cout<<"0->"<<i<<":\t"<<dist[i]<<endl; } for (int ele : ans) { cout<<ele<<","; } cout<<endl; cout<<"depth first search"<<endl; auto ans1 = gOpt.dfs(g); for (auto eleI : ans1) { for (auto eleJ : eleI) { cout<<eleJ<<","; } cout<<endl; } graph::GWeight gw = graph::fromFile2("./gw.txt"); cout<<"spanning tree kruskal"<<endl; auto ans2 = gOpt.spanningTree(gw, true); for (auto ele : ans2) { cout<<ele.toString()<<endl; } cout<<"spanning tree prim"<<endl; auto ans3 = gOpt.spanningTree(gw, false); for (auto ele : ans3) { cout<<ele.toString()<<endl; } cout<<"shortest path dijkstra"<<endl; auto ans4 = gOpt.shortestPath(gw, 0); int i = 0; for (auto ele : ans4) { cout<<0<<"->"<<i<<":\t"<<ele<<endl; i += 1; } return 0; }