Part one . 歐拉圖相關(guān)定義

創(chuàng)新互聯(lián)建站專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于做網(wǎng)站、成都網(wǎng)站制作、東明網(wǎng)絡(luò)推廣、小程序開(kāi)發(fā)、東明網(wǎng)絡(luò)營(yíng)銷(xiāo)、東明企業(yè)策劃、東明品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運(yùn)營(yíng)等，從售前售中售后，我們都將竭誠(chéng)為您服務(wù)，您的肯定，是我們最大的嘉獎(jiǎng)；創(chuàng)新互聯(lián)建站為所有大學(xué)生創(chuàng)業(yè)者提供東明建站搭建服務(wù)，24小時(shí)服務(wù)熱線：13518219792，官方網(wǎng)址：chinadenli.net

1. 從某一特定起點(diǎn)出發(fā)不重復(fù)的遍歷完所有邊的路徑叫做歐拉路徑，具有歐拉路徑的圖叫做半歐拉圖
2. 從圖中任意一點(diǎn)出發(fā)不重復(fù)地遍歷完所有邊并回到起點(diǎn)的回路叫做歐拉回路，具有歐拉回路的圖即歐拉圖

注意：以上定義中的圖均為連通圖

Part two . 歐拉圖性質(zhì)

1. 有向圖中

a.歐拉路徑中有且僅有1個(gè)出度-入度==1和1個(gè)入讀-出度==1的點(diǎn)，其余所有點(diǎn)都滿足出度==入度 。歐拉路徑的起點(diǎn)為出度-入讀==1的點(diǎn)。

b.歐拉回路中所有點(diǎn)都滿足出度-入讀==1。歐拉回路的起點(diǎn)可以是任意點(diǎn)。

2. 無(wú)向圖中

a.歐拉路徑中有2個(gè)奇度數(shù)的點(diǎn)。它的起點(diǎn)為這兩個(gè)奇度數(shù)中較小的一個(gè)點(diǎn)。

b.歐拉回路中所有點(diǎn)的都為偶度數(shù)點(diǎn)。它的起點(diǎn)為任意點(diǎn)。

Part three . 尋找歐拉路徑/回路

例題1：歐拉路徑模板題

思路：拿到題先不急于判定圖的連通性，而是先統(tǒng)計(jì)個(gè)點(diǎn)的出入度情況。如此，我們不僅可以初步判斷此圖是否為半歐拉圖（一般題目的默認(rèn)歐拉圖也包含半歐拉圖），若不滿足度數(shù)條件就說(shuō)明不存在半歐拉圖，而且還可以在滿足度數(shù)條件的基礎(chǔ)上確定一個(gè)起點(diǎn)。而后直接將起點(diǎn)帶入圖中dfs搜索，搜索的同時(shí)還需要統(tǒng)計(jì)所有走走過(guò)的邊的條數(shù)，用以判斷此圖是否聯(lián)通。若此圖聯(lián)通，則統(tǒng)計(jì)數(shù)一定和題目所給邊數(shù)相等，因?yàn)楣铝⒌狞c(diǎn)和邊在搜索時(shí)一定不會(huì)被遍歷到。還需要注意的一點(diǎn)是題目重要求的是字典序最小的答案，那么我們只需要按照所有點(diǎn)的出邊的權(quán)值的字典序給所有出邊排序就可以了。最后將存起來(lái)的答案倒序輸出即可。

上代碼

查看代碼

#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];//鄰接表存圖，最好用鄰接表或者鏈?zhǔn)角跋蛐?，鄰接矩陣容易炸空間
stack<int>ans;
int in[N], out[N],n,m,f1=0,f2=0,sta=1,del[N];
//del用以在搜索時(shí)記住上一次以u(píng)為出發(fā)點(diǎn)走到了哪條邊，這樣就不需要給走過(guò)的邊一一進(jìn)行標(biāo)記了，初始都為0代表
//out in 記錄點(diǎn)的出入度
//sta 存儲(chǔ)起點(diǎn)
//f1 f2分別統(tǒng)計(jì)出度-入度==1和入度-出度==1的點(diǎn)的個(gè)數(shù)
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);//讀入邊，因?yàn)檫叺臋?quán)值為u，故不再重復(fù)存儲(chǔ)權(quán)值
		in[v]++;
		out[u]++;//統(tǒng)計(jì)出入度
	}
	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))//若滿足歐拉回路或歐拉路徑的第一個(gè)條件則進(jìn)行下一步搜索
	{
		for (int i = 1; i <= n; i++)//對(duì)出邊進(jìn)行排序
		{
			sort(edge[i].begin(), edge[i].end());
		}
		dfs(sta);
		while(!ans.empty())//利用棧的后進(jìn)先出性質(zhì)完成答案的輸出
		{
			printf("%d ",ans.top());
			ans.pop();
		}
		puts("");
	}
	else//若不滿足初步條件就直接跳出
		printf("No\n");
	return 0;
}

例題2：歐拉圖簡(jiǎn)單應(yīng)用

分析：其實(shí)和上面的模板題沒(méi)有太大區(qū)別，做法思路相同，只是需要進(jìn)行一些轉(zhuǎn)換。題中要求將首尾字母相同的單詞連接在一起，其實(shí)就是將首字母作為起點(diǎn)，尾字母作為終點(diǎn)，而單詞本身則進(jìn)行編號(hào)處理作為邊的權(quán)值，這樣就成功地將本題轉(zhuǎn)化為一個(gè)尋找字典序最小的歐拉路徑問(wèn)題。雖然大體上看著和例 1 沒(méi)啥區(qū)別，但是值得注意的是邊的權(quán)值不再是起點(diǎn)，因此dfs函數(shù)中需要加一個(gè)參數(shù)來(lái)記錄邊的權(quán)值。另外，本題中dfs類似于一個(gè)必須確定當(dāng)前走這一步可行，才會(huì)記錄上一步路的摸索前進(jìn)的過(guò)程。

上代碼

#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];//用以存儲(chǔ)圖
vector<string>tmp;//存儲(chǔ)所有字母以便后面進(jìn)行排序，輸出答案
int n, in[27], out[27], maxn = -1, minn = 28, sta, f1, f2, k, flag, vis[N], del[N];
//maxn用來(lái)記錄點(diǎn)的最大值，minn用以記錄點(diǎn)的最小值,del用來(lái)標(biāo)記在上一次當(dāng)前點(diǎn)u已經(jīng)遍歷到哪條出邊了
//vis用來(lái)標(biāo)記已經(jīng)走過(guò)并壓入棧中的邊的編號(hào)，主要是用來(lái)彌補(bǔ)這個(gè)dfs的缺陷
stack<int>ans;//倒序記錄答案邊的編號(hào)
bool cmp(node x, node y)
{
	return x.s < y.s;
}

void dfs(int x, int num)//x為本層搜索的起點(diǎn)，num為上一層搜索過(guò)的邊
{
	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]++;//記錄點(diǎn)的出度與入度
		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;//初始化起點(diǎn)為字典序最小的單詞的首字母對(duì)應(yīng)的數(shù)字
	for (int i = minn; i <= maxn; i++)//對(duì)圖中所有點(diǎn)進(jìn)行出入度判定
	{
		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++)//題目中要求滿足條件的字典序最小的答案，故對(duì)每個(gè)點(diǎn)的所有出邊進(jìn)行排序
	{
		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;
}

以上內(nèi)容純屬個(gè)人理解，如有錯(cuò)誤，歡迎糾正。

時(shí)間：2022.3.8

網(wǎng)頁(yè)標(biāo)題：圖論——?dú)W拉圖原理及其應(yīng)用
標(biāo)題鏈接：http://chinadenli.net/article10/dsogodo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供面包屑導(dǎo)航、外貿(mào)網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)公司、企業(yè)建站、虛擬主機(jī)、品牌網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)