資料結構
網路
關係資料庫管理系統 (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 次瀏覽
