7-1 愿天下有情人都是失散多年的兄妹 --DFS用c语言写程序
时间: 2024-09-29 15:14:14 浏览: 9
这个有趣的说法似乎是在引用网络流行语,但它并不是一个直接的编程题目。然而,如果你想要了解如何用C语言实现深度优先搜索(DFS),这是一个经典的图遍历算法,可以模拟查找两个节点之间的路径。以下是使用DFS的一个简单示例,假设我们有一个无向图,用邻接表表示:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node* next;
} Node;
void DFS(Node** graph, int start, int goal) {
Node* current = *graph[start];
while (current != NULL) {
if (current->value == goal) {
printf("找到了! %d -> %d\n", start, goal);
return;
}
// 递归遍历当前节点的所有邻居
DFS(graph, current->value, goal);
current = current->next;
}
printf("未找到路径从 %d 到 %d\n", start, goal);
}
// 添加边到邻接表
void addEdge(Node** graph, int src, int dst) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->value = dst;
newNode->next = graph[src];
graph[src] = newNode;
}
int main() {
int n; // 图的节点数
printf("请输入节点数:");
scanf("%d", &n);
Node** graph = (Node**)malloc(n * sizeof(Node*));
for (int i = 0; i < n; ++i) {
graph[i] = NULL;
}
// 根据输入添加边
for (int i = 0; i < n - 1; ++i) {
int u, v;
printf("请输入边 (%d, %d): ", i + 1, i + 2);
scanf("%d %d", &u, &v);
addEdge(&graph[u - 1], v - 1, i + 1); // 减一操作将用户输入转换为数组索引
}
int start, end;
printf("请输入开始节点和目标节点:");
scanf("%d %d", &start, &end);
DFS(graph, start - 1, end - 1); // 再次减一处理用户输入
return 0;
}
```
这个程序首先创建一个邻接表来存储图,然后根据用户的输入添加边,并执行深度优先搜索来查找指定起点和终点之间的路径。请注意,这里的"失散多年的兄妹"是一个比喻,实际上这里我们在找路径。