数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学访问给定图中所有节点的最小顶点集
引言
寻找访问图中所有节点的最小顶点集在图论中可能是一个至关重要的问题。它在不同领域具有实际应用，包括网络优化、路由算法和任务规划。在本文中，我们将探讨三种不同的方法来阐明这个问题：深度优先搜索 (DFS)、广度优先搜索 (BFS) 和带回溯的深度优先遍历。我们将提供逐步说明、C语言中的代码用法以及每种方法的算法步骤。此外，我们将用一个示例图来说明这些方法的应用，以确保所有三种方法都能产生相同的输出。
方法 1：深度优先搜索 (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
方法 2：广度优先搜索 (BFS)
算法
步骤 1 − 创建一个布尔数组 visited[] 来检查已访问的顶点。
步骤 2 − 创建一个空队列并将起始顶点入队。
步骤 3 − 当队列不为空时，执行以下操作 − 从队列中出队顶点 v。
步骤 4 − 如果 v 未被访问，则将其标记为已访问并处理它。将 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 语言中实现这些方法提供了坚实的基础。无论您是在处理网络优化、任务规划还是任何其他与图相关的問題，这些方法都将成为您解决问题工具包中的宝贵工具。
89 次浏览
