資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究查詢圖中每個連通分量的最大最短距離
介紹
在 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
方法 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
方法 3：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) 和 Floyd-Warshall 演算法。這些方法使我們能夠有效地計算從給定節點到連通分量內所有其他節點的最短距離。透過維護一個執行最大值，我們可以確定每個連通分量的最大最短距離。這些方法在不同領域具有實際應用，例如網路分析、路由最佳化和資源分配，從而能夠更好地理解和利用複雜的圖結構。
更新於： 2023 年 8 月 25 日
93 次檢視
廣告