【文件属性】：
文件名称：数据结构中图论相关算法
文件大小：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<<"}"<
【文件预览】：
graph
----graph.dsw(533B)
----graph.dsp(4KB)
----graph.h(21KB)
----Debug()
--------graph.pdb(481KB)
--------vc60.pdb(60KB)
--------graph.exe(216KB)
--------main.obj(54KB)
----graph.ncb(49KB)
----graph.opt(53KB)
----main.cpp(4KB)
----graph.plg(1KB)
