深度优先搜索（DFS）

目录

一、DFS的基本概念

二、图的DFS

三、深度优先搜索的特点

四、实现DFS

五、DFS代码 

六、完整代码

七、运行结果

---

一、DFS的基本概念

        深度优先搜索（Depth-First Search，DFS）是一种常见的图遍历算法，用于在图或树等数据结构中探索所有可能的路径，以及查找特定目标（如寻找路径、判断连通性等）。DFS从一个起始顶点出发，沿着一条路径尽可能深入地访问顶点，直到不能继续为止，然后回溯到之前的顶点，继续尝试其他路径。这个过程通常使用递归来实现。      

二、图的DFS

        在图的DFS中，我们需要记录已经访问过的顶点，以避免无限循环。我们使用一个布尔数组来表示哪些顶点已经被访问过。从起始顶点开始，对于每个未访问的邻接顶点，我们递归地执行DFS。

三、深度优先搜索的特点

• 深度优先搜索倾向于沿着一条路径尽可能深入，因此可能会在递归中达到最大深度。
• 在实际应用中，DFS常用于查找路径、拓扑排序、连通性判断等问题。

四、实现DFS

  下图为一个示例图，我们将对这个图进行DFS遍历

五、DFS代码 

//DFS算法
bool visited[MAX_VERTICES];         //用于标记顶点是否被访问过，访问过为true
 
void DFS(Graph G, int v) {          //从顶点v出发，对图G进行深度优先遍历
	visit(G, v);                    //访问顶点v
	visited[v] = true;              //标记已访问
	for (int w = getFirstNeighbor(G, v); w >= 0; w = getNextNeighbor(G, v,w)) {
		if (!visited[w]) {          //w顶点没被访问
			DFS(G, w);              //递归调用DFS
		}
	}
}

六、完整代码

#include<iostream>
using namespace std;
 
//邻接矩阵定义图
#define MAX_VERTICES 100        //顶点数目最大值
typedef char VertexType;        //顶点的数据类型
typedef int EdgeType;           //带权图中边上权值的数据类型
struct Graph {
	int num_vertices, num_edge;           // 图当前顶点和边的数量
	VertexType vex[MAX_VERTICES];        //顶点表
	EdgeType adj_matrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵，边表
};
 
//初始化
void init_graph(Graph* graph, int num_vertices) {
	graph->num_vertices = num_vertices;
	graph->num_edge = 0;
	// 初始化邻接矩阵，初始值都为0（表示没有边）
	for (int i = 0; i < num_vertices; ++i) {
		//顶点数据赋值
		graph->vex[i] = 'a' + i;
 
		//邻接矩阵初始化
		for (int j = 0; j < num_vertices; ++j) {
			graph->adj_matrix[i][j] = 0;
		}
	}
}
 
//判断是否存在某条边（无向图）
bool is_edge(Graph* graph, int source, int destination) {
	return graph->adj_matrix[source][destination] != 0 ||
		graph->adj_matrix[destination][source] != 0;
}
 
// 添加边，将邻接矩阵中对应的位置设为1（或边的权重值）
void add_edge(Graph* graph, int source, int destination, int weight) {
	if (!is_edge(graph, source, destination)) {//不存在要添加的这条边
		graph->adj_matrix[source][destination] = weight;
		graph->adj_matrix[destination][source] = weight; // 对于无向图，需要设置对称位置
		graph->num_edge++;
	}
	else {
		cout << "此边已存在，不需要添加" << endl;
	}
 
}
 
//访问顶点
void visit(Graph G, int v) { //访问顶点，这里是打印
	cout << G.vex[v];
}
 
// 求顶点v的第一个邻接点
int getFirstNeighbor(Graph G, int v) {
	if (v >= 0 && v < G.num_vertices) {
		for (int i = 0; i < G.num_vertices; ++i) {
			if (G.adj_matrix[v][i] != 0) {
				return i;
			}
		}
	}
	return -1; // 顶点x没有邻接点或顶点索引无效
}
 
// 求顶点v的下一个邻接点
int getNextNeighbor(Graph G, int v, int w) {
	if (v >= 0 && v < G.num_vertices) {
		for (int i = w + 1; i < G.num_vertices; ++i) {
			if (G.adj_matrix[v][i] != 0) {
				return i;
			}
		}
	}
	return -1; // 顶点x没有除y以外的下一个邻接点或顶点索引无效
}
 
//DFS算法
bool visited[MAX_VERTICES];         //用于标记顶点是否被访问过，访问过为true
 
void DFS(Graph G, int v) {          //从顶点v出发，对图G进行深度优先遍历
	visit(G, v);                    //访问顶点v
	visited[v] = true;              //标记已访问
	for (int w = getFirstNeighbor(G, v); w >= 0; w = getNextNeighbor(G, v, w)) {
		if (!visited[w]) {          //w顶点没被访问
			DFS(G, w);              //递归调用DFS
		}
	}
}
 
//DFSTraverse对图G进行广度优先遍历
void DFSTraverse(Graph G) {
	for (int i = 0; i < G.num_vertices; i++) {
		visited[i] = false;         //初始化标记数组
	}
	//无向图连通图任意一个顶点调用一次DFS即可访问到全部顶点
	DFS(G, 0);                      //从a开始
	//无向图若有多个连通分量，则每个连通分量都调用一次DFS
	//有向图调用一次DFS或者BFS不一定可以访问到所有顶点，得看它是不是强连通的
}
 
int main() {
	//创建一个图
	Graph G;
	Graph* graph = &G;
 
	//初始化
	init_graph(graph, 6);
 
	//添加边
	add_edge(graph, 0, 1, 1);//a-b
	add_edge(graph, 0, 2, 1);//a-c
	add_edge(graph, 0, 4, 1);//a-e
	add_edge(graph, 1, 4, 1);//e-b
	add_edge(graph, 4, 3, 1);//e-d
	add_edge(graph, 4, 5, 1);//e-f
	add_edge(graph, 3, 5, 1);//d-f
 
	//打印一下邻接矩阵
	cout << "所创建的图的邻接矩阵：" << endl;
	for (int i = 0; i < G.num_vertices; i++) {
		for (int j = 0; j < G.num_vertices; j++) {
			cout << G.adj_matrix[i][j];
		}
		cout << endl;
	}
	cout << endl;
 
	//DFS
	cout << "DFS遍历结果为：";
	DFSTraverse(G);
	return 0;
}

七、运行结果

  完全没问题！！！！