寻找存在的路径
https://www.programmercarl.com/kamacoder/0107.%E5%AF%BB%E6%89%BE%E5%AD%98%E5%9C%A8%E7%9A%84%E8%B7%AF%E5%BE%84.html
思路
#include <stdio.h>
#include <stdlib.h>#define MAX_NODES 101// 邻接表的节点结构
typedef struct Node {int vertex;struct Node* next;
} Node;// 图的邻接表
typedef struct Graph {Node* adjacencyList[MAX_NODES];
} Graph;// 初始化图
void initGraph(Graph* graph) {for (int i = 1; i < MAX_NODES; i++) {graph->adjacencyList[i] = NULL;}
}// 创建邻接表节点
Node* createNode(int vertex) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->vertex = vertex;newNode->next = NULL;return newNode;
}// 添加边
void addEdge(Graph* graph, int src, int dest) {// 添加从 src 到 dest 的边Node* newNode = createNode(dest);newNode->next = graph->adjacencyList[src];graph->adjacencyList[src] = newNode;// 添加从 dest 到 src 的边 (无向图)newNode = createNode(src);newNode->next = graph->adjacencyList[dest];graph->adjacencyList[dest] = newNode;
}// DFS 函数
int dfs(Graph* graph, int visited[], int current, int destination) {if (current == destination) {return 1; // 找到目标}visited[current] = 1; // 标记当前节点为已访问Node* temp = graph->adjacencyList[current];while (temp != NULL) {int vertex = temp->vertex;if (!visited[vertex]) { // 如果未访问,递归 DFSif (dfs(graph, visited, vertex, destination)) {return 1;}}temp = temp->next;}return 0; // 没有找到目标
}int main() {int n, m;scanf("%d %d", &n, &m); // 输入节点数和边数Graph graph;initGraph(&graph);// 输入边信息for (int i = 0; i < m; i++) {int s, t;scanf("%d %d", &s, &t);addEdge(&graph, s, t);}int source, destination;scanf("%d %d", &source, &destination); // 输入起点和终点int visited[MAX_NODES] = {0}; // 访问标记数组// 调用 DFS 检查路径if (dfs(&graph, visited, source, destination)) {printf("1\n"); // 存在路径} else {printf("0\n"); // 不存在路径}return 0;
}
学习反思
代码是一个使用邻接表实现的图的深度优先搜索算法。代码首先定义了邻接表的节点结构和图的结构。然后通过initGraph函数初始化图,createNode函数创建节点,addEdge函数添加边。接着定义了DFS函数,用于递归地进行深度优先搜索。在主函数中,首先读取节点数和边数,然后根据输入添加边信息。接着读取起点和终点,然后定义一个访问标记数组,最后调用DFS函数检查是否存在路径,并输出结果。这段代码使用了递归的深度优先搜索算法来检查图中是否存在路径。它通过访问标记数组来标记已经访问过的节点,避免重复访问。在DFS函数中,当当前节点等于目标节点时,返回1表示找到路径;否则,递归地访问当前节点的邻接节点,直到找到路径或遍历完所有邻接节点。最后,根据DFS函数的返回值,输出是否存在路径。这段代码的时间复杂度为O(V+E),其中V为节点数,E为边数。因为在最坏情况下,每个节点都需要遍历一次,并且每个节点的邻接节点都需要遍历一次。空间复杂度为O(V),因为需要一个访问标记数组来记录节点的访问状态。总的来说,这段代码使用邻接表实现了图的深度优先搜索算法。可以用于检查图中是否存在路径。