資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中新增使歐拉回路所需的最小邊數
概念
對於給定的具有 b 個節點和 a 條邊的無向圖，任務是確定在給定圖中構建歐拉回路所需的最小邊數。
輸入
b = 3,
a = 2
Edges[] = {{1, 2}, {2, 3}}輸出
1
透過連線 1 到 3，我們可以構建一個歐拉回路。
方法
為了使圖中存在歐拉回路，我們需要每個節點都具有偶數度，因為這樣就存在一條可以用於在進入節點後離開節點的邊。
現在，可能有兩種情況：
圖中存在一個連通分量
對於這種情況，如果圖中所有節點都具有偶數度，那麼我們說該圖已經具有歐拉回路，我們不需要在其中新增任何邊。但是，如果存在任何具有奇數度的節點，則我們需要新增邊。圖中可以存在偶數個奇數度頂點。這個事件可以透過偶數度節點的度數和奇數度節點的度數之和等於總度數這一事實輕鬆驗證，總度數始終為偶數，因為每條邊對這個和的貢獻為 2。因此，如果我們將圖中隨機的奇數度節點配對並在它們之間新增一條邊，我們就可以使所有節點都具有偶數度，從而使歐拉回路存在。
圖中存在不連通分量
首先，我們將分量標記為奇數和偶數。奇數分量是指其中至少存在一個奇數度節點的分量。現在，我們取所有偶數分量，並從每個分量中選擇一個隨機頂點，並將它們線性排列。因此，在相鄰頂點之間新增邊，我們已經連線了偶數分量並構建了一個等效的奇數分量，該分量有兩個奇數度節點。
因此，為了處理奇數分量，即至少存在一個奇數度節點的分量，我們可以使用邊連線所有這些奇數分量，邊的數量等於不連通分量的數量。這可以透過將分量按迴圈順序放置並從每個分量中選擇兩個奇數度節點並將它們用於連線到兩側的分量來實現。現在我們有一個單個連通分量，我們已經對其進行了解釋。
示例
//This C++ program finds minimum edge required
// to make Euler Circuit
#include <bits/stdc++.h>
using namespace std;
// This Depth-First Search finds a connected
// component
void dfs1(vector<int> g1[], int vis1[], int odd1[],
int deg1[], int comp, int v){
vis1[v] = 1;
if (deg1[v]%2 == 1)
odd1[comp]++;
for (int u : g1[v])
if (vis1[u] == 0)
dfs1(g1, vis1, odd1, deg1, comp, u);
}
// We return minimum edge required to build Euler
// Circuit
int minEdge1(int n, int m, int s1[], int d1[]){
// g1 : to store adjacency list
// representation of graph.
// e1 : to store list of even degree vertices
// o1 : to store list of odd degree vertices
vector<int> g1[n+1], e1, o1;
int deg1[n+1]; // Degrees of vertices used
int vis1[n+1]; // To store visited in DFS
int odd1[n+1]; // Number of odd nodes in components
memset(deg1, 0, sizeof(deg1));
memset(vis1, 0, sizeof(vis1));
memset(odd1, 0, sizeof(odd1));
for (int i = 0; i < m; i++){
g1[s1[i]].push_back(d1[i]);
g1[d1[i]].push_back(s1[i]);
deg1[s1[i]]++;
deg1[d1[i]]++;
}
// This 'ans' is result and 'comp' is component id
int ans = 0, comp = 0;
for (int i = 1; i <= n; i++){
if (vis1[i]==0){
comp++;
dfs1(g1, vis1, odd1, deg1, comp, i);
// We check that if connected component
// is odd.
if (odd1[comp] == 0)
e1.push_back(comp);
// We check that if connected component
// is even.
else
o1.push_back(comp);
}
}
// It has been seen that if whole graph is a single connected
// component with even degree.
if (o1.size() == 0 && e1.size() == 1)
return 0;
// It has been seen that if all connected component is even
if (o1.size() == 0)
return e1.size();
//It has been seen that if graph have atleast one even connected
// component
if (e1.size() != 0)
ans += e1.size();
// For all the odd connected component.
for (int i : o1)
ans += odd1[i]/2;
return ans;
}
// Driven Program
int main(){
int b = 3, a = 2;
int source1[] = { 1, 2 };
int destination1[] = { 2, 3 };
cout << minEdge1(b, a, source1, destination1) << endl;
return 0;
}輸出
1
更新於：2020-07-23
196 次檢視
廣告