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

要求：
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();
	*/
 

}

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