資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使形成環的邊不具有相同顏色的最小所需顏色數
為了減少所需的顏色數量並避免邊形成具有相同顏色的環，您可以使用圖表著色方法。目標是將顏色對映到頂點，以便由邊連線的兩個相鄰頂點不具有相同的顏色。透過識別圖表中的環，我們能夠保證構成環的邊被分配不同的顏色。這需要使用深度優先搜尋 (DFS) 或廣度優先搜尋 (BFS) 等策略遍歷圖表，並在必要時應用回溯以回溯並重新分配顏色。目標是找到滿足條件並保證沒有環具有相同顏色的邊的所需的最少顏色數。
使用的方法
DFS
貪婪著色演算法
DFS
深度優先搜尋 (DFS) 是一種圖遍歷演算法，它透過沿著每個分支檢視最遠可能的頂點來回溯。它從選定的頂點開始，訪問其相鄰的未訪問頂點，並遞迴地應用相同的過程。DFS 使用一個棧來跟蹤要訪問的頂點，以及一個已訪問集來檢查已訪問的頂點。此演算法有效地遍歷圖的深度，從而允許應用諸如路徑查詢、環檢測和拓撲排序。透過有效地探索圖，DFS 有效地查詢未訪問的頂點，使其成為理解和分析圖結構的主要策略。
演算法
初始化邊的空著色方案。
建立一個已訪問集來跟蹤已訪問的頂點。
對於圖中每個未訪問的頂點 v
將 v 標記為已訪問。
將第一個可用顏色分配給邊連線 v 和其父節點（如果適用）。
−遞迴地探索 v 的所有未訪問鄰居。
如果鄰居 u 已經被訪問並且具有與 v 的邊相同的顏色，則透過更改 v 的邊的顏色進行回溯。
如果鄰居 u 未被訪問，則將第一個可用顏色分配給連線 v 和 u 的邊。
如果所有邊都成功著色且沒有衝突，則返回著色方案。
如果出現衝突並且不可能存在著色方案，則透過更改先前邊的顏色進行回溯，並繼續探索。
重複步驟 3-5，直到找到有效的著色方案或所有可能的方案都已窮盡。
示例
#include <iostream>
#include <vector>
using namespace std;
const int numVertices = 5, numEdges = 7;
// Variable to store the graph
vector<pair<int, int>> adjacencyList[numEdges];
// To store whether a vertex is visited or not
int visited[numVertices];
// Boolean value to store whether the graph contains a cycle or not
bool hasCycle;
// Variable to store the color of the edges in the graph
int edgeColors[numEdges];
// Function to traverse the graph using DFS Traversal
void dfs(int vertex)
{
visited[vertex] = 1;
// Loop to iterate through all the edges from the source vertex
for (auto edge : adjacencyList[vertex]) {
int adjacentVertex = edge.first, edgeId = edge.second;
// If the adjacent vertex is not visited
if (visited[adjacentVertex] == 0) {
dfs(adjacentVertex);
edgeColors[edgeId] = 1;
}
// Condition to check cross and forward edges of the graph
else if (visited[adjacentVertex] == 2) {
edgeColors[edgeId] = 1;
}
// Presence of Back Edge
else {
edgeColors[edgeId] = 2;
hasCycle = true;
}
}
visited[vertex] = 2;
}
// Driver Code
int main()
{
adjacencyList[0].push_back(make_pair(1, 0));
adjacencyList[0].push_back(make_pair(2, 1));
adjacencyList[1].push_back(make_pair(2, 2));
adjacencyList[1].push_back(make_pair(3, 3));
adjacencyList[2].push_back(make_pair(3, 4));
adjacencyList[3].push_back(make_pair(4, 5));
adjacencyList[4].push_back(make_pair(2, 6));
// Loop to run DFS Traversal on vertices that are not visited
for (int i = 0; i < numVertices; ++i) {
if (visited[i] == 0) {
dfs(i);
}
}
cout << (hasCycle ? 2 : 1) << endl;
// Loop to print the colors of the edges
for (int i = 0; i < numEdges; ++i) {
cout << edgeColors[i] << ' ';
}
return 0;
}
輸出
2 1 1 1 1 1 1 2
貪婪著色方法
貪婪著色方法是一種簡單的演算法，它對圖的頂點進行著色，以確保沒有相鄰的頂點具有相同的顏色。它首先將第一個可用顏色分配給第一個頂點，然後繼續按順序對其餘頂點進行著色。對於每個頂點，它選擇其相鄰頂點未使用的最小可用顏色。此方法確保有效的頂點著色，但可能不會始終產生所需的最少顏色數。貪婪著色效率高，並且廣泛用於各種應用中，例如排程、圖著色和編譯器最佳化中的分配。
演算法
初始化一個儲存分配給頂點的顏色的集合。當我們為圖中的每個頂點分配顏色時，此集合將被更新。
按任何所需的順序對圖的頂點進行排序。對頂點進行排序可以幫助確定處理它們的順序，並且可能提高著色效率。
對於排序順序中的每個頂點 v
建立一個其相鄰頂點使用的顏色的集合。此集合將儲存當前分配給 v 的鄰居頂點的顏色。
從使用的顏色集合中找到最小的未使用顏色。遍歷使用的顏色集合，並選擇未顯示的最小顏色
將最小的未使用顏色分配給頂點 v。使用分配給頂點 v 的顏色更新顏色集合。
返回分配給每個頂點的顏色集合。生成的彩色集合將提供有效的頂點著色，其中沒有兩個相鄰的頂點共享相同的顏色。
貪婪著色演算法基於可用顏色和相鄰頂點使用的顏色，以貪婪的方式將顏色分配給頂點。雖然它可能不會始終產生圖所需的最少顏色數，但它提供了一種快速有效的頂點著色方法。
示例
#include <iostream>
#include <vector>
using namespace std;
const int numVertices = 5, numEdges = 7;
// Variable to store the graph
vector<vector<int>> adjacencyList(numVertices);
// To store whether a vertex is visited or not
int visited[numVertices];
// Boolean value to store whether the graph contains a cycle or not
bool hasCycle;
// Variable to store the color of the edges in the graph
int edgeColors[numEdges];
// Function to traverse the graph using DFS Traversal
void dfs(int vertex)
{
visited[vertex] = 1;
// Loop to iterate through all the edges from the source vertex
for (int adjacentVertex : adjacencyList[vertex]) {
// If the adjacent vertex is not visited
if (visited[adjacentVertex] == 0) {
dfs(adjacentVertex);
edgeColors[vertex] = 1;
}
// Condition to check cross and forward edges of the graph
else if (visited[adjacentVertex] == 2) {
edgeColors[vertex] = 1;
}
// Presence of Back Edge
else {
edgeColors[vertex] = 2;
hasCycle = true;
}
}
visited[vertex] = 2;
}
// Driver Code
int main()
{
adjacencyList[0] = {1, 2};
adjacencyList[1] = {2, 3};
adjacencyList[2] = {3};
adjacencyList[3] = {4};
adjacencyList[4] = {2};
// Loop to run DFS Traversal on vertices that are not visited
for (int i = 0; i < numVertices; ++i) {
if (visited[i] == 0) {
dfs(i);
}
}
cout << (hasCycle ? 2 : 1) << endl;
// Loop to print the colors of the edges
for (int i = 0; i < numEdges; ++i) {
cout << edgeColors[i] << ' ';
}
return 0;
}
輸出
2 1 1 1 1 2 0 0
結論
本文討論了最小化圖中所需顏色數的問題，以便構成環的邊不具有相同的顏色。它研究了兩種方法：深度優先搜尋 (DFS) 結合回溯演算法和貪婪著色演算法。DFS 方法包括遍歷圖並根據其與相鄰頂點的連線將顏色分配給邊。貪婪著色方法以貪婪的方式將顏色分配給頂點，並考慮相鄰頂點使用的顏色。這兩種方法都旨在找到滿足條件並保證沒有環具有相同顏色的邊的所需的最少顏色數。
66 次瀏覽
