真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

成都創(chuàng)新互聯(lián)網(wǎng)站制作重慶分公司

Graph Theory の brief introduction

一. 圖的概念

??1.定義

??某類具體事物（頂點(diǎn)）和這些事物之間的聯(lián)系（邊）,由頂點(diǎn)（vertex）和邊（edge）組成, 頂點(diǎn)的集合V，邊的集合E，圖記為G = (V,E)

我們提供的服務(wù)有：成都網(wǎng)站制作、網(wǎng)站設(shè)計(jì)、微信公眾號(hào)開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、青島ssl等。為上千多家企事業(yè)單位解決了網(wǎng)站和推廣的問(wèn)題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的青島網(wǎng)站制作公司

2.分類

????1、無(wú)向圖 Def：邊沒(méi)有指定方向的圖

????2、有向圖 Def：邊具有指定方向的圖 （有向圖中的邊又稱為弧，起點(diǎn)稱為弧頭，終點(diǎn)稱為 弧尾）

????3.帶權(quán)圖 Def: 邊上帶有權(quán)值的圖。（不同問(wèn)題中，權(quán)值意義不同，可以是距離、時(shí)間、價(jià)格、代價(jià)等不同屬性）

??

3.無(wú)向圖的術(shù)語(yǔ)

?兩個(gè)頂點(diǎn)之間如果有邊連接，那么就視為兩個(gè)頂點(diǎn)相鄰。

?路徑：相鄰頂點(diǎn)的序列。

?圈：起點(diǎn)和終點(diǎn)重合的路徑。

?連通圖：任意兩點(diǎn)之間都有路徑連接的圖。

?度：頂點(diǎn)連接的邊數(shù)叫做這個(gè)頂點(diǎn)的度。

樹：沒(méi)有圈的連通圖。

?森林：沒(méi)有圈的非連通圖。

??????????????????連通圖 非連通圖

4.有向圖的術(shù)語(yǔ)

在有向圖中，邊是單向的：每條邊所連接的兩個(gè)頂點(diǎn)是一個(gè)有序?qū)?/span>，他們的鄰接性是單向的。

有向路徑：相鄰頂點(diǎn)的序列。

有向環(huán)：一條至少含有一條邊且起點(diǎn)和終點(diǎn)相同的有向路徑。

有向無(wú)環(huán)圖（DAG）：沒(méi)有環(huán)的有向圖。

度：一個(gè)頂點(diǎn)的入度與出度之和稱為該頂點(diǎn)的度。

??1）入度：以頂點(diǎn)為弧頭的邊的數(shù)目稱為該頂點(diǎn)的入度

??2）出度：以頂點(diǎn)為弧尾的邊的數(shù)目稱為該頂點(diǎn)的出度

eg.

1->3->5->6 ：有向路徑 ??

1->3->4->1 ：有向環(huán) ????

(3、4、5、6) ：無(wú)環(huán)有向圖

節(jié)點(diǎn)1的度：3

節(jié)點(diǎn)1的入度：1

節(jié)點(diǎn)1的出度：2

二.圖的表示

??引入：如何用計(jì)算機(jī)來(lái)存儲(chǔ)圖的信息（頂點(diǎn)、邊），這是圖的存儲(chǔ)結(jié)構(gòu)要解決的問(wèn)題？

?1、鄰接矩陣

??對(duì)于一個(gè)有V的頂點(diǎn)的圖而言，可以使用V*V的二維數(shù)組表示。

??G[i][j] 表示的是頂點(diǎn)i與頂點(diǎn)j的關(guān)系。

????如果頂點(diǎn)i和頂點(diǎn)j之間 有邊相連， G[i][j]=1

????如果頂點(diǎn)i和頂點(diǎn)j之間 無(wú)邊相連， G[i][j]=0

??對(duì)于無(wú)向圖：G[i][j]=G[j][i]

??在帶權(quán)圖中，如果在邊不存在的情況下，將G[i][j]設(shè)置為0，則無(wú)法與權(quán)值為0的情況分開，因此選擇較大的常數(shù)INF即可。

? 鄰接矩陣的優(yōu)點(diǎn)：可以在常數(shù)時(shí)間內(nèi)判斷兩點(diǎn)之間是否有邊存在。

? 鄰接矩陣的缺點(diǎn)：表示稀疏圖時(shí)，浪費(fèi)大量?jī)?nèi)存空間。表示稠密圖還是很劃算。

??

??eg. 鄰接矩陣存儲(chǔ)圖

Code 
#include
using namespace std;
int a[1005][1005];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	int u,v;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		a[u][v]=a[v][u]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(a[i][j])
				printf("%d ",j);
		}
		printf("\n");
	}
	return 0;
}

?2、鄰接表

??通過(guò)把“從頂點(diǎn)0出發(fā)有到頂點(diǎn)2，3，5的邊”這樣的信息保存在鏈表中來(lái)表示圖。

??

出邊表的表結(jié)點(diǎn)存放的是從表頭結(jié)點(diǎn)出發(fā)的有向邊所指的尾頂點(diǎn)

入邊表的表結(jié)點(diǎn)存放的則是指向表頭結(jié)點(diǎn)的某個(gè)頭頂點(diǎn)

?帶權(quán)圖的鄰接表:在表結(jié)點(diǎn)中增加一個(gè)存放權(quán)的字段

??

eg.

將如下的圖利用鄰接表進(jìn)行表示，并輸出每個(gè)頂點(diǎn)的度。

Code 
#include
//存邊（編號(hào)和邊權(quán)）
struct edge{
	int v,w;
	edge(){}
	//構(gòu)造函數(shù)
	edge(int V,int W){
		v=V;
		w=W;
	}
};
vector G[maxn];

void addEdge(int u,int v,int w){
	G[u].push_back(edge(v,w));
}

for(int i=1;i<=N;++i){
	int u,v,w;
	cin>>u>>v>>w;
	addEdge(u,v,w);
	addEdge(v,u,w);
}

?3.鏈?zhǔn)角跋蛐?/span>

??參考：鏈?zhǔn)角跋蛐?-最通俗易懂的講解

??如果說(shuō)鄰接表是不好寫但效率好，鄰接矩陣是好寫但效率低的話，前向星就是一個(gè)相對(duì)中庸的數(shù)據(jù)結(jié)構(gòu)。前向星固然好寫，但效率并不高。而在優(yōu)化為鏈?zhǔn)角跋蛐呛?，效率也得到了較大的提升。雖然說(shuō)，世界上對(duì)鏈?zhǔn)角跋蛐堑氖褂貌⒉皇呛軓V泛，但在不愿意寫復(fù)雜的鄰接表的情況下，鏈?zhǔn)角跋蛐且彩且粋€(gè)很優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)。 ——摘自《百度百科》

鏈?zhǔn)角跋蛐瞧鋵?shí)就是靜態(tài)建立的鄰接表，時(shí)間效率為O（m），空間效率也為O（m）。遍歷效率也為O（m）。

對(duì)于下面的數(shù)據(jù)，第一行5個(gè)頂點(diǎn)，7條邊。接下來(lái)是邊的起點(diǎn)，終點(diǎn)和權(quán)值。也就是邊1 -> 2 權(quán)值為1。

樣例

5 7
1 2 1
2 3 2
3 4 3
1 3 4
4 1 5
1 5 6

鏈?zhǔn)角跋蛐谴娴氖且浴?，n】為起點(diǎn)的邊的集合，對(duì)于上面的數(shù)據(jù)輸出就是：

print 
1 //以1為起點(diǎn)的邊的集合
1 5 6
1 3 4
1 2 1
 
2 //以2為起點(diǎn)的邊的集合
2 3 2
 
3 //以3為起點(diǎn)的邊的集合
3 4 3
 
4  //以4為起點(diǎn)的邊的集合
4 5 7
4 1 5
 
5 //以5為起點(diǎn)的邊不存在

對(duì)比鄰接表

對(duì)于鄰接表來(lái)說(shuō)是這樣的：
1 -> 2 -> 3 -> 5
2 -> 3
3 -> 4
4 -> 1 -> 5
5 -> ^
對(duì)于鏈?zhǔn)角跋蛐莵?lái)說(shuō)是這樣的：
edge[0].to = 2; edge[0].next = -1; head[1] = 0;
edge[1].to = 3; edge[1].next = -1; head[2] = 1;
edge[2].to = 4; edge[2],next = -1; head[3] = 2;
edge[3].to = 3; edge[3].next = 0; head[1] = 3;
edge[4].to = 1; edge[4].next = -1; head[4] = 4;
edge[5].to = 5; edge[5].next = 3; head[1] = 5;
edge[6].to = 5; edge[6].next = 4; head[4] = 6;
簡(jiǎn)化后：1 -> 5 -> 3 -> 2

??由此可見(jiàn)對(duì)于每一個(gè)節(jié)點(diǎn)，輸出的順序?yàn)檩斎霑r(shí)的逆序

我們先對(duì)上面的7條邊進(jìn)行編號(hào)第一條邊是0以此類推編號(hào)【0~6】，然后我們要知道兩個(gè)變量的含義：

  • Next ：表示與這個(gè)邊起點(diǎn)相同的上一條邊的編號(hào)。
  • head[ i ] ：數(shù)組，表示以 i 為起點(diǎn)的最后一條邊的編號(hào)。

??加邊函數(shù)是這樣的：

void add_edge(int u, int v, int w)//加邊，u起點(diǎn)，v終點(diǎn)，w邊權(quán)
{
    edge[cnt].to = v; //終點(diǎn)
    edge[cnt].w = w; //權(quán)值
    edge[cnt].next = head[u];//以u(píng)為起點(diǎn)上一條邊的編號(hào)，也就是與這個(gè)邊起點(diǎn)相同的上一條邊的編號(hào)
    head[u] = cnt++;//更新以u(píng)為起點(diǎn)上一條邊的編號(hào)
}

??遍歷函數(shù)是這樣的：

for(int i = 1; i <= n; i++)//n個(gè)起點(diǎn)
    {
        cout << i << endl;
        for(int j = head[i]; j != -1; j = edge[j].next)//遍歷以i為起點(diǎn)的邊
        {
            cout << i << " " << edge[j].to << " " << edge[j].w << endl;
        }
        cout << endl;
    }

第一層for循環(huán)是找每一個(gè)點(diǎn)，依次遍歷以【1，n】為起點(diǎn)的邊的集合。第二層for循環(huán)是遍歷以 i 為起點(diǎn)的所有邊，k首先等于head[ i ]，注意head[ i ]中存的是以 i 為起點(diǎn)的最后一條邊的編號(hào)。然后通過(guò)edge[ j ].next來(lái)找下一條邊的編號(hào)。我們初始化head為-1，所以找到你最后一個(gè)邊（也就是以 i 為起點(diǎn)的第一條邊）時(shí)，你的edge[ j ].next為 -1做為終止條件。

Code 
#include
using namespace std;
const int maxn = 1005;//點(diǎn)數(shù)最大值
int n, m, cnt;//n個(gè)點(diǎn)，m條邊
struct Edge
{
    int to, w, next;//終點(diǎn)，邊權(quán)，同起點(diǎn)的上一條邊的編號(hào)
}edge[maxn];//邊集
int head[maxn];//head[i],表示以i為起點(diǎn)的第一條邊在邊集數(shù)組的位置（編號(hào)）
void init()//初始化
{
    for (int i = 0; i <= n; i++) head[i] = -1;
    cnt = 0;
}
void add_edge(int u, int v, int w)//加邊，u起點(diǎn)，v終點(diǎn)，w邊權(quán)
{
    edge[cnt].to = v; //終點(diǎn)
    edge[cnt].w = w; //權(quán)值
    edge[cnt].next = head[u];//以u(píng)為起點(diǎn)上一條邊的編號(hào)，也就是與這個(gè)邊起點(diǎn)相同的上一條邊的編號(hào)
    head[u] = cnt++;//更新以u(píng)為起點(diǎn)上一條邊的編號(hào)
}
int main()
{
    cin >> n >> m;
    int u, v, w;
    init();//初始化
    for (int i = 1; i <= m; i++)//輸入m條邊
    {
        cin >> u >> v >> w;
        add_edge(u, v, w);//加邊
        /*
        加雙向邊
        add_edge(u, v, w);
        add_edge(v, u, w);
        */
    }
    for (int i = 1; i <= n; i++)//n個(gè)起點(diǎn)
    {
        cout << i << endl;
        for (int j = head[i]; j != -1; j = edge[j].next)//遍歷以i為起點(diǎn)的邊
        {
            cout << i << " " << edge[j].to << " " << edge[j].w << endl;
        }
        cout << endl;
    }
    return 0;
}

三.圖的遍歷

??從圖中的某個(gè)頂點(diǎn)出發(fā)，按某種方法對(duì)圖中的所有頂點(diǎn)訪問(wèn)且僅訪問(wèn)一次。為了保證圖中的頂點(diǎn)在遍歷過(guò)程中僅訪問(wèn)一次，要為每一個(gè)頂點(diǎn)設(shè)置一個(gè)訪問(wèn)標(biāo)志。

??1.DFS

概念

深度優(yōu)先搜索(Depth-First Search)遍歷類似于樹的先根遍歷，是樹的先根遍歷的推廣。假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)未曾被訪問(wèn)，則深度優(yōu)先搜索可從圖中某 個(gè)頂點(diǎn)v出發(fā)，訪問(wèn)此頂點(diǎn)，然后依次從v的未被訪問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問(wèn)到；若此時(shí)圖中尚有頂點(diǎn)未被訪 問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。

Code

Code 
#include
#define Maxn 205
using namespace std;
int n, m;
bool a[Maxn][Maxn], vis[Maxn];
void DFS(int i) {
    cout << i << ' ';
    vis[i] = 1;
    for (int j = 1; j <= n; j++) {
        if (a[i][j]) {
            if (!vis[j]) {
                vis[j] = 1;
                DFS(j);
            }
        }
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        a[x][y] = 1;
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i])
            DFS(i);
    }
    return 0;
}
2.BFS

對(duì)(a)進(jìn)行廣度優(yōu)先搜索 遍歷的過(guò)程如圖(b)所示， 得到的頂點(diǎn)訪問(wèn)序列為: v1->v2->v3->v4->v5->v6->v7->v8

概念

廣度優(yōu)先搜索(Breadth-First Search)遍歷類似于樹的按層次遍歷的過(guò)程。 假設(shè)從圖中某頂點(diǎn)v出發(fā)，在訪問(wèn)v之后依次訪問(wèn)v的各個(gè)未被訪問(wèn)過(guò)的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問(wèn)它們的鄰接點(diǎn)，并使“先被訪問(wèn)的頂點(diǎn)的鄰接 點(diǎn)”先于“后被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)”被訪問(wèn)，直至圖中所有已被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)到。若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的 頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。換句話說(shuō)，廣度優(yōu)先搜索遍歷圖的過(guò)程是以v為起始點(diǎn)，由近至遠(yuǎn)，依次訪問(wèn)和v有路徑相通 且路徑長(zhǎng)度為1，2，…的頂點(diǎn)。

Code 
#include
using namespace std;  
int n,m;
int a[205][205],vis[205];
void bfs(int x){
	queue Q;
	Q.push(x); 
	printf("%d ",x);
	vis[x]=1;
	while(!Q.empty()){
		int now=Q.front();
		Q.pop();
		for(int i=1;i<=n;i++){
			if(a[now][i]&&!vis[i]){
				Q.push(i);
				printf("%d ",i);
				vis[i]=1;
			}
		}
	}
}
int main() {  
	scanf("%d%d",&n,&m);
	int u,v;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		a[u][v]=a[v][u]=1;
	}
	int k;
	scanf("%d",&k);
	bfs(k);
    return 0;  
}
3.歐拉路徑和歐拉回路

??歐拉路是指存在這樣一種圖 , 可以從其中一點(diǎn)出發(fā) , 不重復(fù)地走完其所有的邊 . 如果歐拉路的起點(diǎn)與終點(diǎn)相同 則稱之為歐拉回路

??歐拉路存在的充要條件 : 圖是連通的 ,因?yàn)槿舨贿B通不可能一次性遍歷所有邊。

??對(duì)于無(wú)向圖有且僅有兩個(gè)點(diǎn) ,與其相連的邊數(shù)為奇數(shù) ,其他點(diǎn)相連邊數(shù)皆為偶數(shù) ;對(duì)于兩個(gè)奇數(shù)點(diǎn) , 一個(gè)為起點(diǎn) , 一個(gè)為終點(diǎn) . 起點(diǎn)需要出去 ,終點(diǎn)需要進(jìn)入 ,故其必然與奇數(shù)個(gè)邊相連 .

??對(duì)于有向圖 除去起點(diǎn)和終點(diǎn) , 所有點(diǎn)的出度與入度相等。且起點(diǎn)出度比入度大 1。終點(diǎn)入度比出度大 1。若起點(diǎn)終點(diǎn)出入度也相同 ，則稱為歐拉回路。
可參見(jiàn)鴿巢原理

1. 歐拉通路

只通過(guò)一次圖中的每條邊，且經(jīng)過(guò)圖中所有頂點(diǎn)的通路為歐拉通路；

2. 歐拉回路

只通過(guò)一次圖中的每條邊，且經(jīng)過(guò)圖中所有頂點(diǎn)的回路為歐拉回路；

3. 有向圖的基圖

忽略有向邊的方向，得到的無(wú)向圖則為該有向圖的基圖；

4. 歐拉圖

存在歐拉回路的圖稱為歐拉圖；

5. 半歐拉圖

存在歐拉通路的圖稱為半歐拉圖；

二、判斷與證明

1. 無(wú)向圖

若無(wú)向圖 G 為連通圖，則可通過(guò)度的奇偶性判斷圖 G 是否存在歐拉通路或回路，有；

  1. 若圖 G 不存在度為奇數(shù)的端點(diǎn)時(shí)，則圖 G 有歐拉回路，即，無(wú)向連通多重圖中存在歐拉回路當(dāng)且僅當(dāng)圖中所有頂點(diǎn)的度數(shù)為偶數(shù)；

    對(duì)于上述定理，證明如下；

    1. 先證明其充分性，即存在歐拉回路則圖中的所有頂點(diǎn)的度數(shù)必然為偶數(shù)；

      由于要遍歷完圖中所有的節(jié)點(diǎn)，則對(duì)于除起點(diǎn)外的每一個(gè)節(jié)點(diǎn)，一定在一次遍歷時(shí)，通過(guò)一條邊來(lái)到這個(gè)節(jié)點(diǎn)，并通過(guò)另一條邊離開，所以其度數(shù)一定為偶數(shù)，則對(duì)于起點(diǎn)，通過(guò)一條邊從起點(diǎn)出發(fā)，遍歷所有節(jié)點(diǎn)，遍歷完后，則再通過(guò)一條邊返回，所以起點(diǎn)的度數(shù)也一定為偶數(shù)；

      則得證；

    2. 再證明其必要性，即若連通圖中所有頂點(diǎn)的度數(shù)為偶數(shù)，則必然存在歐拉回路；

      使用構(gòu)造性的存在性證明，則在所有頂點(diǎn)的度數(shù)為偶數(shù)的連通圖中，選取一條回路，則

      1. 若此回路為歐拉回路，則結(jié)論成立了；
      2. 若此回路不為歐拉回路，則將則回路上的邊刪除，若出現(xiàn)孤點(diǎn)，則忽略，則刪除邊后的子圖仍然保有原圖的性質(zhì)，即子圖中間的節(jié)點(diǎn)的度數(shù)為偶數(shù)，且子圖與刪除掉的回路一定有公共頂點(diǎn)，以該點(diǎn)作為起點(diǎn)繼續(xù)找回路，然后刪除，重復(fù)以上過(guò)程，直到所有的邊都被刪除為止，則所有這些刪除的回路一定可連接，構(gòu)成了一條歐拉回路；

      綜上，得證；

    綜上，得證；

  2. 若圖 G 存在且僅存在 2 個(gè)度為奇數(shù)的端點(diǎn)時(shí)，則圖 G 有歐拉通路，其起點(diǎn)為其中 1 個(gè)度為奇數(shù)的端點(diǎn)，終點(diǎn)為另一個(gè)度為奇數(shù)的端點(diǎn)，即在無(wú)向連通多重圖中存在歐拉通路且不存在歐拉回路當(dāng)且僅當(dāng)連通圖中有且只用兩個(gè)頂點(diǎn)的度數(shù)為奇數(shù)；

    對(duì)于上述定理，證明如下，

    1. 先證明其充分性，即存在歐拉通路則圖中有且只有兩個(gè)頂點(diǎn)的度數(shù)為奇數(shù)，其他頂點(diǎn)的度數(shù)皆為偶數(shù)；

      由于要遍歷完圖中所有的節(jié)點(diǎn)，則對(duì)于除起點(diǎn)與終點(diǎn)外的每一個(gè)節(jié)點(diǎn)，一定在一次遍歷時(shí)，通過(guò)一條邊來(lái)到這個(gè)節(jié)點(diǎn)，并通過(guò)另一條邊離開，所以其度數(shù)一定為偶數(shù)，則對(duì)于起點(diǎn)與終點(diǎn)，通過(guò)一條邊從起點(diǎn)出發(fā)，遍歷所有節(jié)點(diǎn)，遍歷完后，則再通過(guò)一條邊到達(dá)終點(diǎn)，所以起點(diǎn)與終點(diǎn)的度數(shù)為奇數(shù)；

      則得證；

    2. 再證明其必要性，即連通圖中有且只有兩個(gè)奇數(shù)度頂點(diǎn)，則必然存在歐拉通路；

      則可將起點(diǎn)與終點(diǎn)進(jìn)行連接，則原圖中所有得節(jié)點(diǎn)度數(shù)均為偶數(shù)，又由于 連通圖中所有頂點(diǎn)的度數(shù)為偶數(shù)，則必然存在歐拉回路 ，所以將連接的邊刪除后，可得到歐拉通路；

      則得證；

    綜上，得證；

  3. 若不滿足上述情況，則不存在歐拉回路與歐拉通路；

2. 有向圖

若有向圖 G 為連通圖，則可通過(guò)出，入度的大小判斷圖 G 是否存在歐拉通路或回路，有；

  1. 若圖 G 所有節(jié)點(diǎn)的入度等于出度，則圖 G 有歐拉回路，即有向連通多重圖中存在歐拉回路當(dāng)且僅當(dāng)圖中所有頂點(diǎn)的入度數(shù)等于出度數(shù)；

    證明如下，

    由于要遍歷完圖中所有的節(jié)點(diǎn)，則對(duì)于除起點(diǎn)外的每一個(gè)節(jié)點(diǎn)，一定在一次遍歷時(shí)，通過(guò)一條邊來(lái)到這個(gè)節(jié)點(diǎn)，并通過(guò)另一條邊離開，所以其入度等于出度，則對(duì)于起點(diǎn)，通過(guò)一條邊從起點(diǎn)出發(fā)，遍歷所有節(jié)點(diǎn)，遍歷完后，則再通過(guò)一條邊返回，所以起點(diǎn)的入度也一定等于出度；

    則得證；

  2. 若圖 G 存在且僅存在 2 個(gè)節(jié)點(diǎn)的入度不等于出度，且一個(gè)節(jié)點(diǎn)入度比出度大 1 ，一個(gè)入度比出度小 1 ，則圖 G 有歐拉通路，其起點(diǎn)為入度比出度小 1 的節(jié)點(diǎn)，終點(diǎn)為節(jié)點(diǎn)入度比出度大 1 節(jié)點(diǎn)，即有向連通多重圖中存在歐拉通路且不存在歐拉回路當(dāng)且僅當(dāng)連通圖中有且只用兩個(gè)頂點(diǎn)的入度不等于出度，且一個(gè)節(jié)點(diǎn)入度比出度大 1 ，另一個(gè)入度比出度小 1 ；

    證明如下，

    由于要遍歷完圖中所有的節(jié)點(diǎn)，則對(duì)于除起點(diǎn)與終點(diǎn)外的每一個(gè)節(jié)點(diǎn)，一定在一次遍歷時(shí)，通過(guò)一條邊來(lái)到這個(gè)節(jié)點(diǎn)，并通過(guò)另一條邊離開，所以其入度等于出度，則對(duì)于起點(diǎn)，通過(guò)一條邊從起點(diǎn)出發(fā)，遍歷所有節(jié)點(diǎn)，不需返回，所以入度比出度小 1 ，對(duì)于終點(diǎn)，通過(guò)一條邊到達(dá)，所以其入度比出度大 1 ；

    則得證；

  3. 若不滿足上述情況，則不存在歐拉回路與歐拉通路；

三、解法

1. DFS

思路

對(duì)于無(wú)向圖，則尋找圖中的度數(shù)為奇數(shù)的點(diǎn)，若沒(méi)有則從任意節(jié)點(diǎn)開始搜索；

對(duì)于有向圖，則尋找圖中入度比出度小 1 的點(diǎn)，若沒(méi)有則從任意節(jié)點(diǎn)開始搜索；

對(duì)節(jié)點(diǎn)搜索時(shí)，搜索與相鄰的節(jié)點(diǎn)，并刪除邊，繼續(xù)遞歸搜索即可；

代碼

以歐拉回路為例；

code 
#include 
#include 
#include 
#include 
#define MAXN 
using namespace std;
int f, n, m, in[MAXN], out[MAXN], s, pos = 1, ans[MAXN], cnt;
bool vis[MAXN], vise[MAXN];
struct edge {
	int to, tot;
};
vector  g[MAXN];
void dfs(int i) {
	vis[i] = true;
	while (!g[i].empty()) { // 遍歷并刪除
		int v = g[i].back().to, tot = g[i].back().tot;
		g[i].pop_back();
		if (!vise[abs(tot)]) {
			vise[abs(tot)] = true; // 標(biāo)記已走過(guò)的邊
			dfs(v);
			ans[++cnt] = tot; // 存入路徑
		}
	}
	return;
}
int main() {
	scanf("%d", &f);
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		g[x].push_back(edge({y, i}));
		if (f == 1) g[y].push_back(edge({x, -i})); // 雙向存邊，記錄反向
		in[x]++, out[y]++;
	}
	if (m == 0) {
		printf("YES\n");
		return 0;
	}
	if (f == 1) {
		for (int i = 1; i <= n; i++) {
			if ((in[i] + out[i]) % 2 == 1) { // 找起點(diǎn)
				printf("NO");
				return 0;
			} else if (in[i] + out[i]) {
				pos = i;
			}
		}
	} else {
		for (int i = 1; i <= n; i++) {
			if (in[i] != out[i]) { // 找起點(diǎn)
				printf("NO");
				return 0;
			} else if (in[i]) {
				pos = i;
			}
		}
	}
	dfs(pos); // 搜索
	for (int i = 1; i <= n; i++) {
		if ((in[i] || out[i]) && !vis[i]) { // 判斷合法
			printf("NO\n");
			return 0;
		}
	}

	printf("YES\n");
	for (int i = cnt; i >= 1; i--) { // 輸出
		if (f == 2) ans[i] = abs(ans[i]);
		printf("%d ", ans[i]);
	}
	return 0; 
}


文章題目：Graph Theory の brief introduction
分享路徑：http://weahome.cn/article/dsoighh.html

其他資訊

在線咨詢

微信咨詢

電話咨詢

028-86922220（工作日）

18980820575（7×24）

提交需求

返回頂部