B00015 C++实现的图类
程序员文章站
2022-07-01 18:34:38
代码来自:github - obscure76/graph: c++ graphs。
graph.h文件内容如下:
#include
#include
代码来自:github - obscure76/graph: c++ graphs。
graph.h文件内容如下:
#include<iostream> #include<cstring> #include<algorithm> #include<list> #include<set> #include<map> #include<queue> #include<climits> #define maxsize 100 using namespace std; class vertex { private: pair<int, vertex=""> > v; public: vertex(){}; vertex(int); bool addadjvertex(int); friend bool operator==(vertex const &, vertex const &); friend bool operator<(vertex const &, vertex const &); friend bool operator>(vertex const &, vertex const &); }; class edge { private: int weight; int src; int dst; public: edge(){}; edge(int, int, int); ~edge(){}; friend bool operator==(edge const &, edge const &); //friend bool operator<(edge const &, edge const &); //friend bool operator>(edge const &, edge const &); int getweight(); int getsource(); int getdest(); }; class graph { private: map<int, int=""> > vertices; list<edge> edges; set<int> visited; public: graph(); bool addvertex(int); bool addedge(int, int, int); bool deletevertex(int); void print(); void bfs(); void dfstraversal(); void dfs(int, list<int>); void pathsum(int); void findpath(int, int, char *, int, int); void bellman(); list<int> topologicalsort(); void topo(); };graph.cpp文件内容如下:
#include<graph.h> vertex::vertex(int v) { } bool vertex::addadjvertex(int v) { } list<int> order; bool operator==(vertex const &v1, vertex const &v2) { return true; } bool operator<(vertex const &v1, vertex const &v2) { return true; } bool operator>(vertex const &v1, vertex const &v2) { return true; } edge::edge(int a, int s1, int s2) { weight = a; src = s1; dst = s2; } int edge::getweight(){return weight;} int edge::getsource(){return src;} int edge::getdest(){return dst;} bool operator==( edge const &e1, edge const & e2) { if(e1.weight==e2.weight && e1.src==e2.src && e1.dst == e2.dst) return true; return false; } graph::graph(){} bool graph::addvertex(int v) { list<int> adjlist; vertices.insert(pair<int, list<int> >(v, adjlist)); } bool graph::addedge(int wt, int s, int d) { edges.push_back(edge(wt, s, d)); map<int, list<int> >::iterator sit = vertices.find(s); if(sit!=vertices.end()) sit->second.push_back(d); else { list<int> adjlist; adjlist.push_back(d); vertices.insert(pair<int, list<int> >(s, adjlist)); } sit = vertices.find(d); if(sit == vertices.end()) { list<int> adjlist1; vertices.insert(pair<int, list<int> >(d, adjlist1)); } } bool graph::deletevertex(int v) { } void graph::print() { map<int, list<int> >::iterator it; for(it = vertices.begin();it!=vertices.end();it++) { cout<<"node "<<it->first<<'-'; for(list<int>::iterator lit = it->second.begin();lit!=it->second.end();lit++) cout<<*lit<<','; cout<<endl; } } void graph::bfs() { queue<int> q; visited.clear(); q.push(vertices.begin()->first); visited.insert(vertices.begin()->first); cout<<"\n bfs traversal :"; while(q.size() > 0) { int v = q.front(); q.pop(); list<int> adjlist = vertices.find(v)->second; list<int>::iterator it; set<int>::iterator sit; for(it = adjlist.begin();it!=adjlist.end();it++) { sit = visited.find(*it); if(sit!=visited.end()) continue; visited.insert(*it); q.push(*it); } cout<<v<<" "; } } void graph::dfstraversal() { visited.clear(); cout<<"\ndfs traversal :"; map<int, list<int> >::iterator it; for(it = vertices.begin();it!=vertices.end();it++) { if(visited.find(it->first) != visited.end()) continue; visited.insert(it->first); dfs(it->first, it->second); } cout<<endl; } void graph::dfs(int v, list<int> adj) { list<int>::iterator lit; for(lit = adj.begin();lit!=adj.end();lit++) { if(visited.find(*lit) != visited.end()) continue; visited.insert(*lit); dfs(*lit, vertices.find(*lit)->second); } cout<<v<<' '; order.push_front(v); } void graph::pathsum(int sum) { char *str; str = (char *)malloc(100); memset(str, 0, 100); visited.clear(); map<int, list<int> >::iterator it; it = vertices.begin(); findpath(sum, 0, str, 0, it->first); } void graph::findpath(int sum, int cval, char *str, int in, int curr) { if(curr+cval > sum) return; if(cval+curr == sum) { str[in] = '0' + curr; str[in+1] = '\0'; cout<<str<<endl; visited.insert(curr); if(visited.find(curr)==visited.end()) findpath(sum, 0, str, 0, curr); } else { cval += curr; //cout<<"cval now"<<cval<<'\t'; str[in] = '0'+curr; map<int, list<int> >::iterator it; it = vertices.find(curr); if(it==vertices.end()) return; list<int> adj = it->second; for(list<int>::iterator lit = adj.begin();lit!=adj.end();lit++) findpath(sum, cval, str, in+1, *lit); for(list<int>::iterator lit = adj.begin();lit!=adj.end();lit++) { if(visited.find(*lit)==visited.end()) { visited.insert(*lit); findpath(sum, 0, str, 0, *lit); } } } } void graph::bellman() { order.clear(); dfstraversal(); map<int, int> vd; map<int, list<int> >::iterator it; int vlen = vertices.size(); for(it = vertices.begin();it!=vertices.end();it++) vd.insert(pair<int, int>(it->first, int_max)); vd.find(vertices.begin()->first)->second = 0; list<int>::iterator lit; for(lit=order.begin();lit!=order.end();lit++) { list<edge>::iterator it; for(it = edges.begin();it!=edges.end();it++) { int src = it->getsource(); int dst = it->getdest(); int wt = it->getweight(); if(src!=*lit) continue; if(vd.find(dst)->second > vd.find(src)->second+wt) vd.find(dst)->second = vd.find(src)->second+wt; } } map<int, int>::iterator mit; for(mit = vd.begin();mit!=vd.end();mit++) cout<<mit->first<<" at dist "<<mit->second<<endl; } list<int> graph::topologicalsort() { order.clear(); dfstraversal(); for(list<int>::iterator it = order.begin();it!=order.end();it++) cout<<*it; return order; } void graph::topo() { order.push_back(4); } int main() { graph g; g.addedge(1,1,2); g.addedge(1,1,3); g.addedge(1,2,4); g.addedge(1,2,5); g.addedge(1,3,6); g.addedge(1,3,8); g.print(); g.bfs(); g.dfstraversal(); g.pathsum(8); cout<<endl; g.topologicalsort(); cout<<endl; g.bellman(); return 0; }
上一篇: 啤酒是酸性还是碱性呢