无向图的构建及深度优先遍历

        深度优先遍历(Depth-First Traversal)

        假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。

按照左优先（当然也可以右优先，只是得到的结果不同）的原则遍历的结果应为：a->b->d->h->e->c->f->g

code

/*
	图的构建及其深度优先搜索
*/
#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 30

typedef int VrType;
typedef char VtType;
bool visted[MAX_VERTEX_NUM];		//搜索时的标记矩阵

typedef struct ARC					//用于表征图的连接关系
{
	VrType adj;						//连接关系
	ARC *info;						//附加信息
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct						//定义图的完整结构
{
	VtType vertex[MAX_VERTEX_NUM];	//顶点		
	AdjMatrix arcs;					//邻接矩阵
	int vertexnum,arcnum;			//弧线和顶点的数目
}MGraph;

void CreateG(MGraph &G)				//创建图
{
	int i,j;

	printf("Construct the Graph...\n");
	G.vertexnum=8;
	G.arcnum=9;

	for(i=0;i<MAX_VERTEX_NUM;i++)	//邻接矩阵的初始化
	{
		for(j=0;j<MAX_VERTEX_NUM;j++)
		{
			G.arcs[i][j].adj=0;
			G.arcs[i][j].info=NULL;
		}
	}

	G.vertex[0]=‘a‘;				//顶点赋值
	G.vertex[1]=‘b‘;
	G.vertex[2]=‘c‘;
	G.vertex[3]=‘d‘;
	G.vertex[4]=‘e‘;
	G.vertex[5]=‘f‘;
	G.vertex[6]=‘g‘;
	G.vertex[7]=‘h‘;

	G.arcs[0][1].adj=1;				//邻接矩阵赋值
	G.arcs[0][1].info=NULL;
	G.arcs[1][0].adj=1;
	G.arcs[1][0].info=NULL;

	G.arcs[1][3].adj=1;
	G.arcs[1][3].info=NULL;
	G.arcs[3][1].adj=1;
	G.arcs[3][1].info=NULL;

	G.arcs[3][7].adj=1;
	G.arcs[3][7].info=NULL;
	G.arcs[7][3].adj=1;
	G.arcs[7][3].info=NULL;

	G.arcs[4][7].adj=1;
	G.arcs[4][7].info=NULL;
	G.arcs[7][4].adj=1;
	G.arcs[7][4].info=NULL;

	G.arcs[4][1].adj=1;
	G.arcs[4][1].info=NULL;
	G.arcs[1][4].adj=1;
	G.arcs[1][4].info=NULL;

	G.arcs[0][2].adj=1;
	G.arcs[0][2].info=NULL;
	G.arcs[2][0].adj=1;
	G.arcs[2][0].info=NULL;

	G.arcs[2][5].adj=1;
	G.arcs[2][5].info=NULL;
	G.arcs[5][2].adj=1;
	G.arcs[5][2].info=NULL;

	G.arcs[2][6].adj=1;
	G.arcs[2][6].info=NULL;
	G.arcs[6][2].adj=1;
	G.arcs[6][2].info=NULL;

	G.arcs[5][6].adj=1;
	G.arcs[5][6].info=NULL;
	G.arcs[6][5].adj=1;
	G.arcs[6][5].info=NULL;

	printf("Construction of Graph OK!\n\n");
	return;
}

void ShowAdjMat(MGraph G)			//邻接矩阵的显示
{
	int i,j;

	printf("The adjacent matrix is:\n");
	for(i=0;i<G.vertexnum;i++)
	{
		for(j=0;j<G.vertexnum;j++)
		{
			printf("%d ",G.arcs[i][j].adj);
		}
		printf("\n");
	}
	printf("\n");

	return;
}

int GetNextVertex(MGraph G,int v)	//获取下一顶点
{
	int i;

	for(i=0;i<G.vertexnum;i++)
	{
		if(G.arcs[v][i].adj!=0 && visted[i]!=true)
		{
			return i;
		}
	}

	return -1;
}

void DFS(MGraph G,int v)			//深度优先搜索
{
	int i;
	int nextid;

	printf("%c ",G.vertex[v]);
	visted[v]=true;
	while(1)
	{
		nextid=GetNextVertex(G,v);
		if(nextid!=-1 && visted[nextid]==false)
		{
			DFS(G,nextid);
		}
		else
		{
			break;
		}
	}

}

void DFSTraverse(MGraph G)			//深度优先搜索
{
	int i;

	printf("The depth first traverse result is:\n");
	for(i=0;i<G.vertexnum;i++)
	{
		visted[i]=false;
	}

	for(i=0;i<G.vertexnum;i++)
	{
		if(visted[i]!=true)
		{
			DFS(G,i);
		}
	}
}

int main(void)
{
	MGraph G;

	CreateG(G);
	ShowAdjMat(G);
	DFSTraverse(G);

	printf("\n\n");
	system("pause");
	return 0;
}

无向图的构建及深度优先遍历,布布扣,bubuko.com

无向图的构建及深度优先遍历

原文：http://blog.csdn.net/cjc211322/article/details/21648659