图的遍历和生成树的求解实现

时间:2022-03-08 12:47:57
要求:
1) 先任意创建一个图;
2) 图的DFS,BFS的递归和非递归算法的实现
3) 最小生成树(两个算法)的实现,求连通分量的实现
4) 要求用邻接矩阵存储实现

本人刚刚学习C语言,想求各位高手能给个比较好的实例!!

2 个解决方案

#1


数据结构好好看一下,大都有现成的算法啊

#2



#include"iostream"
using namespace std;

#define   MAX   999999 


class Graph             //图类
{
public:
void Show();        //显示输出图的顶点,边(无向图的边只输出一次)
void Kruskal();     //克鲁斯卡尔算法
void Prim() ;       //普利姆算法,从第一个字母开始
Graph(int m,int n); //构造函数
int vexnum,edgenum; //顶点数,边数
char *array;        //顶点数组
int **array2;       //边邻接矩阵,0表示没有联通,其他数值表示边的权值
};

int find(int Vex[],int x); //克鲁斯卡尔算法辅助函数



Graph::Graph(int m,int n)
{
vexnum=m;
    edgenum=n;
array=new char[m];
array2=new  int*[n];   
for(int i=0;i<n;i++)   
      array2[i]=new int[n];   
}

void Graph::Show()
{
int i,j;
cout<<"图的顶点如下"<<endl;
for(i=0;i<vexnum;i++)
cout<<array[i]<<"\t";
cout<<endl;
cout<<"图的边如下"<<endl;
for(i=0;i<vexnum;i++)
for(j=i;j<vexnum;j++)
if(array2[i][j]>=1)
cout<<"("<<array[i]<<","<<array[j]<<")"<<endl;
    cout<<"邻接矩阵如下"<<endl;
for(i=0;i<vexnum;i++)
{
for(j=0;j<vexnum;j++)
cout<<array2[i][j]<<" ";
cout<<endl;
}
}


void  Graph::Prim()   
{
int   i,j,k,min; 
int   *lowcost,*closest; 
lowcost=new int[vexnum];
closest=new int[vexnum];
   
for(i=0;i<vexnum;i++)   
    {   
lowcost[i]=array2[0][i];  /*起始点u到V-U集合中各顶点的权存放在lowcost[]中*/  
closest[i]=0;             /*将从U的各顶点里到达V-U中各顶点权最小的顶点*/   
     } 

lowcost[0]=-1;

for(i=1;i<vexnum;i++)   

min=MAX;   
for(j=0;j<vexnum;j++)    
if(lowcost[j]!=0&&lowcost[j]!=-1&&lowcost[j]<min)   
{   
min=lowcost[j];   
k=j;   
}
cout<<"("<<array[closest[k]]<<","<<array[k]<<")"  <<"权值为"<<min<<endl;
lowcost[k]=-1;             /*将该顶点放入U中,即将lowcost[k]设置为-1*/   
for(j=0;j<vexnum;j++)      /*U中加入k后,更新lowcost[],重新登记最小权*/   
if(array2[k][j]!=0&&lowcost[j]!=-1)   
{  
if(lowcost[j]==0||array2[k][j]<lowcost[j])
lowcost[j]=array2[k][j]; /*把从U到V-U中各点权最小的边的权记录下来*/
closest[j]=k;            /*将到j距离最短距离的顶点更新为k*/   
}   

}   
}   



void Graph::Kruskal()
{
int i,j,m=0,n=0,t,h,**array3,*Vex,head,tail;

Vex=new int[vexnum];

for(i=0;i<vexnum;i++)
Vex[i]=0;

array3=new  int*[vexnum];   
for(i=0;i<vexnum;i++)   
      array3[i]=new int[vexnum];

for(i=0;i<vexnum;i++)
for(j=0;j<vexnum;j++)
array3[i][j]=array2[i][j];

for(h=0;h<vexnum-1;h++)
{
t=MAX;
do{
for(i=0;i<vexnum;i++)
for(j=i;j<vexnum;j++)
{
if(array3[i][j]>0)
{
if(array3[i][j]<=t)
{

t=array3[i][j];
m=i;
n=j;
}
}
}

head=find(Vex,m);
tail=find(Vex,n);
array3[m][n]=0;
}
while(head==tail);
if(head!=tail)
{
Vex[head]=tail;
cout<<"("<<array[m]<<","<<array[n]<<")"<<"权值为"<<t<<endl;
}

}
}

int find(int Vex[],int x)
{
while(Vex[x]>0)
x=Vex[x];
return x;
}


void main()
{

int i,j;

Graph A(5,6);
for(i=0;i<5;i++)
A.array[i]='A'+i;
for(i=0;i<5;i++)
for(j=0;j<5;j++)
A.array2[i][j]=0;
A.array2[0][1]=2;
A.array2[0][3]=6;
A.array2[1][0]=2;
A.array2[1][2]=4;
A.array2[1][4]=1;
A.array2[2][1]=4;
A.array2[2][3]=2;
  A.array2[2][4]=3;
A.array2[3][0]=6;
    A.array2[3][2]=2;
A.array2[4][1]=1;
A.array2[4][2]=3;
A.Show();
cout<<"the show of Prim"<<endl;
A.Prim();
cout<<"the show of Kruskal"<<endl;
A.Kruskal();
cout<<endl;



/*
    Graph B(6,10);
for(i=0;i<6;i++)
B.array[i]='A'+i;
for(i=0;i<10;i++)
for(j=0;j<10;j++)
B.array2[i][j]=0;
B.array2[0][1]=6;
B.array2[0][2]=1;
B.array2[0][3]=5;
B.array2[1][0]=6;
B.array2[1][2]=5;
B.array2[1][4]=3;
B.array2[2][0]=1;
B.array2[2][1]=5;
B.array2[2][3]=5;
B.array2[2][4]=6;
B.array2[2][5]=4;
B.array2[3][0]=5;
B.array2[3][2]=5;
B.array2[3][5]=2;
B.array2[4][1]=3;
B.array2[4][2]=6;
B.array2[4][5]=6;
B.array2[5][2]=4;
B.array2[5][3]=2;
B.array2[5][4]=6;
B.Prim();
B.Kruskal();
*/
 

}

我以前写的 不是很好 你自己看看 

#1


数据结构好好看一下,大都有现成的算法啊

#2



#include"iostream"
using namespace std;

#define   MAX   999999 


class Graph             //图类
{
public:
void Show();        //显示输出图的顶点,边(无向图的边只输出一次)
void Kruskal();     //克鲁斯卡尔算法
void Prim() ;       //普利姆算法,从第一个字母开始
Graph(int m,int n); //构造函数
int vexnum,edgenum; //顶点数,边数
char *array;        //顶点数组
int **array2;       //边邻接矩阵,0表示没有联通,其他数值表示边的权值
};

int find(int Vex[],int x); //克鲁斯卡尔算法辅助函数



Graph::Graph(int m,int n)
{
vexnum=m;
    edgenum=n;
array=new char[m];
array2=new  int*[n];   
for(int i=0;i<n;i++)   
      array2[i]=new int[n];   
}

void Graph::Show()
{
int i,j;
cout<<"图的顶点如下"<<endl;
for(i=0;i<vexnum;i++)
cout<<array[i]<<"\t";
cout<<endl;
cout<<"图的边如下"<<endl;
for(i=0;i<vexnum;i++)
for(j=i;j<vexnum;j++)
if(array2[i][j]>=1)
cout<<"("<<array[i]<<","<<array[j]<<")"<<endl;
    cout<<"邻接矩阵如下"<<endl;
for(i=0;i<vexnum;i++)
{
for(j=0;j<vexnum;j++)
cout<<array2[i][j]<<" ";
cout<<endl;
}
}


void  Graph::Prim()   
{
int   i,j,k,min; 
int   *lowcost,*closest; 
lowcost=new int[vexnum];
closest=new int[vexnum];
   
for(i=0;i<vexnum;i++)   
    {   
lowcost[i]=array2[0][i];  /*起始点u到V-U集合中各顶点的权存放在lowcost[]中*/  
closest[i]=0;             /*将从U的各顶点里到达V-U中各顶点权最小的顶点*/   
     } 

lowcost[0]=-1;

for(i=1;i<vexnum;i++)   

min=MAX;   
for(j=0;j<vexnum;j++)    
if(lowcost[j]!=0&&lowcost[j]!=-1&&lowcost[j]<min)   
{   
min=lowcost[j];   
k=j;   
}
cout<<"("<<array[closest[k]]<<","<<array[k]<<")"  <<"权值为"<<min<<endl;
lowcost[k]=-1;             /*将该顶点放入U中,即将lowcost[k]设置为-1*/   
for(j=0;j<vexnum;j++)      /*U中加入k后,更新lowcost[],重新登记最小权*/   
if(array2[k][j]!=0&&lowcost[j]!=-1)   
{  
if(lowcost[j]==0||array2[k][j]<lowcost[j])
lowcost[j]=array2[k][j]; /*把从U到V-U中各点权最小的边的权记录下来*/
closest[j]=k;            /*将到j距离最短距离的顶点更新为k*/   
}   

}   
}   



void Graph::Kruskal()
{
int i,j,m=0,n=0,t,h,**array3,*Vex,head,tail;

Vex=new int[vexnum];

for(i=0;i<vexnum;i++)
Vex[i]=0;

array3=new  int*[vexnum];   
for(i=0;i<vexnum;i++)   
      array3[i]=new int[vexnum];

for(i=0;i<vexnum;i++)
for(j=0;j<vexnum;j++)
array3[i][j]=array2[i][j];

for(h=0;h<vexnum-1;h++)
{
t=MAX;
do{
for(i=0;i<vexnum;i++)
for(j=i;j<vexnum;j++)
{
if(array3[i][j]>0)
{
if(array3[i][j]<=t)
{

t=array3[i][j];
m=i;
n=j;
}
}
}

head=find(Vex,m);
tail=find(Vex,n);
array3[m][n]=0;
}
while(head==tail);
if(head!=tail)
{
Vex[head]=tail;
cout<<"("<<array[m]<<","<<array[n]<<")"<<"权值为"<<t<<endl;
}

}
}

int find(int Vex[],int x)
{
while(Vex[x]>0)
x=Vex[x];
return x;
}


void main()
{

int i,j;

Graph A(5,6);
for(i=0;i<5;i++)
A.array[i]='A'+i;
for(i=0;i<5;i++)
for(j=0;j<5;j++)
A.array2[i][j]=0;
A.array2[0][1]=2;
A.array2[0][3]=6;
A.array2[1][0]=2;
A.array2[1][2]=4;
A.array2[1][4]=1;
A.array2[2][1]=4;
A.array2[2][3]=2;
  A.array2[2][4]=3;
A.array2[3][0]=6;
    A.array2[3][2]=2;
A.array2[4][1]=1;
A.array2[4][2]=3;
A.Show();
cout<<"the show of Prim"<<endl;
A.Prim();
cout<<"the show of Kruskal"<<endl;
A.Kruskal();
cout<<endl;



/*
    Graph B(6,10);
for(i=0;i<6;i++)
B.array[i]='A'+i;
for(i=0;i<10;i++)
for(j=0;j<10;j++)
B.array2[i][j]=0;
B.array2[0][1]=6;
B.array2[0][2]=1;
B.array2[0][3]=5;
B.array2[1][0]=6;
B.array2[1][2]=5;
B.array2[1][4]=3;
B.array2[2][0]=1;
B.array2[2][1]=5;
B.array2[2][3]=5;
B.array2[2][4]=6;
B.array2[2][5]=4;
B.array2[3][0]=5;
B.array2[3][2]=5;
B.array2[3][5]=2;
B.array2[4][1]=3;
B.array2[4][2]=6;
B.array2[4][5]=6;
B.array2[5][2]=4;
B.array2[5][3]=2;
B.array2[5][4]=6;
B.Prim();
B.Kruskal();
*/
 

}

我以前写的 不是很好 你自己看看