asp公司网站源码,php网站制作实例教程,书店中文网站模板,深圳做网站好的网站建设公司C中的深度优先搜索算法
深度优先搜索#xff08;DFS#xff09;是一种用于遍历或搜索树或图的算法。这个算法会尽可能深的搜索树的分支。当节点v的所在边都己被探寻过#xff0c;搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点…C中的深度优先搜索算法
深度优先搜索DFS是一种用于遍历或搜索树或图的算法。这个算法会尽可能深的搜索树的分支。当节点v的所在边都己被探寻过搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点则选择其中一个作为源节点并重复以上过程整个进程反复进行直到所有节点都被访问为止。
以下是使用C实现深度优先搜索的示例代码及其解析
#includeiostream
#includevector using namespace std; vectorint adj[100005]; // 邻接表存储图
bool visited[100005]; // 标记数组记录每个节点是否被访问过 void dfs(int node) { // 深度优先搜索函数 visited[node] true; // 标记当前节点为已访问 cout node ; // 输出当前节点编号 int i; for(i 0; i adj[node].size(); i) { // 遍历当前节点的所有邻接点 if(!visited[adj[node][i]]) { // 如果邻接点未被访问过则继续访问 dfs(adj[node][i]); // 递归调用dfs函数 } }
} int main() { int n, m; // n为节点数m为边数 cin n m; for(int i 0; i m; i) { // 读入m条边构建邻接表 int u, v; cin u v; adj[u].push_back(v); adj[v].push_back(u); // 对于无向图还需要将v添加到u的邻接表中 } int start; // 开始遍历的节点编号 cin start; // 读入开始遍历的节点编号 for(int i 1; i n; i) { // 初始化visited数组将所有节点标记为未访问 visited[i] false; } dfs(start); // 从start节点开始进行深度优先搜索 return 0;
} 代码解析
首先定义了一个邻接表adj和一个标记数组visited用于存储图的信息和记录每个节点是否被访问过。邻接表使用vector数组实现可以方便的添加和删除邻接点。标记数组使用布尔型数组实现方便标记和判断节点是否被访问过。然后定义了一个深度优先搜索函数dfs接受一个节点的编号作为参数。首先将当前节点标记为已访问然后输出当前节点的编号接着遍历当前节点的所有邻接点。如果邻接点未被访问过则递归调用dfs函数进行深度优先搜索。这个过程一直持续到当前节点的所有邻接点都被访问过为止。在主函数中首先读入节点的数量和边的数量然后读入每条边的两个端点将它们添加到邻接表中。注意对于无向图还需要将第二个端点添加到第一个端点的邻接表中。然后初始化标记数组将所有节点标记为未访问。最后从用户输入的起始节点开始进行深度优先搜索。
