非连通图生成树遍历

#include <stdio.h>
#include <malloc.h>
#define LEN sizeof(struct MatrixGraph)
#define TEN sizeof(struct MatrixGraph)
#define VERTEX_MAX 26
#define MAXVALUE 32767
struct MatrixGraph
{
	int Vertex[VERTEX_MAX];                                           //保存顶点信息（序号或字母）
	int Edges[VERTEX_MAX][VERTEX_MAX];                                //保存边的权
	int isTrav[VERTEX_MAX];                                          //遍历标志
	int VertexNum;                                                    //顶点数量
	int EdgeNum;                                                      //边数量
	int GraphType;                                                   //图的类型
};

struct tree
{
	int data;
	struct tree *lchild;
	struct tree *rchild;
};

void CreateMatrixGraph(MatrixGraph *G)
{
	int i,j,k,weight;
	int start,end;
	printf("输入各顶点信息\n");
	for(i=0;i<G->VertexNum;i++)                                       //输入顶点
	{
		printf("\n第%d个顶点",i+1);
		scanf("%d",&G->Vertex[i]);
	}
	printf("输入构成各边的两个顶点及权值\n");
	for(k=0;k<G->EdgeNum;k++)
	{
		printf("第%d条边：",k+1);
		scanf("%d,%d,%d",&start,&end,&weight);
		for(i=0;start!=G->Vertex[i];i++);                             //输入边的信息
			for(j=0;end!=G->Vertex[j];j++);
				G->Edges[i][j]=weight;
				if(G->GraphType==0)                                   //若是无向图
				{
					G->Edges[j][i]=weight;                            //在对角位置保存权值
				}
	}
}

void OutMatrix(MatrixGraph *G)
{
	int i,j;
	for(j=0;j<G->VertexNum;j++)
	{
		printf("\t%d",G->Vertex[j]);                            //在第一行输出顶点信息
	}
	printf("\n");
	for(i=0;i<G->VertexNum;i++)
	{
		printf("%d",G->Vertex[i]);
		for(j=0;j<G->VertexNum;j++)
		{
			if(G->Edges[i][j]==MAXVALUE)                    //若权值为最大值
				printf("\t#");                                      //输出#号
			else
				printf("\t%d",G->Edges[i][j]);
		}
		printf("\n");
	}
}

//先序遍历生成的森林
void BinTree_DLR(tree *bt)
{
	if(bt)
	{
		printf("%d",bt -> data);
		if(bt -> lchild)
		{
			BinTree_DLR(bt -> lchild);
		}
		if(bt -> rchild)
		{
			BinTree_DLR(bt -> rchild);
		}
	}
	return;
}

//深度遍历
void DFSTree(MatrixGraph *G,tree *p, int j)
{
	tree *t;
	G -> isTrav[j] = 1;
	for(int i = 0; i< G -> VertexNum; i++)                     
	{
		if(G -> Edges[j][i] != MAXVALUE&&!G -> isTrav[i]){
			t = (struct tree*)malloc(TEN);
			t -> lchild = NULL;
			t -> rchild = NULL;
			t -> data = G -> Vertex[i];
			p -> rchild = t;
			DFSTree(G,t,i);                                                //递归进行遍历
		}
	}
}
 
//生成森林
void DFSForest(MatrixGraph *G,	tree *root)
{
	int i;
	tree *q,*p;
	for(i = 0; i < G -> VertexNum; i++)
	      G -> isTrav[i] = 0;
	for(i = 0; i < G -> VertexNum; i++){
		if(G -> isTrav[i] == 0){
			p = (struct tree*)malloc(TEN);
			p -> lchild = NULL;
			p -> rchild = NULL;
			p -> data = G -> Vertex[i];
			if(root -> data == MAXVALUE){
				root = p;
			}
			else
				q -> lchild = p;
			q = p;
			DFSTree(G,q,i);
		}
	}
	printf("中序遍历由图生成的树的结果:");
	BinTree_DLR(root);
	printf("\n");
	printf("帝国万岁!");
	printf("\n");
}



void main()
{
	int i,j;
	MatrixGraph G;
	tree root;
	root.data = MAXVALUE;
	s:
	printf("无向图(选1)还是有向图(选2)？");
	scanf("%d",&G.GraphType);
	if(G.GraphType != 1 && G.GraphType != 2){
		printf("输入错误\n");
		goto s;
	}
	printf("输入图的顶点数量和各边数量:");
	scanf("%d,%d",&G.VertexNum,&G.EdgeNum);                         //输入图顶点数和边数
	for(i=0;i<G.VertexNum;i++)
	     for(j=0;j<G.VertexNum;j++)
	          G.Edges[i][j]=MAXVALUE;
		CreateMatrixGraph(&G);
	printf("邻接矩阵数据如下：\n");
	OutMatrix(&G);
	DFSForest(&G,&root);
}