数据结构（C实现）------- 图的深度优先遍历

[本文是自己学习所做笔记，欢迎转载，但请注明出处：http://blog.csdn.net/jesson20121020]

算法描述：

假设给定图G的初始状态是所有顶点均未曾访问过，在G中任选一顶点vi为初始的出发点，则深度优先遍历可定义如下：首先访问出发点vi，并将其标记为已被访问过；然后，依次从vi出发遍历vi的每一个邻接点vj，若vj未曾访问过，则以vj为新的出发点继续进行深度优先遍历，直至图中所有和vi有路径相通的顶点都被访问到为止。因此，若G是连通图，则从初始出发点开始的遍历过程结束也就意味着完成了对图G的遍历。

算法实现：

分别以邻接矩阵和邻接表作为图的存储结构，给出连通图的深度优先搜索遍历的递归算法。算法描述如下：

(1) 访问出发点vi，并将其标记为已被访问已访问过。

(2) 遍历vi的每一个邻接点vj，若vj未曾访问过，则以vj为新的出发点继续进行深度优先遍历。

完整代码：

用邻接矩阵实现深度优先搜索算法源代码如下：

/**
 * 深度遍历图
 **/
void DFS_MG(MGraph MG,int i){
	visit[i] = 1;
	printf("%c\t",MG.vexs[i]);
	int j;
	for (j = 1; j <= MG.vexnum;j++){
		if(visit[j] == 0 && MG.arcs[i][j] == 1)
			DFS_MG(MG,j);
	}
}

用邻接表实现深度优先搜索算法源代码如下：

/**
 * 深度遍历图
 **/
void DFS_AG(ALGraph AG,int i){
	ArcPtr p;
	printf("%c\t",AG.vertices[i].vexdata);
	visit[i] = 1;
	p = AG.vertices[i].firstarc;
	while( p!= NULL ){
		if(visit[p->adjvex] == 0)
			DFS_AG(AG,p->adjvex);
		p = p->nextarc;
	}
}

算法说明：

对于具有n个顶点，e条边的连通图，算法DFS_MG,DFS_AG 均调用n次。除了初始调用是来自外部，基于n-1次调用均是来自DFS_MG和DFS_AG内部的递归调用，用邻接矩阵实现时，遍历一个顶点的所有邻接点需要O(n)时间，则遍历整个图需要O(n^2),即DFS_MG的时间复杂度为O(n^2)。

用邻接表实现时，遍历n个顶点的所有邻接点是对边表节点的扫描一遍，故算法DFS_AG时间复杂度为O(n+e)。

采用深度优先遍历算法时，都要用到访问标志，所以该算法的空间复杂度为O(n).

邻接矩阵实现深度优先搜索算法完整代码如下：

/*
 ============================================================================
 Name        : Graph.c
 Author      : jesson20121020
 Version     : 1.0
 Description : create Graph using Adjacency Matrix, Ansi-style
 ============================================================================
 */

#include <stdio.h>
#include <stdlib.h>
#define MAX_VEX_NUM 50
typedef char VertexType;
typedef enum {
	DG, UDG
} GraphType;
typedef struct {
	VertexType vexs[MAX_VEX_NUM];
	int arcs[MAX_VEX_NUM][MAX_VEX_NUM];
	int vexnum, arcnum;
	GraphType type;
} MGraph;

//设置图中顶点访问标志
int visit[MAX_VEX_NUM];

/**
 * 根据名称得到指定顶点在顶点集合中的下标
 * vex  顶点
 * return 如果找到，则返回下标，否则，返回０
 */
int getIndexOfVexs(char vex, MGraph *MG) {
	int i;
	for (i = 1; i <= MG->vexnum; i++) {
		if (MG->vexs[i] == vex) {
			return i;
		}
	}
	return 0;
}

/**
 * 创建邻接矩阵
 */
void create_MG(MGraph *MG) {
	int i, j, k;
	int v1, v2, type;
	char c1, c2;
	printf("Please input graph type DG(0) or UDG(1) :");
	scanf("%d", &type);
	if (type == 0)
		MG->type = DG;
	else if (type == 1)
		MG->type = UDG;
	else {
		printf("Please input correct graph type DG(0) or UDG(1)!");
		return;
	}

	printf("Please input vexmun : ");
	scanf("%d", &MG->vexnum);
	printf("Please input arcnum : ");
	scanf("%d", &MG->arcnum);
	getchar();
	for (i = 1; i <= MG->vexnum; i++) {
		printf("Please input %dth vex(char):", i);
		scanf("%c", &MG->vexs[i]);
		getchar();
	}

	//初始化邻接矩阵
	for (i = 1; i <= MG->vexnum; i++) {
		for (j = 1; j <= MG->vexnum; j++) {
			MG->arcs[i][j] = 0;
		}
	}

	//输入边的信息，建立邻接矩阵
	for (k = 1; k <= MG->arcnum; k++) {
		printf("Please input %dth arc v1(char) v2(char) : ", k);

		scanf("%c %c", &c1, &c2);
		v1 = getIndexOfVexs(c1, MG);
		v2 = getIndexOfVexs(c2, MG);
		if (MG->type == 1)
			MG->arcs[v1][v2] = MG->arcs[v2][v1] = 1;
		else
			MG->arcs[v1][v2] = 1;
		getchar();
	}
}
/**
 * 打印邻接矩阵和顶点信息
 */
void print_MG(MGraph MG) {
	int i, j;
	if(MG.type == DG){
		printf("Graph type: Direct graph\n");
	}
	else{
		printf("Graph type: Undirect graph\n");
	}

	printf("Graph vertex number: %d\n",MG.vexnum);
	printf("Graph arc number: %d\n",MG.arcnum);

	printf("Vertex set:\n ");
	for (i = 1; i <= MG.vexnum; i++)
		printf("%c\t", MG.vexs[i]);
	printf("\nAdjacency Matrix:\n");

	for (i = 1; i <= MG.vexnum; i++) {
		j = 1;
		for (; j < MG.vexnum; j++) {
			printf("%d\t", MG.arcs[i][j]);
		}
		printf("%d\n", MG.arcs[i][j]);
	}
}

/**
 * 初始化顶点访问标志
 **/
void init_Visit(){
	int i;
	for(i = 0;i < MAX_VEX_NUM;i++)
		visit[i] = 0;
}


/**
 * 深度遍历图
 **/
void DFS_MG(MGraph MG,int i){
	visit[i] = 1;
	printf("%c\t",MG.vexs[i]);
	int j;
	for (j = 1; j <= MG.vexnum;j++){
		if(visit[j] == 0 && MG.arcs[i][j] == 1)
			DFS_MG(MG,j);
	}
}

/**
 * 主函数
 */
int main(void) {
	MGraph MG;
	create_MG(&MG);
	print_MG(MG);
	printf("The result of DFS:\n");
	DFS_MG(MG,1);

	return EXIT_SUCCESS;
}

邻接表实现深度优先搜索算法的完整代码如下：

/*
 ============================================================================
 Name        : ALGraph.c
 Author      : jesson20121020
 Version     : 1.0
 Copyright   : Your copyright notice
 Description : Graph using linkList, Ansi-style
 ============================================================================
 */

#include <stdio.h>
#include <stdlib.h>

#include <stdio.h>

#define MAX_VERTEX_NUM 50
typedef enum {
	DG, UDG
} GraphType;
typedef char VertexType;
//表节点
typedef struct ArcNode {
	int adjvex; //邻接节点
	int weight; //边权重
	struct ArcNode *nextarc; //下一个节点指针
} ArcNode, *ArcPtr;
//头节点
typedef struct {
	VertexType vexdata;
	int id;
	ArcPtr firstarc;
} VNode;
//头节点数组
typedef struct {
	VNode vertices[MAX_VERTEX_NUM];
	int vexnum, arcnum;
	GraphType type;
} ALGraph;

int visit[MAX_VERTEX_NUM];

/**
 * 根据顶点字符得到在顶点数组中的下标
 */
int getIndexOfVexs(char vex, ALGraph *AG) {
	int i;
	for (i = 1; i <= AG->vexnum; i++) {
		if (AG->vertices[i].vexdata == vex) {
			return i;
		}
	}
	return 0;
}
/**
 * 创建邻接表
 */
void create_AG(ALGraph *AG) {
	ArcPtr p,q;
	int i, j, k, type;
	VertexType v1, v2;
	printf("Please input graph type UG(0) or UDG(1) :");
	scanf("%d", &type);
	if (type == 0)
		AG->type = DG;
	else if (type == 1)
		AG->type = UDG;
	else {
		printf("Please input correct graph type UG(0) or UDG(1)!");
		return;
	}

	printf("please input vexnum:");
	scanf("%d", &AG->vexnum);
	printf("please input arcnum:");
	scanf("%d", &AG->arcnum);
	getchar();
	for (i = 1; i <= AG->vexnum; i++) {
		printf("please input the %dth vex(char) : ", i);
		scanf("%c", &AG->vertices[i].vexdata);
		getchar();
		AG->vertices[i].firstarc = NULL;
	}

	for (k = 1; k <= AG->arcnum; k++) {
		printf("please input the %dth arc v1(char) v2(char) :", k);
		scanf("%c %c", &v1, &v2);
		i = getIndexOfVexs(v1, AG);
		j = getIndexOfVexs(v2, AG);

		//根据图的类型创建邻接表
		//方法1，插入到链表头
		/*
		if (AG->type == DG) { //有向图
			p = (ArcPtr) malloc(sizeof(ArcNode));
			p->adjvex = j;
			p->nextarc = AG->vertices[i].firstarc;
			AG->vertices[i].firstarc = p;
		} else { //无向图
			p = (ArcPtr) malloc(sizeof(ArcNode));
			p->adjvex = j;
			p->nextarc = AG->vertices[i].firstarc;
			AG->vertices[i].firstarc = p;

			p = (ArcPtr) malloc(sizeof(ArcNode));
			p->adjvex = i;
			p->nextarc = AG->vertices[j].firstarc;
			AG->vertices[j].firstarc = p;
		}
		*/
		//方法2，插入到链表尾
		if (AG->type == DG) { //有向图
			p = (ArcPtr) malloc(sizeof(ArcNode));
			p->adjvex = j;
			//表为空
			if(AG->vertices[i].firstarc == NULL){
				AG->vertices[i].firstarc = p;
			}
			else{
				//找最后一个表节点
				q = AG->vertices[i].firstarc;
				while(q->nextarc != NULL){
					q = q->nextarc;
				}
				q->nextarc = p;
			}
			p->nextarc = NULL;

		} else { //无向图

			p = (ArcPtr) malloc(sizeof(ArcNode));
			p->adjvex = j;
			//表为空
			if(AG->vertices[i].firstarc == NULL){
				AG->vertices[i].firstarc = p;
			}
			else{
				//找最后一个表节点
				q = AG->vertices[i].firstarc;
				while(q->nextarc != NULL){
					q = q->nextarc;
				}
				q->nextarc = p;
			}
			p->nextarc = NULL;

			p = (ArcPtr) malloc(sizeof(ArcNode));
			p->adjvex = i;
			//表为空
			if(AG->vertices[j].firstarc == NULL){
				AG->vertices[j].firstarc = p;
			}
			else{
				//找最后一个表节点
				q = AG->vertices[j].firstarc;
				while(q->nextarc != NULL){
					q = q->nextarc;
				}
				q->nextarc = p;
			}
			p->nextarc = NULL;
		}

		getchar();
	}
}

/**
 * 输出图的相关信息
 */
void print_AG(ALGraph AG) {
	ArcPtr p;
	int i;
	if (AG.type == DG) {
		printf("Graph type: Direct graph\n");
	} else {
		printf("Graph type: Undirect graph\n");
	}

	printf("Graph vertex number: %d\n", AG.vexnum);
	printf("Graph arc number: %d\n", AG.arcnum);

	printf("Vertex set :\n");
	for (i = 1; i <= AG.vexnum; i++)
		printf("%c\t", AG.vertices[i].vexdata);
	printf("\nAdjacency List:\n");
	for (i = 1; i <= AG.vexnum; i++) {
		printf("%d", i);
		p = AG.vertices[i].firstarc;
		while (p != NULL) {
			printf("-->%d", p->adjvex);
			p = p->nextarc;
		}
		printf("\n");
	}
}

/**
 * 初始化顶点访问标志
 **/
void init_Visit(){
	int i;
	for(i = 0;i < MAX_VERTEX_NUM;i++)
		visit[i] = 0;
}


/**
 * 深度遍历图
 **/
void DFS_AG(ALGraph AG,int i){
	ArcPtr p;
	printf("%c\t",AG.vertices[i].vexdata);
	visit[i] = 1;
	p = AG.vertices[i].firstarc;
	while( p!= NULL ){
		if(visit[p->adjvex] == 0)
			DFS_AG(AG,p->adjvex);
		p = p->nextarc;
	}
}

int main(void) {
	ALGraph AG;

	create_AG(&AG);

	print_AG(AG);
	printf("The result of DFS:\n");
	DFS_AG(AG,1);

	return EXIT_SUCCESS;
}

秒客网

数据结构（C实现）------- 图的深度优先遍历

算法描述：

算法实现：

完整代码：

算法说明：

相关文章