数据结构中图论相关算法

【文件属性】：
文件名称：数据结构中图论相关算法
文件大小：163KB
文件格式：RAR
更新时间：2012-04-02 14:03:30
图论相关算法 其涵盖了数据结构中图章节的大部分算法 #include #include #include #include #include #ifndef ONCE_GRAPH #define ONCE_GRAPH const int MAX_NUM=32767; const int QUEUESIZE=100; struct ArcNode {int adjvex; ArcNode *nextarc; int weight; }; struct VNode {char* pointdata; ArcNode *firstarc; }; struct edge { int u; int v; void swap(const int p,const int n) { int temp; if(p>n) { temp=u; u=u>v?u:v; v=vtemp?v:temp; } } }; class Graph {private: VNode *a; int pointnum; int edgenum; int kind; bool *vision; void BFSpart(int start); void DFSpart(int start); void findindegree(int *array); bool Hamiton(int start,int *&path,int &count); void Criticalpoint_part(int s,int &count,int *vis,int *low); void Thedoubleconnectsweight_part(const int cp,const int parent,edge *const stack,int &top,int &count,int *vis,int *low)const; void Topologicsort_helpCriticalpath(int *array,int &tp,int *earlist); public: Graph(int pointnum,int kind); ~Graph(); void creatGraph(); void DFS(int start); void BFS(int start); bool isConnectedGraph(); void Topologicsort(); void Criticalpoint(int start=1); void Criticalpath(); void Thedoubleconnectsweight(const int start)const; void Minimumandborntree_a(int satrt); void Minimumandborntree_b(); void Theshortestpath_a(int start=1); void Theshortestpath_b(); void Hamitontrack(); }; //************************************************************************************************** Graph::Graph(int pointnum,int kind) { this->pointnum=pointnum; this->kind=kind; a=new VNode[pointnum+1]; vision=new bool[pointnum+1]; for(int i=1;i<=pointnum;i++) { a[i].firstarc=NULL; vision[i]=false; } edgenum=0; } //********************************************************************************** Graph::~Graph() { for(int i=1;i<=pointnum;i++) { ArcNode *p=a[i].firstarc, *q; while(p) { q=p->nextarc; delete p; p=q; } } //**************************** delete []a; delete []vision; //**************************** } //********************************************************************************** void Graph::creatGraph() { cout<<"Attention:"<"<>ps>>pe>>weight; if(ps<=0||ps>pointnum||pe<=0||pe>pointnum||pe==ps||weight<0) break; ArcNode *p=a[pe].firstarc; while(p) { if(p->adjvex==ps) { p->weight=weight; ArcNode *q=a[ps].firstarc; if(kind==1) { while(q) { if(q->adjvex==pe) { q->weight=weight; break; } q=q->nextarc; } } break; } p=p->nextarc; } if(!p) { if(kind==1) { ArcNode *arc1=new ArcNode, *arc2=new ArcNode; arc1->adjvex=pe; arc1->weight=weight; arc2->adjvex=ps; arc2->weight=weight; arc1->nextarc=a[ps].firstarc; a[ps].firstarc=arc1; arc2->nextarc=a[pe].firstarc; a[pe].firstarc=arc2; } else { ArcNode *arc1=new ArcNode; arc1->adjvex=pe; arc1->weight=weight; arc1->nextarc=a[ps].firstarc; a[ps].firstarc=arc1; } edgenum++; } //cout<adjvex]) { DFSpart(p->adjvex); } p=p->nextarc; } } //********************************************************************************** void Graph::BFSpart(int start=1) { //cout<<"get into BFSpart!"<adjvex]) queue[rear++]=p->adjvex; p=p->nextarc; } front++; } } //********************************************************************************** void Graph::BFS(int start=1) { int i; for(i=1;i<=pointnum;i++) { vision[i]=false; } BFSpart(start); //cout<<"get into BFS!"<adjvex]++; //cout<<"in while!"<nextarc; } //cout<<"in for!"<>j; } } //************************** ******************************************************** void Graph::Topologicsort() { //int pointnum=this->pointnum; if(kind==1) { cout<<"Just directed graph can be engaged in Topologicsort!"<=0) { cout<adjvex]) { stack[++top]=temp->adjvex; //array[num++]=temp->adjvex; } temp=temp->nextarc; } } cout<<");"<adjvex].weight=temp->weight; temp=temp->nextarc; } int j=1; while(true) { j=1; for(;j<=pointnum&&vision[j];j++); min=j; j++; for (;j<=pointnum&&!vision[j];j++) if(choos[min].weight>choos[j].weight&&!vision[j]) min=j; if (min>pointnum) return; vision[min]=true; cout<<"("<weightadjvex].weight&&!vision[temp->adjvex]) { choos[temp->adjvex].startpoint=min; choos[temp->adjvex].weight=temp->weight; } temp=temp->nextarc; } } //***************** delete []choos; //***************** } //********************************************************************************** void Graph::Minimumandborntree_b() { //*******************************据邻接表求边集数组************************************* struct edgepoint { int start; int end; int weight; }; edgepoint *edge=new edgepoint[edgenum+1];//new! for(int i=1;i<=edgenum;i++) edge[i].weight=-1; int count=1; if(kind==1) { for(int j=1;j<=pointnum;j++) for(ArcNode *temp=a[j].firstarc;temp;temp=temp->nextarc) if (temp->adjvex<=j); else { edge[count].start=j; edge[count].end=temp->adjvex; edge[count].weight=temp->weight; count++; } } else { for(int j=1;j<=pointnum;j++) for(ArcNode *temp=a[j].firstarc;temp;temp=temp->nextarc) { edge[count].start=j; edge[count].end=temp->adjvex; edge[count].weight=temp->weight; count++; } } //cout<<"edge end!"<edge[j].weight&&!vis[j]) min=j; //cout<<"min is "<adjvex].weight=temp->weight; temp=temp->nextarc; } while(true) { int j, min=-1; for(j=1;j<=pointnum&&vision[j];j++); if(j<=pointnum) { min=j++; for(;j<=pointnum;j++) if(we[min].weight>we[j].weight&&!vision[j]) min=j; vision[min]=true; path[min]=we[min].currentpoint; temp=a[min].firstarc; while(temp) { if(!vision[temp->adjvex]) { if((we[min].weight+temp->weight)adjvex].weight) { we[temp->adjvex].weight=we[min].weight+temp->weight; we[temp->adjvex].currentpoint=min; } } temp=temp->nextarc; } } else break; } int *stack=new int[pointnum],//new! top=-1; for(int u=1;u<=pointnum;u++) { if(u!=start) { int up=u; while(up!=-1) { stack[++top]=up; up=path[up]; } } if(top!=-1) { cout<adjvex]=j; d[j][temp->adjvex]=temp->weight; temp=temp->nextarc; } } for(int p=1;p<=pointnum;p++) for(int q=1;q<=pointnum;q++) for(int e=1;e<=pointnum;e++) { if(d[p][e]+d[e][q]s) { //cin>>p; cout<<"The shortest path from "<adjvex]) if(Hamiton(temp->adjvex,path,count)) return true; if(vision[temp->adjvex]&&temp->adjvex==path[0]&&count==(pointnum-1)) return true; temp=temp->nextarc; } vision[start]=false; count--; //cout<<"in Hamiton end"<>start; if(start<1||start>pointnum) cout<<"Illegal point!"<>>"; cout<>>"; cout.flush(); //**************************** delete []path; //**************************** } //********************************************************************************** bool Graph::isConnectedGraph() { int *coll=new int[pointnum+1];//new! ArcNode *temp; for(int i=1;i<=pointnum;i++) coll[i]=-1; if(kind==1) for(int j=1;j<=pointnum;j++) { temp=a[j].firstarc; while(temp) { if(jadjvex) { coll[temp->adjvex]=j; } temp=temp->nextarc; } } else { delete []coll; return false; } for(int m=1;m<=pointnum;m++) for(int n=coll[m],t=m;n!=-1;t=n,n=coll[n]) if(coll[n]!=-1) coll[t]=coll[n]; int ancestor, t=1; while(coll[t]!=-1) t=coll[t]; ancestor=t; for(int e=2;e<=pointnum;e++) { t=e; while (coll[t]!=-1) t=coll[t]; if(ancestor!=t) return false; } delete []coll; return true; } //********************************************************************************** void Graph::Criticalpoint(int start) { int *vis=new int[pointnum+1], *low=new int[pointnum+1], count=0; for(int i=1;i<=pointnum;i++) vis[i]=0; cout<<"Critical point below:"<adjvex]) Criticalpoint_part(temp->adjvex,count,vis,low); temp=temp->nextarc; } } cout<adjvex]) { //cout<<"kkkif"<adjvex,count,vis,low); if(low[temp->adjvex]adjvex]; if(low[temp->adjvex]>=vis[s]) cout<<" "<adjvex]adjvex]; //cout<<"kkk else if"<nextarc; } low[s]=min; } //********************************************************************************** void Graph::Thedoubleconnectsweight_part(const int cp,const int parent,edge *const stack,int &top,int &count,int *vis,int *low)const { int min; edge e; min=vis[cp]=++count; ArcNode *temp=a[cp].firstarc; while(temp) { if(temp->adjvex!=parent&&vis[temp->adjvex]adjvex; stack[++top]=e; } if(!vis[temp->adjvex]) { Thedoubleconnectsweight_part(temp->adjvex,cp,stack,top,count,vis,low); if(low[temp->adjvex]>=vis[cp]) { cout<<"{"; do { e=stack[top--]; e.swap(cp,temp->adjvex); cout<<"("<adjvex); cout<<"}"<low[temp->adjvex]) min=low[temp->adjvex]; } else if(vis[temp->adjvex]adjvex]; temp=temp->nextarc; } low[cp]=min; } //********************************************************************************** void Graph::Thedoubleconnectsweight(const int start)const { if(start<1||start>pointnum) return; int *vis=new int[pointnum+1], *low=new int[pointnum+1], count=0, top=-1; edge *stack=new edge[edgenum]; for(int i=1;i<=pointnum;i++) vis[i]=0; Thedoubleconnectsweight_part(start,-1,stack,top,count,vis,low); //************************* delete []vis; delete []low; delete []stack; //************************* } //********************************************************************************** void Graph::Topologicsort_helpCriticalpath(int *array,int &tp,int *earlist) { tp=-1; //int pointnum=this->pointnum; if(kind==1) { cout<<"Just directed graph can be engaged in Topologicsort!"<=0) { array[++tp]=stack[top]; int topc; temp=a[topc=stack[top--]].firstarc; //cout<<"in while --!"<adjvex]) { stack[++top]=temp->adjvex; //array[num++]=temp->adjvex; } //cout<<"end if!"<adjvex]weight) earlist[temp->adjvex]=earlist[topc]+temp->weight; //cout<<"end if if!"<nextarc; } } //**************************** delete []indegree; delete []stack; //**************************** } //********************************************************************************** void Graph::Criticalpath() { int *stack=new int[pointnum+1], *earliest=new int[pointnum+1], *lastest=new int[pointnum+1], top=-1; Topologicsort_helpCriticalpath(stack,top,earliest); //cout<<"end Topologicsort_helpCriticalpath"<=0) for(ArcNode *temp=a[stack[top--]].firstarc;temp;temp=temp->nextarc) if(lastest[temp->adjvex]>lastest[stack[top+1]]-temp->weight) lastest[temp->adjvex]=lastest[stack[top+1]]-temp->weight; for(int t=1;t<=pointnum;t++) { cout<nextarc) if(earliest[m]==(lastest[tp->adjvex]-tp->weight)) cout<<"("<adjvex<<") "; cout<<"}"<