Code/Resource
Windows Develop
Linux-Unix program
Internet-Socket-Network
Web Server
Browser Client
Ftp Server
Ftp Client
Browser Plugins
Proxy Server
Email Server
Email Client
WEB Mail
Firewall-Security
Telnet Server
Telnet Client
ICQ-IM-Chat
Search Engine
Sniffer Package capture
Remote Control
xml-soap-webservice
P2P
WEB(ASP,PHP,...)
TCP/IP Stack
SNMP
Grid Computing
SilverLight
DNS
Cluster Service
Network Security
Communication-Mobile
Game Program
Editor
Multimedia program
Graph program
Compiler program
Compress-Decompress algrithms
Crypt_Decrypt algrithms
Mathimatics-Numerical algorithms
MultiLanguage
Disk/Storage
Java Develop
assembly language
Applications
Other systems
Database system
Embeded-SCM Develop
FlashMX/Flex
source in ebook
Delphi VCL
OS Develop
MiddleWare
MPI
MacOS develop
LabView
ELanguage
Software/Tools
E-Books
Artical/Document
LGraph.cpp
Package: 7.rar [view]
Upload User: lsjld999
Upload Date: 2022-06-19
Package Size: 980k
Code Size: 6k
Category:
Graph program
Development Platform:
Visual C++
- #include "iostream"
- #include "Queue.h"
- #include "Forest.h"
- using namespace std;
- enum error_code {Failure,success,NotPresent,Duplicate};
- struct gnode
- {
- gnode (){nextArc=NULL;}
- gnode (int vertex,int weight,gnode * next)
- {adjVex=vertex; w=weight;nextArc=next;}
- int adjVex;
- int w;
- gnode* nextArc;
- };
- class LGraph
- {
- public :
- int bainshu();//求图的边数
- void panduan_tree(LGraph &G);//判断是否为有向树
- void DFS_creat_tree();//深度遍历生成树
- void preorder(fnode * &T);
- void output_layer();//输出各个节点的值及层次数
- void BFS_creat_tree();//广度遍历生成树
- void creat_tree(fnode * & T,int v);//遍历生成树
- void output_path(int w,int first);//输出路径
- void BFS_solve(LGraph &G);
- void BFS_solve(LGraph &G, int v,int q);//求解给定顶点到某一顶点的路径
- void creat();//创建图
- LGraph(){n=0; e=0;};//构造函数
- LGraph(int mSize);//构造函数
- error_code Insert (int u,int v,int w);//插入边
- error_code Remove (int u,int v);//删除边
- bool Exist(int u,int v);//判断边是否存在
- int firstAdj(LGraph G,int v);//求第一个元素
- int nextAdj(LGraph G,int v,int w);//求元素在W 后的元素
- void DFS(LGraph & G,int v);//深度遍历
- void DFS_travel(LGraph &G);//深度遍历图
- void BFS(LGraph & G,int v);//广度遍历
- void BFS_travel(LGraph &G);// 广度遍历图
- protected:
- gnode ** a;//节点数组
- int n;
- int e;queue<fnode *> Q;
- bool visited[50];
- bool Tag[20][20];fnode * W;
- };
- LGraph::LGraph(int mSize)
- {
- n=mSize; e=0;
- a=new gnode *[n];
- for(int i=1;i<=n;i++)
- a[i]=NULL;
- }
- bool LGraph::Exist(int u, int v)
- {
- if(u==1||v==1||u>n||v>n)
- return false ;
- gnode *p=a[u];
- while (p&&p->adjVex!=v)
- p=p->nextArc;
- if(!p)return false;
- else return true;
- }
- error_code LGraph::Insert(int u, int v, int w)
- {
- if (u<1||v<1||u>n||v>n||u==v) return Failure;
- if(Exist(u,v))
- return Duplicate;
- gnode *p=new gnode (v,w,a[u]);
- a[u]=p;e++;
- return success;
- }
- error_code LGraph::Remove (int u,int v)
- {
- if(u<1||v<1||u>n||v>n) return Failure;
- gnode *p=a[u];gnode *q=NULL;
- while (p&&p->adjVex!=v)
- {q=p; p=p->nextArc;}
- if(!p) return NotPresent;
- if (q) q->nextArc=p->nextArc;
- else a[u]=p->nextArc;
- delete p;
- e--;
- return success;
- }
- void LGraph::creat()
- {int m;
- cout<<"请输入节点总数 "<<endl;
- cin>>m;
- n =m;
- e=0;
- a=new gnode *[n];
- for(int j=1;j<=n;j++)
- a[j]=NULL;
- for(int i=1;i<=n;i++)
- {int w=0;
- cout<<"与 "<<i<<"相关的点 "<<endl;
- int x;
- while (cin>>x)
- Insert(i,x,w);
- cin.clear();
- }
- }
- int LGraph::firstAdj(LGraph G,int v)
- {
- if (v>=1&&v<=n) return a[v]->adjVex;
- else return 0;
- }
- int LGraph::nextAdj(LGraph G,int v,int w)
- {if (v>=1&&v<=n)
- {
- gnode *q=a[v];
- while (q->adjVex!=w) q=q->nextArc;
- {if (q->nextArc!=NULL)
- return q->nextArc->adjVex;
- else return 0;
- }
- }
- else return 0;
- }
- void LGraph::DFS(LGraph & G,int v)
- {
- int w;
- cout<<v<<" "; visited[v]=true;
- w=firstAdj(G,v);
- while (w!=0)
- {
- if(visited[w]==false){Tag[v][w]=true;
- DFS(G,w);
- }
- w=nextAdj(G,v,w);
- }
- }
- void LGraph::DFS_travel(LGraph &G)
- {
- int i;
- for(i=1;i<=n;i++)
- visited[i]=false;
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- Tag[i][j]=false;
- cout<<"深度遍历图"<<endl;
- for(i=1;i<=n;i++)
- if(visited[i]==false)
- DFS(G,i);
- cout<<endl;
- }
- void LGraph::BFS(LGraph &G, int v)
- {
- int w;
- queue<int> Q;
- cout<<v<<" ";
- visited[v]=true;
- Q.append(v);
- while (!Q.empty())
- {
- v=Q.serve();
- w=firstAdj(G,v);
- while (w!=0)
- {
- if (!visited[w])
- {
- cout<<w;Tag[v][w]=true;
- visited[w]=true;
- Q.append(w);}
- w=nextAdj(G,v,w);
- }
- }
- }
- void LGraph::BFS_travel(LGraph & G)
- {
- int i;
- for(i=1;i<=n;i++)
- visited[i]=false;
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- Tag[i][j]=false;
- cout<<"广度遍历图"<<endl;
- for(i=1;i<=n;i++)
- if(visited[i]==false)
- BFS(G,i);
- cout<<endl;
- }
- void LGraph::BFS_solve(LGraph & G)
- {int a;
- for(int k=1;k<=n;k++)
- visited[k]=false;
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- Tag[i][j]=false;
- cout<<"请输入出发顶点 "<<endl;
- cin>>a;
- for(int b=1;b<=n;b++){
- cout<<"从顶点 "<<a<<"到顶点"<<b<<"的最短路径"<<endl;
- BFS_solve(G, a, b);
- cout<<endl;
- }
- }
- void LGraph::BFS_solve(LGraph & G,int v,int q)
- {
- int m=0; bool p=false;
- int w; int first=v;
- queue<int> Q;
- visited[v]=true;
- Q.append(v);
- if (v==q) cout<<"NO PATH"<<" "<<"steps "<<m;
- else
- {
- while(!Q.empty())
- {
- v=Q.serve();
- w=firstAdj(G,v);
- while (w!=0)
- {
- if (!visited[w])
- {
- visited[w]=true;
- Q.append(w);
- Tag[v][w]=true;
- if (w==q){ p=true;
- output_path(w,first);break;
- }
- }
- w=nextAdj(G,v,w);
- }
- }
- }
- if (!p&&v!=q)
- cout<<"NO PATH"<<" "<<"steps "<<m;
- for(int i=1;i<=n;i++) visited[i]=false;
- }
- void LGraph::output_path(int w,int first)
- {int s=0; int k=0
- ;
- while(w!=first){
- for( s=1;s<=n;s++)
- if(Tag[s][w]==true&&w>s)
- { cout<<w<<"<- ";k++;
- w=s;
- }
- }
- cout<<first<<endl;
- cout<<"steps "<<k<<endl;
- }
- void LGraph::creat_tree(fnode * & T,int v)
- { int i=1;int p=0;int q=0;
- T=new fnode (v,NULL,NULL);
- if (T->data==1) W=T;
- for(int k=0;i<=n;i++)
- {
- if(Tag[v][i]==true)
- { if(k==0){
- k++;
- creat_tree(T->firstson,i);
- }
- else{
- fnode * Y=new fnode ();
- Y=T;
- if(T->firstson!=NULL) T=T->firstson;
- while(T->nextbrother!=NULL) T=T->nextbrother;
- creat_tree(T->nextbrother,i);
- T=Y;
- }
- }
- }
- }
- void LGraph::BFS_creat_tree()
- {Forest F;
- creat_tree(F.root,1);
- cout<<"先序输出广度遍历生成树:"<<endl;
- if (F.root==NULL) cout<<"NULL"<<endl;
- preorder(W);
- }
- void LGraph::DFS_creat_tree()
- {Forest F;
- creat_tree(F.root,1);
- cout<<"先序输出深度遍历生成树:"<<endl;
- if (F.root==NULL) cout<<"NULL"<<endl;
- preorder(W);
- }
- void LGraph::preorder(fnode * &T)
- {
- if(T!=NULL){
- cout<<T->data<<" ";
- preorder(T->firstson);
- preorder(T->nextbrother);
- }
- }
- int LGraph::bainshu()
- {
- return e;
- }
- void LGraph::panduan_tree(LGraph &G)
- {
- int i=0;
- BFS_travel(G);
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- if(Tag[i][j]==true) i++;
- if(i<e) cout<<"该图是有向树"<<endl;
- else cout<<"该图不是有向树"<<endl;
- }
- int main()
- {
- LGraph G;
- G.creat();
- cout<<"第1题"<<endl;
- cout<<"图的边数"<<G.bainshu();
- cout<<"第2题"<<endl;
- G.BFS_solve(G);
- cout<<"第3题"<<endl;
- G.panduan_tree(G);
- cout<<"第4题"<<endl;
- G.DFS_creat_tree();
- cout<<"第5题"<<endl;
- G.BFS_creat_tree();
- return 0;
- }