그림 의 깊이 없 이 우선 옮 겨 다 니 기 (인접 행렬)

1691 단어 데이터 구조

#include
#include
#define INFINTY 65535 //   
#define MAX  20  //      
#define OK 1
#define ERROR 0
#define FALSE 0
#define TRUE 1
typedef int status;
typedef int EdgeType;// 
typedef char VertexType;//   
//typedef enum{DG,DN,UDG,UDN}GraphKind;//   ,   ,   ,   
typedef struct
{
	VertexType vexs[MAX];//  
	EdgeType  arcs[MAX][MAX];  //    
	int vexnum,arcnum; //          
//	GraphKind kind;  //    
}MGraph;
status LocateVex(MGraph *G,VertexType e)
{
	int i;
	for(i=0;ivexnum;++i)
	{
		if(e==G->vexs[i])
			return i;
	}
	return -1;
}
status CreatUDG(MGraph *G)//   
{
	scanf("%d %d",&G->vexnum,&G->arcnum);getchar();
	int i,j,k;
	VertexType v1,v2;
	i=0;
	while(ivexnum)
	{
		scanf("%c",&G->vexs[i]);
		i++;
	}
	getchar();
	for(i=0;ivexnum;i++)//      
		for(j=0;jvexnum;j++)
			G->arcs[i][j]=INFINTY;
	for(k=0;karcnum;k++)
	{
		scanf("%c,%c",&v1,&v2);//          
		getchar();
		i=LocateVex(G,v1);
		j=LocateVex(G,v2);
		G->arcs[j][i]=1;
		G->arcs[i][j]=G->arcs[j][i];
	}
	return OK;
}
int visited[MAX];
void DFS(MGraph *G,int v)
{
	int j;
	visited[v]=TRUE;
	printf("%c ",G->vexs[v]);
	for(j=0;jvexnum;j++)
		if(G->arcs[v][j]==1&&!visited[j])
			DFS(G,j);
}
void DFSTraverse(MGraph *G)
{
	int v;
	for(v=0;vvexnum;++v)
		visited[v]=FALSE;
	for(v=0;vvexnum;++v)
		if(!visited[v])
			DFS(G,v);
}
void main()
{
	MGraph *G=NULL;
	G=(MGraph *)malloc(sizeof(MGraph));
	CreatUDG(G);
	DFSTraverse(G);
}                                 
                          

좋은 웹페이지 즐겨찾기