极客笔记C++ 找出能够访问给定图中所有节点的最小顶点集
介绍
在图中找到能够访问所有节点的最小顶点集可能是图假设中的关键问题。它在不同领域中有实际应用，如网络优化、定向算法和任务规划。在本文中，我们将探讨三种不同的方法来解决这个问题：深度优先搜索 (DFS)、广度优先搜索 (BFS) 和带有回溯的深度优先遍历。我们将详细解释每种方法的算法步骤，并提供在 C 语言中使用代码示例。此外，我们将通过一个测试图来演示如何使用这些方法，以确保这三种策略都能得到相同的输出。
方法一：深度优先搜索 (DFS)
算法
- 步骤 1 - 创建一个布尔数组 visited[] 以检查是否访问过顶点。
-
步骤 2 - 初始化一个空栈，并将起始顶点推入栈中。
-
步骤 3 - 当栈不为空时，执行以下操作：
-
步骤 4 - 从栈中弹出顶点 v。如果 v 没有被访问过，则将其标记为已访问，并处理它。将 v 的所有未访问的相邻顶点推入栈中。重复步骤 3，直到栈为空。
-
步骤 5 - 返回已访问的顶点作为最小顶点集。
示例
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100
void dfs(int graph[MAX_VERTICES][MAX_VERTICES], int V, int start, bool visited[]) {
visited[start] = true;
printf("%d ", start);
for (int i = 0; i < V; i++) {
if (graph[start][i] == 1 && !visited[i]) {
dfs(graph, V, i, visited);
}
}
}
void smallestSetOfVertices(int graph[MAX_VERTICES][MAX_VERTICES], int V) {
bool visited[MAX_VERTICES] = { false };
for (int i = 0; i < V; i++) {
if (!visited[i]) {
dfs(graph, V, i, visited);
}
}
}
int main() {
int V = 5;
int graph[MAX_VERTICES][MAX_VERTICES] = {
{0, 1, 1, 0, 0},
{1, 0, 1, 0, 0},
{1, 1, 0, 0, 0},
{0, 0, 0, 0, 1},
{0, 0, 0, 1, 0}
};
printf("Smallest set of vertices: ");
smallestSetOfVertices(graph, V);
return 0;
}
输出
Smallest set of vertices: 0 1 2 3 4
方法二：广度优先搜索（BFS）
算法
-
步骤1 - 创建一个布尔数组visited[]用于检查已访问的顶点。
-
步骤2 - 创建一个空栈并将起始顶点入队。
-
步骤3 - 当队列不为空时，按照以下步骤进行：从队列中出队一个顶点v。
-
步骤4 - 如果v未被访问过，则将其标记为已访问，并将其所有未访问的邻接顶点入队。
-
步骤5 - 重复步骤3直到栈变为空。
-
步骤6 - 调用定义的函数smallestSetOfVertices()并打印结果。
示例
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100
void bfs(int graph[MAX_VERTICES][MAX_VERTICES], int V, int start, bool visited[]) {
int queue[MAX_VERTICES];
int front = 0, rear = 0;
queue[rear++] = start;
visited[start] = true;
while (front != rear) {
int v = queue[front++];
printf("%d ", v);
for (int i = 0; i < V; i++) {
if (graph[v][i] == 1 && !visited[i]) {
visited[i] = true;
queue[rear++] = i;
}
}
}
}
void smallestSetOfVertices(int graph[MAX_VERTICES][MAX_VERTICES], int V) {
bool visited[MAX_VERTICES] = { false };
for (int i = 0; i < V; i++) {
if (!visited[i]) {
bfs(graph, V, i, visited);
}
}
}
int main() {
int V = 5;
int graph[MAX_VERTICES][MAX_VERTICES] = {
{0, 1, 1, 0, 0},
{1, 0, 1, 1, 0},
{1, 1, 0, 0, 1},
{0, 1, 0, 0, 1},
{0, 0, 1, 1, 0}
};
printf("Smallest set of vertices: ");
smallestSetOfVertices(graph, V);
return 0;
}
输出
Smallest set of vertices: 0 1 2 3 4
方法3：深度优先遍历与回溯
算法
-
步骤1 - 创建一个布尔数组visited[]以检查已经访问过的顶点。初始化一个空栈，并将起始顶点推入栈中。
-
步骤2 - 当栈不为空时，执行以下操作 – 从栈中查看顶部的顶点v。
-
步骤3 - 如果顶点v未被访问过，则将其标记为已访问并处理它。找到顶点v的一个未访问的相邻顶点u。
-
步骤4 - 如果存在这样的顶点u，则将u推入栈中并结束。如果没有未访问的相邻顶点，则将v从栈中弹出。
-
步骤5 - 重复步骤3-4直到栈为空。
-
步骤6 - 最后，显示最小的顶点集合。
例子
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100
void dfs(int graph[MAX_VERTICES][MAX_VERTICES], int V, int start, bool visited[]) {
int stack[MAX_VERTICES];
int top = -1;
stack[++top] = start;
while (top != -1) {
int v = stack[top];
if (!visited[v]) {
visited[v] = true;
printf("%d ", v);
}
int u;
for (u = 0; u < V; u++) {
if (graph[v][u] == 1 && !visited[u]) {
stack[++top] = u;
break;
}
}
if (u == V)
top--;
}
}
void smallestSetOfVertices(int graph[MAX_VERTICES][MAX_VERTICES], int V) {
bool visited[MAX_VERTICES] = { false };
for (int i = 0; i < V; i++) {
if (!visited[i]) {
dfs(graph, V, i, visited);
}
}
}
int main() {
int V = 5;
int graph[MAX_VERTICES][MAX_VERTICES] = {
{0, 1, 1, 0, 0},
{1, 0, 1, 0, 0},
{1, 1, 0, 0, 0},
{0, 0, 0, 0, 1},
{0, 0, 0, 1, 0}
};
printf("Smallest set of vertices: ");
smallestSetOfVertices(graph, V);
return 0;
}
输出
Smallest set of vertices: 0 1 2 3 4
结论
我们研究了三种成功的方法，用于发现在给定的图中访问所有节点所需的最小顶点集。这些策略提供了不同的技巧来遍历图并识别关键顶点。通过利用这些方法，我们可以优化网络路径，减少资源利用以及提高任务规划效率。给定的代码示例和算法步骤为在C语言中执行这些方法提供了坚实的基础。无论你在进行网络优化、任务规划或其他与图相关的问题时，这些方法都将成为你解决问题的有价值工具。