现在的位置: 首页 > 综合 > 正文

图的深度优先搜索(邻接表)

2013年06月20日 ⁄ 综合 ⁄ 共 1909字 ⁄ 字号 评论关闭

图的遍历(Traversing Graph)是指从图中某一顶点出发访问图中其余顶点,且使每个顶点仅被访问一次。

深度优先搜索(Depth First Search)

        深度优先搜索假设初始状态下图中所有顶点都未被访问,尝试优先搜索从图中某个顶点v出去,访问此顶点,然后依次从v的未被访问的邻接点出发深度优先遍历图,直到图中所有和v相连连的顶点都被访问到。如果此时图中还有没有访问到的顶点,则另选图中未被访问的某顶点作为起始点,重复上述过程,直到图中所有顶点都被访问到。

采用邻接表存储图的具体实现如下:

#include <cstdio>
#include <cstdlib>

#define VERTEXNUM 100 //顶点个数
typedef char VertexType;
typedef int EdgeType;
typedef enum{FALSE, TRUE} Boolean;
Boolean visited[VERTEXNUM];

/***************************************
 *
 * 邻接表存储结构 
 *
 * *************************************/
typedef struct node
{
	int adjvex; //顶点位置
	struct node *next; //指向下一条边的指针
}EdgeNode;

typedef struct vnode
{
	VertexType vertex; //顶点信息
	EdgeNode *firstedge; //指向第一条依附该顶点的边的指针
}AdjList[VERTEXNUM];

typedef struct
{
	AdjList vertexs; //邻接表
	int vernum, edgenum; //图中当前的顶点和边数
}Graph;

/***************************************
 *
 * 建立图的邻接表
 *
 * *************************************/
void MakeGraph(Graph *graph)
{

	int v1, v2;
	int i, j, k;
	printf("请输入图的顶点数n和边数e:\n");
	scanf("%d%d", &graph->vernum, &graph->edgenum);
	printf("请输入顶点信息(顶点号<CR>)每个顶点以回车作为结束:\n");

	for(i = 0; i < graph->vernum; i++)
	{
		getchar();
		scanf("%c", &graph->vertexs[i].vertex);
		graph->vertexs[i].firstedge = NULL; //初始第一条边为空
	}

	printf("请输入每条边对应的两个顶点的序号(格式为i,j):\n");
	EdgeNode *p;
	for(k = 0; k < graph->edgenum; k++)
	{
		scanf("%d,%d", &i, &j);  //读入边<vi,vj>的序号
		p = (node *)malloc(sizeof(node)); //生成新的结点
		p->adjvex = j - 1;
		p->next = graph->vertexs[i - 1].firstedge;
		graph->vertexs[i - 1].firstedge = p;
	}
}

/***************************************
 *
 * 深度优先遍历
 *
 * *************************************/
void DFSTraverse(Graph *graph, int v)
{
	visited[v] = TRUE;
	printf("深度遍历:结点%c\n", graph->vertexs[v].vertex);
	EdgeNode *p = graph->vertexs[v].firstedge;
	while(p != NULL)
	{
		if(!visited[p->adjvex])
			DFSTraverse(graph, p->adjvex);
		p = p->next;
	}
}

void DFS(Graph *graph)
{
	int i;
	for(i = 0; i < graph->vernum; i++)
		visited[i] = FALSE;

	for(i = 0; i < graph->vernum; i++)
		if(!visited[i])
			DFSTraverse(graph, i);
}

int main()
{
	Graph *graph = (Graph *)malloc(sizeof(Graph));
	MakeGraph(graph); //建立图的邻接表
	DFS(graph); //深度优先遍历

	return 0;
}

对于图一中的图,上述程序运行结果如图二。

图一


图二



抱歉!评论已关闭.