当前位置：首页 > ds >正文

深度优先算法学习

ds 2025/7/20 13:09:21

1: 从 1点出发到 15点
在这里插入图片描述

#include <stdio.h>#define MAX_NODES 100typedef struct {int node_id;int *nextNodes;int nextNodesSize;
} Node;// 假设我们有一个节点数组，全局保存了所有节点
Node nodes[MAX_NODES];void dfs(int node_id)
{Node *node = &nodes[node_id];printf("visited: %d\n", node_id); // 打印访问的节点for (size_t i = 0; i < node->nextNodesSize; i++) {dfs(node->nextNodes[i]);}
}int main()
{// 创建并初始化临时数组int nextNodes1[] = {20, 3};int nextNodes2[] = {5, 6};int nextNodes6[] = {9, 10, 15};// 使用这些数组初始化节点nodes[1] = (Node){1, nextNodes1, 2};nodes[20] = (Node){20, nextNodes2, 2};nodes[5] = (Node){5, NULL, 0};nodes[6] = (Node){6, nextNodes6, 3};nodes[9] = (Node){9, NULL, 0};nodes[10] = (Node){10, NULL, 0};nodes[15] = (Node){15, NULL, 0};nodes[3] = (Node){3, NULL, 0};// 执行深度优先搜索dfs(1);return 0;
}

2 : 如果有环怎么遍历
在这里插入图片描述

#include <stdio.h>#define MAX_NODES 100typedef struct
{int node_id;int *nextNodes;int nextNodesSize;
} Node;// 假设我们有一个节点数组，全局保存了所有节点
Node nodes[MAX_NODES];int isVisited[MAX_NODES]; // 0 没访问过  1 访问过void dfs(int node_id)
{Node *node = &nodes[node_id];if (isVisited[node_id] == 1){return;}isVisited[node_id] = 1;printf("visited: %d\n", node_id); // 打印访问的节点for (size_t i = 0; i < node->nextNodesSize; i++){dfs(node->nextNodes[i]);}
}
int main()
{// 创建并初始化临时数组int nextNodes1[] = {20};int nextNodes20[] = {5, 6};int nextNodes3[] = {1};int nextNodes6[] = {9, 10, 15};int nextNodes15[] = {3};// 使用这些数组初始化节点nodes[1] = (Node){1, nextNodes1, 1};nodes[20] = (Node){20, nextNodes20, 2};nodes[5] = (Node){5, NULL, 0};nodes[6] = (Node){6, nextNodes6, 3};nodes[9] = (Node){9, NULL, 0};nodes[10] = (Node){10, NULL, 0};nodes[15] = (Node){15, nextNodes15, 1};nodes[3] = (Node){3, nextNodes3, 1};// 执行深度优先搜索dfs(1);return 0;
}

3: 是否出现了环
![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/bfb76d1d5950403fa208c81eef3525ff.png

#include <stdio.h>
#define MAX_NODES 100typedef struct
{int node_id;int *nextNodes;int nextNodesSize;
} Node;// 假设我们有一个节点数组，全局保存了所有节点
Node nodes[MAX_NODES];int isVisited[MAX_NODES]; // 0 没访问过  1 访问中  2 访问完成void dfs(int node_id)
{Node *node = &nodes[node_id];if (isVisited[node_id] == 1){printf("\n id: %d cycle \n", node_id);return;}if (isVisited[node_id] == 2){return; // 已访问完成，无需重复}isVisited[node_id] = 1;printf("visited: %d\n", node_id);for (size_t i = 0; i < node->nextNodesSize; i++){dfs(node->nextNodes[i]);}isVisited[node_id] = 2;
}int main()
{// 创建并初始化临时数组int nextNodes1[] = {20};int nextNodes20[] = {5, 6};int nextNodes3[] = {1};int nextNodes6[] = {9, 10, 15};int nextNodes15[] = {3};// 使用这些数组初始化节点nodes[1] = (Node){1, nextNodes1, 1};nodes[20] = (Node){20, nextNodes20, 2};nodes[5] = (Node){5, NULL, 0};nodes[6] = (Node){6, nextNodes6, 3};nodes[9] = (Node){9, NULL, 0};nodes[10] = (Node){10, NULL, 0};nodes[15] = (Node){15, nextNodes15, 1};nodes[3] = (Node){3, nextNodes3, 1};// 执行深度优先搜索dfs(1);return 0;
}

4：期望输出环上的结点
在这里插入图片描述

#include <stdio.h>#define MAX_NODES 100typedef struct
{int node_id;int *nextNodes;int nextNodesSize;
} Node;// 假设我们有一个节点数组，全局保存了所有节点
Node nodes[MAX_NODES];int isVisited[MAX_NODES]; // 0 没访问过  1 访问中  2 访问完成int stack[MAX_NODES];
int head=0;void showstack(){printf("\n");for (size_t i = 0; i < head; i++){printf(" %d ",stack[i]);}printf("\n");
}void dfs(int node_id)
{Node *node = &nodes[node_id];if (isVisited[node_id] == 1){showstack();printf("cycle");return;}isVisited[node_id] = 1;printf("visited: %d\n", node_id); // 打印访问的节点stack[head]=node_id;head++;for (size_t i = 0; i < node->nextNodesSize; i++){dfs(node->nextNodes[i]);}isVisited[node_id] = 2;head--;
}int main()
{// 创建并初始化临时数组int nextNodes1[] = {20};int nextNodes20[] = {5, 6};int nextNodes3[] = {1};int nextNodes6[] = {9, 10, 15};int nextNodes15[] = {3};// 使用这些数组初始化节点nodes[1] = (Node){1, nextNodes1, 1};nodes[20] = (Node){20, nextNodes20, 2};nodes[5] = (Node){5, NULL, 0};nodes[6] = (Node){6, nextNodes6, 3};nodes[9] = (Node){9, NULL, 0};nodes[10] = (Node){10, NULL, 0};nodes[15] = (Node){15, nextNodes15, 1};nodes[3] = (Node){3, nextNodes3, 1};// 执行深度优先搜索dfs(1);return 0;
}