首页 > 代码库 > 简单Graph类
简单Graph类
#include<iostream> #include<string> #include<queue> #include<algorithm> #include<cstdio> #include<vector> using namespace std; class Node { public: bool vis; int first; Node() { vis=false; first=-1; } }; template<typename Elem> class Edge { public: int from,to; Elem val; int nxt; Edge(int f,int t,Elem v) :from(f),to(t),val(v) {} Edge(){} explicit Edge(Edge &b) { b.from=from; b.to=to; b.val=val; b.nxt=nxt; } }; template <typename Elem> class Graph { int num_of_edge,num_of_node;//容量,真实值大于等于这个值时执行expand函数 int curNodeSize,curEdgeSize; Node *node; Edge<Elem> *edge; private: void expandNode() { num_of_node<<=1; Node *tem=node; node=new Node[num_of_node]; for(int i=0;i<curNodeSize;i++) { node[i]=tem[i]; } delete tem; } void expandEdge() { num_of_edge<<=1; Edge<Elem> *tem=edge; edge=new Edge<Elem>[num_of_edge]; for(int i=0;i<curEdgeSize;i++) { edge[i]=tem[i]; } delete tem; } public: Graph(int nodeNum,int edgeNum) { node=new Node[nodeNum]; edge=new Edge<Elem>[edgeNum]; num_of_edge=edgeNum; num_of_node=nodeNum; curNodeSize=0,curEdgeSize=0; } Graph() { num_of_edge=1000; num_of_node=500; node=new Node[500]; edge=new Edge<Elem>[1000]; curNodeSize=0,curEdgeSize=0; } void reset() { for(int i=0;i<curNodeSize;i++) { node[i].first=-1; } curNodeSize=0,curEdgeSize=0; } void addEdge(int from,int to,Elem val) { edge[curEdgeSize].nxt=node[from].first; edge[curEdgeSize].val=val; edge[curEdgeSize].to=to; edge[curEdgeSize].from=from; node[from].first=curEdgeSize++; if(curEdgeSize==num_of_edge) expandEdge(); } void addNode() { curNodeSize++; if(curNodeSize==num_of_node) expandNode(); } void DFS(int root) { cout<<root<<' '; node[root].vis=true; for(int i=node[root].first;i!=-1;i=edge[i].nxt) { int to=edge[i].to; if(node[to].vis==false) { DFS(to); } } } }; int main() { Graph<int> graph(10,50); for(int i=0;i<5;i++) graph.addNode(); graph.addEdge(0,2,3); graph.addEdge(1,3,6); graph.addEdge(0,1,6); graph.DFS(0); }
简单Graph类
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。