图的基础(C++)
阅读量：2029 次
发布时间：2019-04-28
本文共 5723 字，大约阅读时间需要 19 分钟。
DenseGraph.h
#ifndef DENSEGRAPH_H_INCLUDED#define DENSEGRAPH_H_INCLUDED#include #include #include #include #include #include using namespace std;//稠密图-邻接矩阵class DenseGraph{private: int n,m;//点和边 bool directed;//有向无向 vector >g;public: DenseGraph(int n,bool directed){ this->n=n; this->m=0; this->directed=directed; for(int i=0;i (n,false)); } } ~DenseGraph(){ } int V(){ return n;} int E(){ return m;} void addEdge(int v,int w){ assert(v>=0&&v =0&&w =0&&v =0&&w v=v; this->index=-1; } int begin(){ //要迭代的第一个元素 index=-1;//不见得第一个就是，而是应该找第一个为ture的元素 return next(); } int next(){ //从当前迭代的元素偏移，找下一个元素 for(index+=1;index =G.V(); } };};/*//稠密图遍历int main(){ int N=20; int M=100; DenseGraph g(N,false); for(int i=0;i
SparseGraph.h
#ifndef SPARSEGRAPH_H_INCLUDED#define SPARSEGRAPH_H_INCLUDED#include #include #include #include #include #include using namespace std;//稀疏图-邻接表class SparseGraph{private: int n,m; bool directed; vector >g;public: SparseGraph(int n,bool directed){ this->n=n; this->m=0; this->directed=directed; for(int i=0;i
()); } } ~SparseGraph(){ } void addEdge(int v,int w){ assert(v>=0&&v
=0&&w =0&&v =0&&w v=v; this->index=0; } int begin(){ //要迭代的第一个元素 index=0; if(G.g[v].size()) return G.g[v][index]; return -1; } int next(){ //从当前迭代的元素偏移，找下一个元素 index++; if(index =G.g[v].size(); } };};/*//稀疏图遍历int main(){ int N=20; int M=100; srand(time(NULL)); SparseGraph g1(N,false); for(int i=0;i ReadGraph.h
#ifndef READGRAPH_H_INCLUDED#define READGRAPH_H_INCLUDED//C++文件读取//可同时作用在稀疏图和稠密图上#include #include #include #include #include using namespace std;template class ReadGraph{public: ReadGraph(Graph &graph,const string &filename){ ifstream file ( filename ); string line; int V,E; assert(file.is_open()); assert(getline(file,line)); stringstream ss(line); ss>>V>>E; for(int i=0;i >a>>b;//把ss中的内容赋给a,b assert(a>=0&&a =0&&b readGraph1(g1,filename); g1.show(); cout< readGraph2(g2,filename); g2.show(); return 0;}*/#endif
Component.h
#ifndef COMPONENT_H_INCLUDED#define COMPONENT_H_INCLUDED#include #include using namespace std;template class Component{private: Graph &G; bool *visited; int ccount; int *id; void dfs(int v){ visited[v]=true; id[v]=ccount; typename Graph::adjInterator adj(G,v); for(int i=adj.begin();!adj.end();i=adj.next()){ if(!visited[i]) dfs(i); } }public: Component(Graph &graph):G(graph){ visited=new bool[G.V()]; id=new int[G.V()]; ccount=0; for(int i=0;i =0&&v =0&&w
Path.h
#ifndef PATH_H_INCLUDED#define PATH_H_INCLUDEDtemplate class Path{ //寻找图中从一个点到另外一个点的路径private: Graph &G; int s; bool* visited; int* from;//记录访问的当前节点的前一个节点 void dfs(int v){ visited[v]=true; typename Graph::adjInterator adj(G,v); for(int i=adj.begin();!adj.end();i=adj.next()){ if(!visited[i]){ from[i]=v; dfs(i); } } }public: Path(Graph &graph,int s):G(graph){ //算法初始化 assert(s>=0&&s s=s; //寻路算法 dfs(s); } ~Path(){ delete [] visited; delete [] from; } bool hasPath(int w){ //s->w是否有路 assert(w>=0&&w
&vec){
//s->w的路径 stack
s; int p=w; while(p!=-1){ s.push(p); p=from(p); } vec.clear(); while(!s.empty()){ vec.push_back(s.top()); s.pop(); } } void showPath(int w){
//打印路径 vector
vec; path(w,vec); for(int i=0;i
"; } }};/*int main(){ string filename="testG2.txt"; SparseGraph g=SparseGraph(7,false); ReadGraph readGraph(g,filename); Path dfs(g,0); cout<<"DFS: "; dfs.showPath(6); return 0;}*/#endif // PATH_H_INCLUDED ShortestPath.h
#ifndef SHORTESTPATH_H_INCLUDED#define SHORTESTPATH_H_INCLUDEDtemplate class ShortestPath{ //bfs求无权图的最短路径private: Graph &G; int s; bool *visited; int *from; int *ord;//记录从s到每一个节点的最短距离public: ShortestPath(Graph &graph,int s):G(graph){ //算法初始化 assert(s>=0&&s s=s; queue q; //无向图的最短路径算法 q.push(s); visited[s]=true; ord[s]=0; while(!q.empty()){ int v=q.front(); q.pop(); typename Graph::adjIterator(G,v); for(int i=adj.begin();!adj.end();i=adj.next()) if(!visited[i]){ q.push(i); visited[i]; from[i]=v; ord[i]=ord[v]+1; } } } ~ShortestPath(){ delete [] visited; delete [] from; delete [] ord; } bool hasPath(int w){ //s->w是否有路 assert(w>=0&&w
s; int p=w; while(p!=-1){ s.push(p); p=from(p); } vec.clear(); while(!s.empty()){ vec.push_back(s.top()); s.pop(); } } void showPath(int w){