图的遍历：深度优先搜索与广度优先搜索

1、定义

• 深度优先搜索（DFS）：从图中某个初始顶点v出发，首先访问初始顶点v，然后选择一个与顶点v相邻且没被访问过的顶点w为初始顶点，再从w出发进行深度优先遍历，直到图中与当前顶点v邻接的所有顶点都被访问过为止。

• 广度优先搜索（BFS）：首先访问初始顶点v，接着访问顶点v的所有未被访问过的邻接点v1,v2,...,vt，然后再按照v1,v2,...,vt的次序，访问每一个顶点的所有未被访问过的邻接点，依次类推，直到图中所有和初始顶点v有路径相通的顶点都被访问过为止。

2、应用

• 深度优先搜索主要用于图的查找。
• 广度优先搜索主要用于求图中两个顶点的最短路径。

3、实现

（1）邻接矩阵图的类型定义

#define N 100

typedef char ElemType;

//adjacency matrix graph
typedef struct MGraph
{
	ElemType vertexes[N];
	int edges[N][N];
	int visited[N];
	int n;
}MGraph;

（2）深度优先搜索算法（DFS）

//deep-first search
void DFS(MGraph &g, int k)
{
	cout << g.vertexes[k];
	g.visited[k] = 1;
	for (int i = 0; i < g.n; i++)
	{
		if (g.visited[i] == 0 && g.edges[k][i] != 0)
		{
			DFS(g, i);
		}
	}
}

（3）广度优先搜索算法（BFS）

//breadth-first search
void BFS(MGraph g, int k)
{
	queue<int> q;
	q.push(k);
	g.visited[k] = 1;
	while (!q.empty())
	{
		k = q.front();
		cout << g.vertexes[k];
		q.pop();
		for (int i = 0; i < g.n; i++)
		{
			if (g.visited[i] == 0 && g.edges[k][i] != 0)
			{
				q.push(i);
				g.visited[i] = 1;
			}
		}
	}
}

4、测试

样例输入：

5
HUEAK 
0 0 2 3 0
0 0 0 7 4
2 0 0 0 0
3 7 0 0 1
0 4 0 1 0

预期输出：

HUEAK
HUEAK 

#include <iostream>
#include <queue>
using namespace std;

#define N 100

typedef char ElemType;

//adjacency matrix graph
typedef struct MGraph
{
	ElemType vertexes[N];
	int edges[N][N];
	int visited[N];
	int n;
}MGraph;

//deep-first search
void DFS(MGraph &g, int k)
{
	cout << g.vertexes[k];
	g.visited[k] = 1;
	for (int i = 0; i < g.n; i++)
	{
		if (g.visited[i] == 0 && g.edges[k][i] != 0)
		{
			DFS(g, i);
		}
	}
}

//breadth-first search
void BFS(MGraph g, int k)
{
	queue<int> q;
	q.push(k);
	g.visited[k] = 1;
	while (!q.empty())
	{
		k = q.front();
		cout << g.vertexes[k];
		q.pop();
		for (int i = 0; i < g.n; i++)
		{
			if (g.visited[i] == 0 && g.edges[k][i] != 0)
			{
				q.push(i);
				g.visited[i] = 1;
			}
		}
	}
}

int main()
{
	int n;
	while (cin >> n)
	{
		//init
		MGraph g;
		g.n = n;
		//input
		for (int i = 0; i < n; i++)
			cin >> g.vertexes[i];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				cin >> g.edges[i][j];
		//print
		memset(g.visited, 0, n * sizeof(int));
		DFS(g, 0); cout << endl;
		memset(g.visited, 0, n * sizeof(int));
		BFS(g, 0); cout << endl;
	}
	return 0;
}

参考文献

[1] 李春葆.数据结构教程.清华大学出版社，2013.