拓撲排序
拓撲排序主要用來解決有向無環(huán)圖萍丐，常用來描述一個工程或系統(tǒng)的進行過程。
有向無環(huán)圖(DAG,Directed Acyclic Graph)分類：
①AOV網(wǎng)：用一個有向圖表示一個工程的各子工程及其相互制約的關(guān)系放典，其中以頂點表示活動逝变，弧表示活動之間的優(yōu)先制約關(guān)系，稱這種有向圖為頂點表示活動的網(wǎng)奋构，簡稱AOV網(wǎng)(Activity On Vertex network).
②AOE網(wǎng)：以弧表示活動壳影，以頂點表示活動的開始或結(jié)束事件，稱這種有向圖為邊表示活動的網(wǎng)声怔，簡稱為AOE網(wǎng)(Activity On Edge).
拓撲序：
如果圖中從v到w有一條有向路徑态贤，則v一定排在w之前舱呻。滿足此條件的頂點序列稱為一個拓撲序
獲得一個拓撲序的過程就是拓撲排序
注意４谆稹！能進行拓撲序的一定是DAG.
實現(xiàn)思路：
//用一個隊列Q盛放沒有前驅(qū)結(jié)點的點箱吕，每次從中取出一個
1.在有向圖中選擇一個沒有前驅(qū)的頂點并輸出（Indegree[V]==0）
2.從圖中刪除該頂點和所有以它為尾的唤娌怠（后驅(qū)的indegree--）
重復這兩步，直到Q為空
//此種算法的復雜度為T=O(|V|+|E|)
bool TopSort( LGraph Graph, Vertex TopOrder[] )
{ /* 對Graph進行拓撲排序, TopOrder[]順序存儲排序后的頂點下標 */
int Indegree[MaxVertexNum], cnt;
Vertex V;
PtrToAdjVNode W;
Queue Q = CreateQueue( Graph->Nv );
/* 初始化Indegree[] */
for (V=0; V<Graph->Nv; V++)
Indegree[V] = 0;
/* 遍歷圖茬高，得到Indegree[] */
for (V=0; V<Graph->Nv; V++)
for (W=Graph->G[V].FirstEdge; W; W=W->Next)
Indegree[W->AdjV]++; /* 對有向邊<V, W->AdjV>累計終點的入度 */
/* 將所有入度為0的頂點入列 */
for (V=0; V<Graph->Nv; V++)
if ( Indegree[V]==0 )
AddQ(Q, V);
/* 準備工作完成下面進入拓撲排序 */
cnt = 0;
while( !IsEmpty(Q) ){
V = DeleteQ(Q); /* 彈出一個入度為0的頂點 */
TopOrder[cnt++] = V; /* 將之存為結(jié)果序列的下一個元素 */
/* 對V的每個鄰接點W->AdjV */
for ( W=Graph->G[V].FirstEdge; W; W=W->Next )
if ( --Indegree[W->AdjV] == 0 )/* 若刪除V使得W->AdjV入度為0 */
AddQ(Q, W->AdjV); /* 則該頂點入列 */
} /* while結(jié)束*/
if ( cnt != Graph->Nv )
return false; /* 說明圖中有回路, 返回不成功標志 */
else
return true;
}
歐拉通路/回路
定義：
歐拉通路：從S到T所有邊恰好經(jīng)過一次（一筆畫問題）
歐拉回路：從S回到S兆旬，所有邊恰好經(jīng)過一次（回到原點）
歐拉圖：存在歐拉回路（可以直接查奇頂點的個數(shù)來判斷）
判定（充要條件）：
（直接找奇度的個數(shù)，如果是）
歐拉回路：（每個頂點的度數(shù)必須是偶數(shù)）
1怎栽、含有至少2個頂點的連通多重圖具有歐拉回路當且僅當他的每個頂點度都是偶數(shù)
2丽猬、連通多重圖具有歐拉通路但無歐拉回路當且僅當 她恰巧有兩個度為奇數(shù)的點
歐拉通路：（奇頂點的個數(shù)等于0或者2）
1、圖G是連通的熏瞄，無孤立點存在
2脚祟、對于無向圖來說，度數(shù)為奇數(shù)的的點可以有2個或者0個强饮，并且這兩個奇點其中一個為起點另外一個為終點由桌。對于有向圖來說，可以存在兩個點邮丰，其入度不等于出度行您，其中一個出度比入度大1，為路徑的起點剪廉；另外一個入度比出度大1娃循，為路徑的終點。
定理2：如果一個圖有2n個奇頂點斗蒋，那么至少要用n筆才能走完
構(gòu)造方法
可以用DFS構(gòu)造（但是好麻煩我就鴿了）
//同時適用于通路和回路的無向圖
//若為有向圖捌斧，可以在最開始進行邊的標記（vis=0捧书，沒有通的就vis=-1），走過的時候標記為1
//即vis[u][v]=1
void euler(int u){
for(int v=0;v<n;v++){
if(G[u][v]&&!vis[u][v]){//如果有路且沒走過
vis[u][v]=vis[v][u]=1;//將兩邊標記
euler(v);//遞歸
//此次輸出print會使打印逆序骤星，應(yīng)用一個stack存放经瓷，最后一起輸出
printf("%d %d\n",u,v);//打印走的一條邊
}
}
}
//打印通路時，需要將V換成起點
哈密頓通路/回路
定義：
哈密頓圖：是一個無向圖洞难，由指定的起點前往指定的終點舆吮，途中經(jīng)過所有其他節(jié)點且只經(jīng)過一次。在圖論中是指含有哈密頓回路的圖
哈密頓回路：閉合的哈密頓路徑
哈密頓路徑：含有圖中所有頂點的路徑（走法）
半哈密頓圖：有哈密頓路徑但沒有哈密頓回路的圖
判定
一:Dirac定理(充分條件)
設(shè)一個無向圖中有N個頂點,若所有頂點的度數(shù)大于等于N/2,則哈密頓回路一定存在.(N/2指的是?N/2?,向上取整)
二:基本的必要條件
設(shè)圖G=<V, E>是哈密頓圖,則對于v的任意一個非空子集S,若以|S|表示S中元素的數(shù)目,G-S表示G中刪除了S中的點以及這些點所關(guān)聯(lián)的邊后得到的子圖,則W(G-S)<=|S|成立.其中W(G-S)是G-S中聯(lián)通分支數(shù).
三:競賽圖(哈密頓通路) N(N>=2)階競賽圖一點存在哈密頓通路.
具體思路：
只能用暴力枚舉法队贱，沒有什么其他辦法
所以說哈密頓只能解決少部分點
1色冀、首先規(guī)定作為起止點的頂點。由于回路是無向的柱嫌，因此起止點可直接任選锋恬；
2、規(guī)定中間點的其中兩點的先后次序编丘。這步是對基本窮舉的簡單優(yōu)化：對每對線路（每條回路都有順時針和逆時針兩種序列表示法）來說与学，不同的只是線路的方向，因此嘉抓，若選擇任意兩個中間頂點索守，并規(guī)定該兩頂點的先后次序（比如頂點a必須排在b前方），就可以把頂點序列的數(shù)量減半抑片。
（這一改進后卵佛，排列的總次數(shù)仍需要(n-1)!/2次，這意味著除非問題規(guī)模很小敞斋，不然窮舉查找法是不實用的）截汪。
3、通過生成n-1個中間點的組合來得到所有的線路植捎，計算這些線路的長度衙解，排序求得最短線路。
其他方法（求特定兩個點的路徑鸥跟，且所有節(jié)點都走一遍）：
可以用matlab寫出所有哈密頓路徑丢郊，根據(jù)起點和終點進行篩選
若找不到，就是無解
實現(xiàn)代碼
參考了一下其他博客的：
哈密頓回路：
https://blog.csdn.net/qq_30091945/article/details/77942384
哈密頓通路：
https://blog.csdn.net/zhangyifei521/article/details/53283028
