LGraph.cpp
Upload User: lsjld999
Upload Date: 2022-06-19
Package Size: 980k
Code Size: 6k
Category:

Graph program

Development Platform:

Visual C++

  1. #include "iostream"
  2. #include "Queue.h"
  3. #include "Forest.h"
  4. using namespace std;
  5.  enum error_code {Failure,success,NotPresent,Duplicate};
  6. struct gnode 
  7. {
  8. gnode (){nextArc=NULL;}
  9. gnode (int vertex,int weight,gnode * next)
  10. {adjVex=vertex; w=weight;nextArc=next;}
  11. int adjVex;
  12. int w;
  13. gnode* nextArc;
  14. };
  15. class  LGraph
  16. {
  17. public :
  18. int  bainshu();//求图的边数
  19.     void panduan_tree(LGraph &G);//判断是否为有向树
  20. void DFS_creat_tree();//深度遍历生成树
  21. void preorder(fnode * &T);
  22. void output_layer();//输出各个节点的值及层次数
  23. void BFS_creat_tree();//广度遍历生成树
  24. void creat_tree(fnode * & T,int v);//遍历生成树
  25. void output_path(int w,int first);//输出路径
  26. void BFS_solve(LGraph &G);
  27.    void BFS_solve(LGraph &G, int v,int q);//求解给定顶点到某一顶点的路径
  28. void creat();//创建图
  29. LGraph(){n=0; e=0;};//构造函数
  30. LGraph(int mSize);//构造函数
  31. error_code Insert (int u,int v,int w);//插入边
  32. error_code  Remove (int u,int v);//删除边
  33. bool Exist(int u,int v);//判断边是否存在
  34. int firstAdj(LGraph G,int v);//求第一个元素
  35. int  nextAdj(LGraph G,int v,int w);//求元素在W 后的元素
  36.     void DFS(LGraph & G,int v);//深度遍历
  37. void DFS_travel(LGraph &G);//深度遍历图
  38. void BFS(LGraph & G,int v);//广度遍历
  39. void BFS_travel(LGraph &G);// 广度遍历图
  40. protected:
  41. gnode **  a;//节点数组
  42. int n;
  43. int e;queue<fnode *> Q;
  44. bool   visited[50];
  45. bool Tag[20][20];fnode * W;
  46. };
  47. LGraph::LGraph(int mSize)
  48. {
  49.  n=mSize; e=0;
  50.  a=new  gnode *[n];
  51.  for(int i=1;i<=n;i++)
  52.  a[i]=NULL;
  53. }
  54. bool LGraph::Exist(int u, int v)
  55. {
  56.  if(u==1||v==1||u>n||v>n)
  57.  return false ;
  58.  gnode *p=a[u];
  59.  while (p&&p->adjVex!=v)
  60.  p=p->nextArc;
  61.  if(!p)return false;
  62.  else return true;
  63. }
  64. error_code LGraph::Insert(int u, int v, int w)
  65. {
  66. if (u<1||v<1||u>n||v>n||u==v)  return Failure;
  67. if(Exist(u,v)) 
  68. return Duplicate;
  69. gnode *p=new gnode (v,w,a[u]);
  70. a[u]=p;e++;
  71. return success;
  72. }
  73. error_code  LGraph::Remove (int u,int v)
  74. {
  75. if(u<1||v<1||u>n||v>n)  return Failure;
  76. gnode *p=a[u];gnode *q=NULL;
  77. while (p&&p->adjVex!=v)
  78. {q=p; p=p->nextArc;}
  79. if(!p) return NotPresent;
  80. if (q)  q->nextArc=p->nextArc;
  81. else  a[u]=p->nextArc;
  82. delete p;
  83. e--;
  84. return success;
  85. }
  86. void LGraph::creat()
  87. {int m;  
  88. cout<<"请输入节点总数 "<<endl;
  89. cin>>m;
  90. n =m;
  91. e=0;
  92. a=new  gnode *[n];
  93.  for(int j=1;j<=n;j++)
  94.  a[j]=NULL;
  95. for(int i=1;i<=n;i++)
  96. {int w=0;
  97. cout<<"与 "<<i<<"相关的点  "<<endl;
  98. int x; 
  99. while (cin>>x)
  100. Insert(i,x,w);
  101. cin.clear();
  102. }
  103. }
  104. int LGraph::firstAdj(LGraph G,int v)
  105. {
  106. if (v>=1&&v<=n) return a[v]->adjVex;
  107. else return 0;
  108. }
  109. int LGraph::nextAdj(LGraph G,int v,int w)
  110. {if (v>=1&&v<=n) 
  111. {
  112. gnode *q=a[v];
  113. while (q->adjVex!=w) q=q->nextArc;
  114. {if (q->nextArc!=NULL)
  115. return q->nextArc->adjVex;
  116. else return 0;
  117. }
  118. }
  119. else return 0;
  120. }
  121. void LGraph::DFS(LGraph & G,int v)
  122. {
  123. int w;
  124. cout<<v<<"   "; visited[v]=true;
  125. w=firstAdj(G,v);
  126. while (w!=0)
  127. {
  128. if(visited[w]==false){Tag[v][w]=true;
  129. DFS(G,w);
  130. }
  131. w=nextAdj(G,v,w);
  132. }
  133. }
  134. void LGraph::DFS_travel(LGraph &G)
  135. {
  136. int i;
  137. for(i=1;i<=n;i++)
  138. visited[i]=false;
  139. for(int i=1;i<=n;i++)
  140. for(int j=1;j<=n;j++)
  141. Tag[i][j]=false;
  142. cout<<"深度遍历图"<<endl;
  143. for(i=1;i<=n;i++)
  144. if(visited[i]==false)
  145. DFS(G,i);
  146. cout<<endl;
  147. }
  148. void LGraph::BFS(LGraph &G, int v)
  149. {
  150. int w;
  151. queue<int> Q;
  152. cout<<v<<"   ";
  153. visited[v]=true;
  154. Q.append(v);
  155. while (!Q.empty())
  156. {
  157. v=Q.serve();
  158. w=firstAdj(G,v);
  159. while (w!=0)
  160. {
  161. if (!visited[w])
  162. {
  163. cout<<w;Tag[v][w]=true;
  164. visited[w]=true;
  165. Q.append(w);}
  166. w=nextAdj(G,v,w);
  167. }
  168. }
  169. }
  170. void LGraph::BFS_travel(LGraph & G)
  171. {
  172. int i;
  173. for(i=1;i<=n;i++)
  174. visited[i]=false;
  175. for(int i=1;i<=n;i++)
  176. for(int j=1;j<=n;j++)
  177. Tag[i][j]=false;
  178. cout<<"广度遍历图"<<endl;
  179. for(i=1;i<=n;i++)
  180. if(visited[i]==false)
  181. BFS(G,i);
  182. cout<<endl;
  183. }
  184. void LGraph::BFS_solve(LGraph & G)
  185. {int a;
  186. for(int k=1;k<=n;k++)
  187. visited[k]=false;
  188. for(int i=1;i<=n;i++)
  189. for(int j=1;j<=n;j++)
  190. Tag[i][j]=false;
  191. cout<<"请输入出发顶点 "<<endl;
  192. cin>>a;
  193. for(int b=1;b<=n;b++){
  194. cout<<"从顶点 "<<a<<"到顶点"<<b<<"的最短路径"<<endl;
  195. BFS_solve(G, a, b);
  196. cout<<endl;
  197. }
  198. }
  199. void LGraph::BFS_solve(LGraph & G,int v,int q)
  200. {
  201. int m=0;  bool p=false;
  202. int w; int  first=v;
  203. queue<int> Q;
  204. visited[v]=true;
  205. Q.append(v);
  206. if (v==q) cout<<"NO PATH"<<"   "<<"steps "<<m; 
  207. else 
  208. {
  209. while(!Q.empty())
  210. {
  211. v=Q.serve();
  212. w=firstAdj(G,v);
  213. while (w!=0)
  214. {
  215. if (!visited[w])
  216. {
  217. visited[w]=true;
  218. Q.append(w);
  219. Tag[v][w]=true;
  220. if (w==q){ p=true;
  221. output_path(w,first);break;
  222. }
  223. }
  224. w=nextAdj(G,v,w);
  225.    }
  226. }
  227. }
  228. if (!p&&v!=q)
  229. cout<<"NO PATH"<<"   "<<"steps "<<m;
  230. for(int i=1;i<=n;i++)  visited[i]=false;
  231. }
  232. void LGraph::output_path(int w,int first)
  233. {int s=0;   int k=0
  234. ;
  235. while(w!=first){
  236.   for( s=1;s<=n;s++)
  237.   if(Tag[s][w]==true&&w>s) 
  238.   { cout<<w<<"<-  ";k++;
  239.   w=s;
  240.   }
  241. }
  242. cout<<first<<endl;
  243. cout<<"steps "<<k<<endl;
  244. }
  245. void LGraph::creat_tree(fnode * & T,int v)
  246. { int i=1;int p=0;int q=0;
  247. T=new fnode (v,NULL,NULL);  
  248. if (T->data==1)   W=T;
  249. for(int k=0;i<=n;i++)
  250. {  
  251. if(Tag[v][i]==true) 
  252. {  if(k==0){
  253. k++;
  254.    creat_tree(T->firstson,i);
  255. }
  256. else{ 
  257. fnode * Y=new fnode ();
  258. Y=T;
  259. if(T->firstson!=NULL) T=T->firstson;
  260. while(T->nextbrother!=NULL)  T=T->nextbrother;
  261.    creat_tree(T->nextbrother,i);
  262.    T=Y;
  263. }
  264. }
  265.   
  266. }
  267. }
  268. void LGraph::BFS_creat_tree()
  269. {Forest F; 
  270. creat_tree(F.root,1);
  271. cout<<"先序输出广度遍历生成树:"<<endl;
  272. if (F.root==NULL) cout<<"NULL"<<endl;
  273. preorder(W);
  274. }
  275. void LGraph::DFS_creat_tree()
  276. {Forest F; 
  277. creat_tree(F.root,1);
  278. cout<<"先序输出深度遍历生成树:"<<endl;
  279. if (F.root==NULL) cout<<"NULL"<<endl;
  280. preorder(W);
  281. }
  282. void LGraph::preorder(fnode * &T)
  283. {
  284. if(T!=NULL){
  285. cout<<T->data<<"        ";
  286. preorder(T->firstson);
  287. preorder(T->nextbrother);
  288. }
  289. }
  290. int LGraph::bainshu()
  291. {
  292. return e;
  293. }
  294. void LGraph::panduan_tree(LGraph &G)
  295. {
  296. int i=0;
  297. BFS_travel(G);
  298. for(int i=1;i<=n;i++)
  299. for(int j=1;j<=n;j++)
  300. if(Tag[i][j]==true)  i++;
  301. if(i<e)  cout<<"该图是有向树"<<endl;
  302. else   cout<<"该图不是有向树"<<endl;
  303. }
  304. int main()
  305. LGraph G;
  306. G.creat();
  307. cout<<"第1题"<<endl;
  308. cout<<"图的边数"<<G.bainshu();
  309. cout<<"第2题"<<endl;
  310. G.BFS_solve(G);
  311. cout<<"第3题"<<endl;
  312. G.panduan_tree(G);
  313. cout<<"第4题"<<endl;
  314. G.DFS_creat_tree();
  315. cout<<"第5题"<<endl;
  316. G.BFS_creat_tree();
  317. return 0;
  318. }