資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究統計給定有向圖中所有哈密頓路徑
介紹
在圖論中，哈密頓路徑是指訪問每個頂點恰好一次且不重複邊的頂點序列。它以愛爾蘭數學家威廉·羅恩·漢密爾頓爵士命名，他為包括圖論在內的多個領域做出了重大貢獻。在本文中，我們將深入瞭解如何使用 C++ 程式設計理解和統計有向圖中所有可能的哈密頓路徑。現在，輪到我們應用這些原理，揭開不同型別有向圖中隱藏的秘密。
統計給定有向圖中所有哈密頓路徑
有向圖由一組頂點和一組具有特定方向或方向的邊連線而成。與邊是雙向或可以雙向的無向圖不同，有向圖對其邊施加嚴格的方向性。
輸入
在以上程式碼中，我們以鄰接矩陣作為輸入，
0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1 0 1 0 0 1 1 0
當演算法到達一個之前未訪問過的頂點時，它將該頂點標記為已訪問，並遞迴探索從該頂點出發所有可能的路徑。如果演算法恰好訪問了所有頂點一次，則它將 hamilton_paths_count 變數加 1。
示例
演算法從頂點 0 開始，遞迴探索從該頂點出發所有可能的路徑。演算法使用 visited_nodes 陣列跟蹤到目前為止已訪問的頂點。
可以構建的六條哈密頓路徑為：
0 -> 1 -> 2 -> 3 -> 4 0 -> 3 -> 2 -> 1 -> 4 0 -> 3 -> 4 -> 1 -> 2 0 -> 1 -> 4 -> 3 -> 2 0 -> 2 -> 1 -> 4 -> 3 0 -> 2 -> 3 -> 4 -> 1
因此，在給定的有向圖中，路徑數為 6。
方法 1：使用遞迴函式的 C++ 程式碼來統計給定有向圖中所有哈密頓路徑
統計給定有向圖中所有可能的哈密頓路徑需要一種稱為回溯的廣泛搜尋策略。該方法系統地探索每個可行的解決方案，並在此過程中丟棄發現不可行的任何可能性。
演算法
步驟 1 - 首先定義處理所需的的資料結構。
步驟 2 - 建立一個鄰接矩陣（二維陣列）來表示我們的有向圖。
步驟 3 - 定義變數，例如 number_of_vertices 來儲存總數，以及初始化為 0 的 hamilton_paths_count。
步驟 4 - 使用另一個名為 visited_nodes 的陣列跟蹤已訪問的節點，最初將所有頂點標記為未訪問。
步驟 5 - 給定頂點，我們必須查詢它們之間的邊，並避開函式之前已訪問過的任何頂點。
步驟 6 - 開發計算目的所需的函式。
createGraph() - 根據使用者定義的輸入或隨機生成方法初始化表示頂點連線的鄰接矩陣。
hamiltonPath() - 遞迴函式探索每個可能性，同時注意不要多次訪問已遍歷的頂點。
步驟 7 - 列印輸出。
示例
//The header file to include the input and output is used
// Maximum number of vertices
#include<iostream>
#define V 5
// Declaring variable for counting Hamiltonian paths
//Adjacent matrix is initialized
int hamilton_paths_count = 0;
int graph[V][V] = {
{0, 1, 0, 1, 0},
{1, 0, 1, 1, 0},
{0, 1, 0, 1, 1},
{1, 1, 1, 0, 1},
{0, 0, 1, 1, 0}
};
// Adjacency matrix representing the directed graph
bool visited_nodes[V];
//Implementation to obtain user-defined or random initialization of adjacency matrix
void createGraph() {
}
void hamiltonPath(int current_vertex, int total_vertices_visited) {
// Base case: all vertices have been visited once
// Increment count for a valid Hamiltonian path found
if(total_vertices_visited == V) {
hamilton_paths_count++;
return;
}
// Here, before invoking this function recursively, we make sure that an edge exists between two connected vertices and that the following vertices have not already been visited*/
visited_nodes[current_vertex] = true;
for(int i=0;i<V;i++) {
if(graph[current_vertex][i]!=0 && !visited_nodes[i]) {
hamiltonPath(i, total_vertices_visited+1);
//We increment the total_vertices_visited by 1 and move on to check if there are more valid paths from this point. Rinse and repeat!
//Once a recursive iteration is complete, reset 'visited' status while backtracking **/
visited_nodes[i] = false;
}
}
}
//main function to test the code
int main() {
createGraph();
memset(visited_nodes,false,sizeof(visited_nodes)); // Initialize all nodes as unvisited
hamiltonPath(0,1);
std::cout << "Total Hamiltonian Paths: " <<hamilton_paths_count<<std::endl;
return 0;
}
輸出
Total Hamiltonian Paths: 6
結論
最常用的程式語言是 C 和 C++，使用其中任何一種語言，我們都可以輕鬆處理哈密頓路徑。此路徑屬於數學運算，透過使用圖論，我們可以根據鄰接矩陣的輸入找到總路徑。以上程式碼中使用的方法是遞迴函式。
312 次檢視
