資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究根據給定條件，查詢是否可以遍歷給定圖中每個節點恰好一次
簡介
圖論在理解各種現實世界問題方面起著至關重要的作用，包括課程最佳化、考試安排和任務規劃。圖論中一個有趣的問題是尋找哈密頓路徑，即一條恰好訪問圖中每個節點一次的路徑。這個問題在電路設計、DNA測序和排程安排等領域都有應用。在本文中，我們深入探討了各種方法來確定根據某些條件是否可以恰好訪問給定圖中的每個節點。我們重點關注三種特定的演算法：回溯演算法、深度優先搜尋 (DFS) 和帶剪枝的回溯演算法。特別是，我們使用 C++ 程式語言演示了這些方法，提供了程式碼片段、分步演算法和每種方法的輸出。
方法 1：深度優先搜尋 (DFS)
DFS 演算法透過以深度優先的方式遍歷圖來探索所有可能的路徑。它使用一個棧來跟蹤當前路徑，並使用一個訪問陣列來檢查已訪問的頂點。
演算法
步驟 1 − 從圖的第一個頂點開始，並將其標記為已訪問。
步驟 2 − 將當前頂點推入棧中，並將其新增到路徑中。
步驟 3 − 當棧不為空時 −
從棧中彈出頂部的頂點。
如果所有頂點都已訪問，則列印路徑並返回 true。
對於每個未訪問的相鄰頂點，將其標記為已訪問，將其推入棧中，並將其新增到路徑中。
步驟 4 − 如果棧變為空，則返回 false。
示例
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
bool isSafe(int v, int pos, const vector<int>& path, const vector<vector<int>>& graph) {
if (graph[path[pos - 1]][v] == 0)
return false;
for (int i = 0; i < pos; ++i)
if (path[i] == v)
return false;
return true;
}
bool dfsUtil(const vector<vector<int>>& graph, vector<int>& path, vector<bool>& visited, int pos) {
int n = graph.size();
if (pos == n) {
for (int v : path)
cout << v << " ";
cout << endl;
return true;
}
for (int v = 1; v < n; ++v) {
if (!visited[v] && isSafe(v, pos, path, graph)) {
visited[v] = true;
path[pos] = v;
if (dfsUtil(graph, path, visited, pos + 1))
return true;
visited[v] = false;
path[pos] = -1;
}
}
return false;
}
void findHamiltonianPath(const vector<vector<int>>& graph) {
int n = graph.size();
vector<int> path(n, -1);
vector<bool> visited(n, false);
visited[0] = true; // Mark the first vertex as visited
path[0] = 0;
if (!dfsUtil(graph, path, visited, 1))
cout << "No Hamiltonian path exists." << endl;
}
int main() {
vector<vector<int>> graph = {
{0, 1, 1, 1},
{1, 0, 1, 0},
{1, 1, 0, 1},
{1, 0, 1, 0}
};
cout << "Depth-First Search (DFS):" << endl;
findHamiltonianPath(graph);
return 0;
}
輸出
Depth-First Search (DFS): 0 1 2 3
方法 2：回溯演算法
回溯演算法是一種蠻力方法，它有效地探索圖中的所有可能路徑以找到哈密頓路徑。它使用一個遞迴函式，在遇到死衚衕時回溯。
演算法
步驟 1 − 從圖的第一個頂點開始。
步驟 2 − 如果所有頂點都已訪問，則列印路徑並返回 true。
步驟 3 − 對於每個未訪問的相鄰頂點，將其標記為已訪問並將其新增到路徑中。
步驟 4 − 遞迴呼叫函式處理路徑中的下一個頂點。
步驟 5 − 如果遞迴呼叫返回 true，則路徑已完成。返回 true。
步驟 6 − 如果遞迴呼叫返回 false，則透過將當前頂點標記為未訪問並將其從路徑中移除來回溯。
步驟 7 − 如果沒有更多相鄰頂點可以探索，則返回 false。
示例
#include <iostream>
#include <vector>
using namespace std;
bool isSafe(int v, int pos, const vector<int>& path, const vector<vector<int>>& graph) {
if (graph[path[pos - 1]][v] == 0)
return false;
for (int i = 0; i < pos; ++i)
if (path[i] == v)
return false;
return true;
}
bool hamiltonianPathUtil(const vector<vector<int>>& graph, vector<int>& path, int pos) {
if (pos == graph.size()) {
for (int v : path)
cout << v << " ";
cout << endl;
return true;
}
for (int v = 1; v < graph.size(); ++v) {
if (isSafe(v, pos, path, graph)) {
path[pos] = v;
if (hamiltonianPathUtil(graph, path, pos + 1))
return true;
path[pos] = -1; // Backtrack
}
}
return false;
}
void findHamiltonianPath(const vector<vector<int>>& graph) {
vector<int> path(graph.size(), -1);
path[0] = 0; // Start with the first vertex
if (!hamiltonianPathUtil(graph, path, 1))
cout << "No Hamiltonian path exists." << endl;
}
int main() {
vector<vector<int>> graph = {
{0, 1, 1, 1},
{1, 0, 1, 0},
{1, 1, 0, 1},
{1, 0, 1, 0}
};
cout << "Backtracking Algorithm:" << endl;
findHamiltonianPath(graph);
return 0;
}
輸出
Backtracking Algorithm: 0 1 2 3
結論
總之，我們研究了兩種不同的方法來確定是否可以恰好訪問每個圖中的每個節點一次。這個問題，稱為哈密頓路徑問題，需要找到一條恰好訪問圖中每個節點一次而不返回任何節點的路徑。首先，我們討論了回溯演算法，該算法系統地探索圖中的所有可能路徑。該演算法使用遞迴和回溯來找到有效的哈密頓路徑。儘管它在計算上可能代價高昂，但回溯演算法為該問題提供了一個直接的解決方案。
127 次檢視
