7-2-1.txt

数据结构源程序

/*图的基本运算与实现*/
#include <stdio.h>
#define MaxVertexNum 10
typedef int VertexType;
typedef int EdgeType;
typedef struct /*邻接矩阵存储的图结构*/
{
	VertexType vexs[MaxVertexNum];
	EdgeType edges[MaxVertexNum][MaxVertexNum];
	int n,e;
} Mgragh;
typedef struct node/*邻接表存储的图结构*/
{
	int adjvex;
	struct node *next;
}EdgeNode;
typedef struct vnode
{
	VertexType vertex;
	EdgeNode *firstedge;
}VertexNode;
typedef VertexNode Adjlist[MaxVertexNum];
typedef struct
{
	Adjlist adjlist;
	int n,e;
} ALGragh;

void menu();
void init_Mgragh(Mgragh *G);
void CreateMGragh(Mgragh *G);
void CreateALGragh(ALGragh *G);
void DFSTraverseM(Mgragh *G);
void DFSM(Mgragh *G,int i,int *visited);
void BFSTraverseM(Mgragh *G);
void BFSM(Mgragh *G,int i,int *visited);
void DFSTraverseAL(ALGragh *G);
void DFSAL(ALGragh *G,int i,int *visited);
void BFSTraverseAL(ALGragh *G);
void BFSAL(ALGragh *G,int i,int *visited);

main()
{
	int n,m=1;
	Mgragh G;
	ALGragh ALG;
	/*clrscr();*/
	while(m)
	{
		menu();
		scanf("%d",&n);
		switch(n)
		{
			case 1:{/*邻接矩阵建立图*/
				init_Mgragh(&G);
				CreateMGragh(&G);
				break;
				}
			case 2:{/*邻接表建立图*/
				CreateALGragh(&ALG);
				break;
				}
			case 3:{/*邻接矩阵深度优先搜索*/
				DFSTraverseM(&G);
				break;
				}
			case 4:{/*邻接矩阵广度优先搜索*/
				
				break;
				}
			case 5:{/*邻接表深度优先搜索*/
				DFSTraverseAL(&ALG);
				break;
				}
			case 6:{/*邻接表广度优先搜索*/
				
				break;
				}
			case 0:m=0;
		}
	}
}
void menu()
{
	/*clrscr();*/
	printf("\n");
	printf("\t\t1.Create MGraph\n\n");
	printf("\t\t2.Create ALGraph\n\n");
	printf("\t\t3.DFST M\n\n");
	printf("\t\t4.BFAT M\n\n");
	printf("\t\t5.DFST AL\n\n");
	printf("\t\t6.BFAT AL\n\n");
	printf("\t\t0.exit\n\n");
	printf("\n\n\n\tplease select:");
	return;
}
void init_Mgragh(Mgragh *G)
{
	int i,j;
	for(i=0;i<MaxVertexNum;i++)
	{
		G->vexs[i]=-1;
	}
	for(i=0;i<MaxVertexNum;i++)
	{
		for(j=0;j<MaxVertexNum;j++)
		{
			G->edges[i][j]=-32767;
		}
	}
	return;
}
void CreateMGragh(Mgragh *G)
{
	int i,j,k,m;
	printf("Please Input vexs and edges(format:vex,edge):\n");
	scanf("%d,%d",&(G->n),&(G->e));
	printf("Please Input information of vexs:\n");
	for(i=0;i<G->n;i++)
	{
		scanf("%d",&(G->vexs[i]));
	}
	printf("Please Input the serial NO. of two vexs and their information of edge:\n");
	for(k=0;k<G->e;k++)
	{
		scanf("%d,%d",&i,&j);
		scanf("%d",&m);
		G->edges[i][j]=m;
		G->edges[j][i]=m;
	}
	return;
}
void CreateALGragh(ALGragh *G)
{
	int i,j,k,m;
	EdgeNode *s;
	printf("Please Input vexs and edges(format:vex,edge):\n");
	scanf("%d,%d",&(G->n),&(G->e));
	printf("Please Input information of vexs:\n");
	for(i=0;i<G->n;i++)
	{
		scanf("%d",&m);
		G->adjlist[i].vertex=m;
		G->adjlist[i].firstedge=NULL;
	}
	printf("Please Input the serial NO. of two vexs about edge:\n");
	for(k=0;k<2*(G->e);k++)
	{
		scanf("%d,%d",&i,&j);
		s=(EdgeNode*)malloc(sizeof(EdgeNode));
		s->adjvex=j;
		s->next=G->adjlist[i].firstedge;
		G->adjlist[i].firstedge=s;
	}
	return;
}
void DFSTraverseM(Mgragh *G)
{
	int i,visited[MaxVertexNum];
	for(i=0;i<G->n;i++)
	{
		visited[i]=0;
	}
	for(i=0;i<G->n;i++)
	{
		if(visited[i]==0)
		{
			DFSM(G,i,visited);
		}
	}
	return;
}
void DFSM(Mgragh *G,int i,int *visited)
{
	int m,n;
	printf("%5d",G->vexs[i]);
	visited[i]=1;
	for(m=i;m<G->n;m++)
	{
		for(n=0;n<G->n;n++)
		{
			if((visited[n]==0)&&(G->edges[m][n]!=-32767))
			{
				DFSM(G,n,visited);
			} /* end if */
		} /* end for n */
	} /* end for m */
	return;	
}
void BFSTraverseM(Mgragh *G)
{
}
void BFSM(Mgragh *G,int i,int *visited)
{
}
void DFSTraverseAL(ALGragh *G)
{
	int i,visited[MaxVertexNum];
	for(i=0;i<G->n;i++)
	{
		visited[i]=0;
	}
	for(i=0;i<G->n;i++)
	{
		if(visited[i]==0)
		{
			DFSAL(G,i,visited);
		}
	}
	return;
}
void DFSAL(ALGragh *G,int i,int *visited)
{
	EdgeNode *p;
	printf("%5d",G->adjlist[i].vertex);
	visited[i]=1;
	p=G->adjlist[i].firstedge;
	while(p)
	{
		if(visited[p->adjvex]==0)
		{
			DFSAL(G,p->adjvex,visited);
		}
		p=p->next;
	} /* end while */
}
void BFSTraverseAL(ALGragh *G)
{
}
void BFSAL(ALGragh *G,int i,int *visited)
{
}