极客笔记C++ 在图的每个组件中找到最大的最短距离
介绍
在C语言中，找到图的每个组件中的最大最短距离可能是一个重要的任务。图是通过邻接表或矩阵表示的。通过使用广度优先搜索（BFS）或深度优先搜索（DFS），我们可以计算从每个节点到该组件内所有其他节点的最短距离。为了得到每个组件中的最大最短距离，我们遍历组件并维护一个最大值。最后，我们输出每个组件的结果。这种高效的算法使我们能够在不同的应用中分析复杂的网络，优化路由和资源分配。
方法1：广度优先搜索（BFS）
算法
- 第1步 - 创建BFS()函数，包括多个参数来执行BFS。
-
第2步 - 初始化一个二维数组来存储BFS遍历的节点。
-
第3步 - 遍历图中的所有节点。
-
第4步 - 如果一个节点未被访问过，则从该节点开始执行BFS。
-
第5步 - 在BFS过程中，计算从起始节点到该组件内所有其他节点的最短距离。
-
第6步 - 跟踪在BFS过程中遇到的最大距离。
-
第7步 - 最后，调用findMaxShortestDistance()函数来打印结果。
示例
#include <stdio.h>
#include <stdbool.h>
#define MAX_NODES 100
// Function to perform BFS
void BFS(int graph[MAX_NODES][MAX_NODES], int start, int num_nodes, int* visited, int* max_distance) {
int queue[MAX_NODES];
int front = 0, rear = 0;
int distance[MAX_NODES] = {0};
queue[rear++] = start;
visited[start] = 1;
while (front < rear) {
int node = queue[front++];
for (int i = 0; i < num_nodes; i++) {
if (graph[node][i] && !visited[i]) {
queue[rear++] = i;
visited[i] = 1;
distance[i] = distance[node] + 1;
if (distance[i] > *max_distance)
*max_distance = distance[i];
}
}
}
}
// Function to find maximum shortest distance in each component
void findMaxShortestDistance(int graph[MAX_NODES][MAX_NODES], int num_nodes) {
int visited[MAX_NODES] = {0};
int max_distance = 0;
for (int i = 0; i < num_nodes; i++) {
if (!visited[i]) {
BFS(graph, i, num_nodes, visited, &max_distance);
printf("Maximum shortest distance in component starting from node %d: %d\n", i, max_distance);
max_distance = 0;
}
}
}
// Sample graph representation
int main() {
int graph[MAX_NODES][MAX_NODES] = {
{0, 1, 1, 0, 0},
{1, 0, 0, 1, 0},
{1, 0, 0, 0, 1},
{0, 1, 0, 0, 0},
{0, 0, 1, 0, 0}
};
int num_nodes = 5;
findMaxShortestDistance(graph, num_nodes);
return 0;
}
输出
Maximum shortest distance in component starting from node 0:2
方法二：深度优先搜索（DFS）
以下是各种步骤列出：
-
步骤1 - 包含所需的头文件。
-
步骤2 - 定义包含多个参数的DFS（）函数。如果未经过核心，则从该核心开始执行DFS。在DFS过程中，计算从起始核心到组件内所有其他核心点的最短距离。
-
步骤3 - 跟踪DFS过程中遇到的最大移除。
-
步骤4 - 为每个组件放弃最大的分离。
示例
#include <stdio.h>
#include <stdbool.h>
#define MAX_NODES 100
// Function to perform DFS
void DFS(int graph[MAX_NODES][MAX_NODES], int start, int num_nodes, int* visited, int* max_distance) {
visited[start] = 1;
for (int i = 0; i < num_nodes; i++) {
if (graph[start][i] && !visited[i]) {
int distance = *max_distance + 1;
if (distance > *max_distance)
*max_distance = distance;
DFS(graph, i, num_nodes, visited, max_distance);
}
}
}
// Function to find maximum shortest distance in each component
void findMaxShortestDistance(int graph[MAX_NODES][MAX_NODES], int num_nodes) {
int visited[MAX_NODES] = {0};
int max_distance = 0;
for (int i = 0; i < num_nodes; i++) {
if (!visited[i]) {
DFS(graph, i, num_nodes, visited, &max_distance);
printf("Maximum shortest distance in component starting from node %d: %d\n", i, max_distance);
max_distance = 0;
}
}
}
// Sample graph representation
int main() {
int graph[MAX_NODES][MAX_NODES] = {
{0, 1, 0, 1, 0},
{1, 0, 1, 0, 0},
{0, 1, 0, 0, 1},
{1, 0, 0, 0, 1},
{0, 0, 1, 1, 0}
};
int num_nodes = 5;
findMaxShortestDistance(graph, num_nodes);
return 0;
}
输出
Maximum shortest distance in component starting from node 0:4
方法三：Floyd-Warshall算法
下面展示了各个步骤
-
步骤1 - 使用起始节点之间的初始距离初始化一个移除框架。
-
步骤2 - 执行Floyd-Warshall算法来计算所有节点对的最短距离。
-
步骤3 - 通过元素重复并找到每个元素中的最大最短距离。
-
步骤4 - 输出每个元素的最大距离。
示例
#include <stdio.h>
#include <stdbool.h>
#define MAX_NODES 100
#define INF 999999
// Function to find maximum shortest distance in each component
void findMaxShortestDistance(int gr[MAX_NODES][MAX_NODES], int num_nodes) {
int dt[MAX_NODES][MAX_NODES];
// Initialize distance matrix
for (int i = 0; i < num_nodes; i++) {
for (int j = 0; j < num_nodes; j++) {
dt[i][j] = gr[i][j];
}
}
// Floyd-Warshall algorithm
for (int k = 0; k < num_nodes; k++) {
for (int i = 0; i < num_nodes; i++) {
for (int j = 0; j < num_nodes; j++) {
if (dt[i][k] + dt[k][j] < dt[i][j]) {
dt[i][j] = dt[i][k] + dt[k][j];
}
}
}
}
// Find maximum distance in each component
int max_distance;
for (int i = 0; i < num_nodes; i++) {
max_distance = 0;
for (int j = 0; j < num_nodes; j++) {
if (dt[i][j] > max_distance && dt[i][j] != INF) {
max_distance = dt[i][j];
}
}
printf("Maximum shortest distance in component starting from node %d: %d\n", i, max_distance);
}
}
// Sample graph representation
int main() {
int graph[MAX_NODES][MAX_NODES] = {
{0, 1, 1, INF, INF},
{1, 0, INF, 1, INF},
{1, INF, 0, INF, 1},
{INF, 1, INF, 0, INF},
{INF, INF, 1, INF, 0}
};
int num_nodes = 5;
findMaxShortestDistance(graph, num_nodes);
return 0;
}
输出
Maximum shortest distance in component starting from node 0: 2
Maximum shortest distance in component starting from node 1: 3
Maximum shortest distance in component starting from node 2: 3
Maximum shortest distance in component starting from node 3: 4
Maximum shortest distance in component starting from node 4: 4
结论
总之，在图表分析中找到每个组件中最极端的最短距离可能是一个重要的任务。我们在C语言中探讨了三种方法：广度优先搜索（BFS）、深度优先搜索（DFS）和弗洛伊德-沃舍尔算法。这些方法使我们能够有效地计算从给定节点到组件内的所有其他节点的最短距离。通过保持一个正在运行的最大值，我们将确定每个组件的最大最短距离。这些方法在各个领域都有实际应用，如网络分析、路由优化和资源分配，可以更好地理解和利用复杂的图表结构。