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();
*/
}
我以前写的 不是很好 你自己看看