广度优先遍历和深度优先遍历

广度优先遍历

对于用邻接矩阵表示的图

①邻接矩阵的构建:

> /*一些量的定义*/
queue`<char`> q;				//定义一个队列，使用库函数queue
#define MVNum 100			//表示最大顶点个数
bool visited[MVNum];		        //定义一个visited数组，记录已被访问的顶点

/*邻接矩阵存储表示*/
typedef struct AMGraph
{
	char vexs[MVNum];            //顶点表
	int arcs[MVNum][MVNum];      //邻接矩阵
	int vexnum, arcnum;          //当前的顶点数和边数
}AMGraph;

/*找到顶点v的对应下标*/
int LocateVex(AMGraph &G, char v)
{
	int i;
	for (i = 0; i < G.vexnum; i++)
		if (G.vexs[i] == v)
			return i;
}

/*采用邻接矩阵表示法，创建无向图G*/
int CreateUDG_1(AMGraph &G)
{
	int i, j, k;
	char v1, v2;
	scanf("%d%d", &G.vexnum, &G.arcnum);	                //输入总顶点数，总边数
	getchar();				   	        //获取'\n’，防止其对之后的字符输入造成影响
	for (i = 0; i < G.vexnum; i++)			
		scanf("%c", &G.vexs[i]);			//依次输入点的信息
	for (i = 0; i < G.vexnum; i++)
		for (j = 0; j < G.vexnum; j++)
			G.arcs[i][j] = 0;			//初始化邻接矩阵边，0表示顶点i和j之间无边
	for (k = 0; k < G.arcnum; k++)
	{
		getchar();
		scanf("%c%c", &v1, &v2);			//输入一条边依附的顶点
		i = LocateVex(G, v1);				//找到顶点i的下标
		j = LocateVex(G, v2);				//找到顶点j的下标
		G.arcs[i][j] = G.arcs[j][i] = 1;	        //1表示顶点i和j之间有边，无向图不区分方向
	}
	return 1;
}

/*采用邻接矩阵表示图的广度优先遍历*/
void BFS_AM(AMGraph &G,char v0)
{
/*从v0元素开始访问图*/
 
	int u,i,v,w;
	v = LocateVex(G,v0);                            //找到v0对应的下标
	printf("%c ", v0);                              //打印v0
	visited[v] = 1;		                        //顶点v0已被访问
	q.push(v0);			                //将v0入队
 
	while (!q.empty())
	{
		u = q.front();				//将队头元素u出队，开始访问u的所有邻接点
		v = LocateVex(G, u);			//得到顶点u的对应下标
		q.pop();				//将顶点u出队
		for (i = 0; i < G.vexnum; i++)
		{
			w = G.vexs[i];
			if (G.arcs[v][i] && !visited[i])//顶点u和w间有边，且顶点w未被访问
			{
				printf("%c ", w);	//打印顶点w
				q.push(w);		//将顶点w入队
				visited[i] = 1;		//顶点w已被访问
			}
		}
	}
}

对于邻接表表示的广度优先遍历

/*找到顶点对应的下标*/
int LocateVex(ALGraph &G, char v)
{
	int i;
	for (i = 0; i < G.vexnum; i++)
		if (v == G.vertices[i].data)
			return i;
}

/*邻接表存储表示*/
typedef struct ArcNode	        //边结点
{
	int adjvex;		//该边所指向的顶点的位置
	ArcNode *nextarc;	//指向下一条边的指针
	int info;		//和边相关的信息，如权值
}ArcNode;
 
typedef struct VexNode		//表头结点
{
	char data;				
	ArcNode *firstarc;	//指向第一条依附该顶点的边的指针
}VexNode,AdjList[MVNum];	//AbjList表示一个表头结点表
 
typedef struct ALGraph
{
	AdjList vertices;
	int vexnum, arcnum;
}ALGraph;

/*采用邻接表表示法，创建无向图G*/
int CreateUDG_2(ALGraph &G)
{
	int i, j, k;
	char v1, v2;
	scanf("%d%d", &G.vexnum, &G.arcnum);	        //输入总顶点数，总边数
	getchar();
	for (i = 0; i < G.vexnum; i++)			//输入各顶点，构造表头结点表
	{
		scanf("%c", &G.vertices[i].data);	//输入顶点值
		G.vertices[i].firstarc = NULL;		//初始化每个表头结点的指针域为NULL
	}
	for (k = 0; k < G.arcnum; k++)			//输入各边，构造邻接表
	{
		getchar();
		scanf("%c%c", &v1, &v2);			//输入一条边依附的两个顶点
		i = LocateVex(G, v1);				//找到顶点i的下标
		j = LocateVex(G, v2);				//找到顶点j的下标
		ArcNode *p1 = new ArcNode;			//创建一个边结点*p1
		p1->adjvex = j;						//其邻接点域为j
		p1->nextarc = G.vertices[i].firstarc; G.vertices[i].firstarc = p1; // 将新结点*p插入到顶点v1的边表头部
		ArcNode *p2 = new ArcNode;			//生成另一个对称的新的表结点*p2
		p2->adjvex = i;
		p2->nextarc = G.vertices[j].firstarc;
		G.vertices[j].firstarc = p1;
	}
	return 1;
}

/*采用邻接表表示图的广度优先遍历*/
void BFS_AL(ALGraph &G, char v0)
{
	int u,w,v;
	ArcNode *p;
	printf("%c ", v0);		                                        //打印顶点v0
	v = LocateVex(G, v0);	                                                //找到v0对应的下标
	visited[v] = 1;			                                        //顶点v0已被访问
	q.push(v0);				                                //将顶点v0入队
	while (!q.empty())
	{
		u = q.front();		                                        //将顶点元素u出队，开始访问u的所有邻接点
		v = LocateVex(G, u);                                            //得到顶点u的对应下标
		q.pop();			//将顶点u出队
		for (p = G.vertices[v].firstarc; p; p = p->nextarc)		//遍历顶点u的邻接点
		{
			w = p->adjvex;	
			if (!visited[w])	//顶点p未被访问
			{
				printf("%c ", G.vertices[w].data);	        //打印顶点p
				visited[w] = 1;				        //顶点p已被访问
				q.push(G.vertices[w].data);			//将顶点p入队
			}
		}
	}
}

非联通图的广度优先遍历的实现方法

在这里插入代码片/*广度优先搜索非连通图*/
void BFSTraverse(AMGraph G)
{
	int v;
	for (v = 0; v < G.vexnum; v++)
		visited[v] = 0;							//将visited数组初始化
	for (v = 0; v < G.vexnum; v++)
		if (!visited[v]) BFS_AM(G, G.vexs[v]);	                        //对尚未访问的顶点调用BFS
}

深度优先遍历

邻接矩阵表示的深度优先遍历

void DFS_AM(AMGraph &G, int v)
{
	int w;
	printf("%c ", G.vexs[v]);
	visited[v] = 1;
	for (w = 0; w < G.vexnum; w++)
		if (G.arcs[v][w]&&!visited[w]) //递归调用
			DFS_AM(G,w);
}

邻接表表示的深度优先遍历

void DFS_AL(ALGraph &G, int v)
{
	int w;
	printf("%c ", G.vertices[v].data);
	visited[v] = 1;
	ArcNode *p = new ArcNode;
	p = G.vertices[v].firstarc;
	while (p)
	{
		w = p->adjvex;
		if (!visited[w]) DFS_AL(G, w);
		p = p->nextarc;
	}
}

转载于文章链接