二、图的遍历——深度优先遍历

article/2025/9/20 8:15:45

深度优先遍历，也有称为深度优先搜索，简称为DFS。

深度优先遍历其实就是一个递归的过程，它从图中某个顶点ⅴ出发，访问此顶点，然后从V的未被访问的邻接点出发深度优先遍历图，直至图中所有和V有路径相通的顶点都被访问到。

邻接矩阵方式的深度优先遍历

#include<iostream>
#include<vector>
using namespace std;#define MAXVEX 100//最大顶点数
typedef char VertexType;//顶点类型
typedef int EdgeType;//边上的权值类型
typedef struct
{VertexType vexs[MAXVEX];//顶点表EdgeType arc[MAXVEX][MAXVEX];//邻接矩阵int numVertexte;//当前顶点数int numEdges;//当前边数
}MGraph;void DFS(MGraph G, int i, vector<bool>& visited)
{visited[i] = true;cout << G.vexs[i] << " ";//打印当前节点for (int j = 0; j < G.numVertexte; ++j){if (G.arc[i][j] == 1 && !visited[j])//如果节点i和节点j之间可达，并且节点j未被访问过{DFS(G, j, visited);//则从几点j开始继续深度遍历}}
}
void DFSTraverse(MGraph G)
{vector<bool> visited(G.numVertexte,false);//初始所有的顶点状态都是未访问过的for (int i = 0; i < G.numVertexte; ++i){if (!visited[i])//如果当前节点没被访问过，则从当前节点开始深度遍历{DFS(G, i, visited);}}
}

时间复杂度： $O(n^{2})$

邻接表方式的深度优先遍历

#include<iostream>
#include<vector>
using namespace std;#define MAXVEX 100//最大顶点数
typedef char VertexType;//顶点类型
typedef int EdgeType;//边上的权值类型typedef struct EdgeNode
{int adjvex;//邻接点域，存储该顶点对应的下标EdgeType weight;//用于存储权值，对于非网图可以不需要struct EdgeNode* next;//指向下一个邻接点
}EdgeNode;typedef struct VertexNode //顶点表结点
{VertexType data;//存储顶点信息EdgeNode* firstedge;//指向该顶点的第一个相邻结点
}VertexNode,AdjList[MAXVEX];typedef struct
{AdjList adjList;int numVertexes;//当前顶点数int numEdges;//当前边数
}GraphAdjList;void DFS(GraphAdjList G, int i, vector<bool>& visited)
{EdgeNode* p;visited[i] = true;cout << G.adjList[i].data << " ";p = G.adjList[i].firstedge;while (p){if (!visited[p->adjvex])//如果当前顶点未被访问过，则从当前节点开始深度优先遍历{DFS(G, p->adjvex, visited);}p = p->next;//当前节点的后一个节点}
}void DFSTraverse(GraphAdjList G)
{vector<bool> visited(G.numVertexes, false);//初始所有顶点状态都是未访问过状态for (int i = 0; i < G.numVertexes; ++i){if (!visited[i])//如果当前顶点未被访问过，则从当前节点开始深度优先遍历{DFS(G, i, visited);}}
}

时间复杂度： $O(n+e)$