Part one . 歐拉圖相關定義
- 從某一特定起點出發不重復的遍歷完所有邊的路徑叫做歐拉路徑，具有歐拉路徑的圖叫做半歐拉圖
- 從圖中任意一點出發不重復地遍歷完所有邊并回到起點的回路叫做歐拉回路，具有歐拉回路的圖即歐拉圖
注意：以上定義中的圖均為連通圖
Part two . 歐拉圖性質
- 有向圖中
a.歐拉路徑中有且僅有1個出度-入度==1和1個入讀-出度==1的點，其余所有點都滿足出度==入度 ，歐拉路徑的起點為出度-入讀==1的點，
b.歐拉回路中所有點都滿足出度-入讀==1，歐拉回路的起點可以是任意點，
2. 無向圖中
a.歐拉路徑中有2個奇度數的點，它的起點為這兩個奇度數中較小的一個點，
b.歐拉回路中所有點的都為偶度數點，它的起點為任意點，
Part three . 尋找歐拉路徑/回路
例題1：歐拉路徑模板題
思路：拿到題先不急于判定圖的連通性，而是先統計個點的出入度情況，如此，我們不僅可以初步判斷此圖是否為半歐拉圖（一般題目的默認歐拉圖也包含半歐拉圖），若不滿足度數條件就說明不存在半歐拉圖，而且還可以在滿足度數條件的基礎上確定一個起點，而后直接將起點帶入圖中dfs搜索，搜索的同時還需要統計所有走走過的邊的條數，用以判斷此圖是否聯通，若此圖聯通，則統計數一定和題目所給邊數相等，因為孤立的點和邊在搜索時一定不會被遍歷到，還需要注意的一點是題目重要求的是字典序最小的答案，那么我們只需要按照所有點的出邊的權值的字典序給所有出邊排序就可以了，最后將存起來的答案倒序輸出即可，
上代碼
查看代碼
#define CRT SECURE NO WARNINGS
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<cmath>
using namespace std;
const int N = 1e5 + 10;
vector<int> edge[N];//鄰接表存圖，最好用鄰接表或者鏈式前向星，鄰接矩陣容易炸空間
stack<int>ans;
int in[N], out[N],n,m,f1=0,f2=0,sta=1,del[N];
//del用以在搜索時記住上一次以u為出發點走到了哪條邊，這樣就不需要給走過的邊一一進行標記了，初始都為0代表
//out in 記錄點的出入度
//sta 存盤起點
//f1 f2分別統計出度-入度==1和入度-出度==1的點的個數
void dfs(int x)
{
for (int i =del[x]; i <edge[x].size(); i=del[x])
{
del[x] = i + 1;
dfs(edge[x][i]);
}
ans.push(x);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++)
{
int u, v;
scanf("%d%d", &u, &v);
edge[u].push_back(v);//讀入邊，因為邊的權值為u，故不再重復存盤權值
in[v]++;
out[u]++;//統計出入度
}
for (int i = 1; i <= n; i++)
{
if (in[i] - out[i] == 1)
f1++;
if (out[i] - in[i] == 1)
f2++, sta = i;
if (abs(in[i] - out[i]) > 1)//若存在出入度相差>2的情況，則一定不滿足題意，直接回傳
{
printf("No\n"); return 0;
}
}
if ((f1==1&&f2==1)||(f1==0&&f2==0))//若滿足歐拉回路或歐拉路徑的第一個條件則進行下一步搜索
{
for (int i = 1; i <= n; i++)//對出邊進行排序
{
sort(edge[i].begin(), edge[i].end());
}
dfs(sta);
while(!ans.empty())//利用堆疊的后進先出性質完成答案的輸出
{
printf("%d ",ans.top());
ans.pop();
}
puts("");
}
else//若不滿足初步條件就直接跳出
printf("No\n");
return 0;
}
例題2：歐拉圖簡單應用
分析：其實和上面的模板題沒有太大區別，做法思路相同，只是需要進行一些轉換，題中要求將首尾字母相同的單詞連接在一起，其實就是將首字母作為起點，尾字母作為終點，而單詞本身則進行編號處理作為邊的權值，這樣就成功地將本題轉化為一個尋找字典序最小的歐拉路徑問題，雖然大體上看著和例 1 沒啥區別，但是值得注意的是邊的權值不再是起點，因此dfs函式中需要加一個引數來記錄邊的權值，另外，本題中dfs類似于一個必須確定當前走這一步可行，才會記錄上一步路的摸索前進的程序，
上代碼
查看代碼
#define CRT SECURE NO WARNINGS
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<cmath>
using namespace std;
const int N = 1e3 + 10;
struct node
{
int v, num;
string s;
};
vector<node> maps[27];//用以存盤圖
vector<string>tmp;//存盤所有字母以便后面進行排序，輸出答案
int n, in[27], out[27], maxn = -1, minn = 28, sta, f1, f2, k, flag, vis[N], del[N];
//maxn用來記錄點的最大值，minn用以記錄點的最小值,del用來標記在上一次當前點u已經遍歷到哪條出邊了
//vis用來標記已經走過并壓入堆疊中的邊的編號，主要是用來彌補這個dfs的缺陷
stack<int>ans;//倒序記錄答案邊的編號
bool cmp(node x, node y)
{
return x.s < y.s;
}
void dfs(int x, int num)//x為本層搜索的起點，num為上一層搜索過的邊
{
if (flag)
return;
if (k == n)
flag = 1;
for (int i = del[x]; i < maps[x].size(); i = del[x])
{
del[x] = i + 1;
k++;
dfs(maps[x][i].v, maps[x][i].num);
}
if (!vis[num])
ans.push(num), vis[num]++;
}
int main()
{
scanf("%d", &n);
string t = "zzzzzzzzzzzzzzzzzzzzz";
for (int i = 0; i < n; i++)
{
string s;
cin >> s;
if (s < t)
t = s;//確定字典序最小的字母
tmp.push_back(s);
int u = (s[0] - 'a') + 1;
int v = (s[s.size() - 1] - 'a') + 1;
in[v]++;//記錄點的出度與入度
out[u]++;
maps[u].push_back({ v,i,tmp[i] });//讀入邊的資訊
maxn = max(v, max(maxn, u));
minn = min(v, min(minn, u));
}
sta = t[0] - 'a' + 1;//初始化起點為字典序最小的單詞的首字母對應的數字
for (int i = minn; i <= maxn; i++)//對圖中所有點進行出入度判定
{
if (in[i] - out[i] == 1 && (in[i] || out[i]))
f1++;
if (out[i] - in[i] == 1 && (in[i] || out[i]))
f2++, sta = i;
}
if (!((f1 == f2 == 1) || (f1 == 0 && f2 == 0))) {//初步確定圖中是否含歐拉路
printf("***\n");
return 0;
}
for (int i = minn; i <= maxn; i++)//題目中要求滿足條件的字典序最小的答案，故對每個點的所有出邊進行排序
{
sort(maps[i].begin(), maps[i].end(), cmp);
}
dfs(sta, maps[sta][0].num);
if (!flag)//未遍歷所有邊不滿足條件，直接跳出
{
printf("***\n");
return 0;
}
int mark = 1;
while (!ans.empty())//倒序輸出答案
{
if (mark)
cout << tmp[ans.top()], ans.pop(), mark = 0;
else
cout << "." << tmp[ans.top()], ans.pop();
}
return 0;
}以上內容純屬個人理解，如有錯誤，歡迎糾正，
時間：2022.3.8
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/440518.html
標籤：其他