dfs演算法復雜度

1. 如何分析回溯 dfs時間復雜度

因為是選擇其中一個方向不斷前進，直接遇到某條件後才返回到上一次的起點重新嘗試另一條路徑。如果是廣度優先，那麼應該是同時向多個方向進發。

2. acmdfs判斷無向圖是否有環

如果存在迴路，則必存在一個子圖，是一個環路。環路中所有頂點的度>=2。
n演算法：
第一步：刪除所有度<=1的頂點及相關的邊，並將另外與這些邊相關的其它頂點的度減一。
第二步：將度數變為1的頂點排入隊列，並從該隊列中取出一個頂點重復步驟一。
如果最後還有未刪除頂點，則存在環，否則沒有環。
n演算法分析：
由於有m條邊，n個頂點。
i)如果m>=n，則根據圖論知識可直接判斷存在環路。（證明：如果沒有環路，則該圖必然是k棵樹 k>=1。根據樹的性質，邊的數目m = n-k。k>=1，所以：m<n）
ii)如果m<n 則按照上面的演算法每刪除一個度為0的頂點操作一次（最多n次），或每刪除一個度為1的頂點（同時刪一條邊）操作一次（最多m次）。這兩種操作的總數不會超過m+n。由於m<n，所以演算法復雜度為O(n)。
註：
該方法，演算法復雜度不止O(V)，首先初始時刻統計所有頂點的度的時候，復雜度為(V + E)，即使在後來的循環中E>=V，這樣演算法的復雜度也只能為O(V + E)。其次，在每次循環時，刪除度為1的頂點，那麼就必須將與這個頂點相連的點的度減一，並且執行delete node from list[list[node]]，這里查找的復雜度為list[list[node]]的長度，只有這樣才能保證當degree[i]=1時，list[i]裡面只有一個點。這樣最差的復雜度就為O(EV)了。

3. 八皇後遞歸演算法的復雜性

期盤是8*8的么?
八皇後採用回溯的方法,其實就是一種效率比較低下的方法,採用深度優先遍歷的方法進行(dfs),如果想問更多歡迎在我blog留言,我天天上的.
下面說正事:
如果是棋盤的長度n=8的話應該是O(n^16),但事實上應該比這快很多,因為O(n^16)會成一個很小的系數,為什麼會這樣呢,比如第一個頂點要考慮8*8的情況,在確定第二個頂點的時候就是小於7*7的情況了,但是演算法時間復雜度只是處略的估計,不計較系數,而且n也不大.
要是還有疑慮可以在hi上給我留言.

4. 數據結構判斷一個無向圖是否為樹的疑問

首先題目中有一處應該是錯了。
第2到n+1行，應該改為，第2到m+1行

方法：DFS搜索圖，圖中的邊只可能是樹邊或反向邊，一旦發現反向邊，則表明存在環。該演算法的復雜度為O(V)。

代碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

/*
設計演算法判斷一個無向圖G是否為樹。若是，輸出「Yes！」；否則輸出「No！」。
輸入格式：
第1行是空格分隔的兩個整數n和m，分別表示無向圖的頂點數和邊數，n<=10000,m<=100000。
第2到m+1行，每行兩個整數a和b，表示頂點a和b之間有一條邊，1 < = a,b <=n 。
鍵盤輸入，不必檢查輸入錯誤，輸入確保正確。
輸出格式：
屏幕上顯示一行，「yes！」或 「no！」.行末有回車。

樣例1

樣例2

輸入：
4 3
1 2
2 3
3 1
輸出：
No！

輸入：
2 1
1 2

輸出：
Yes！
*/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

const int N=10000, M=100000;
bool edge[N][N]; // 數組記錄兩點是否存在邊
bool visit[N]; // 標記該節點是否訪問過

bool DFS_check(int x, int y=-1)
{
if (visit[x])
return false;

visit[x] = true;
int i;
for (i=0;i<N;i++)
if (edge[x][i] && i!=y)
if (visit[i])
return false;
else
if (!DFS_check(i, x))
return false;

return true;
}

int main()
{
int n,m;
scanf("%d%d",&n,&m);

memset(edge,false,sizeof(edge));
int i,x,y;
for (i=0;i<m;i++)
{
scanf("%d%d",&x,&y);
edge[x-1][y-1] = true;
edge[y-1][x-1] = true;
}

memset(visit,false,sizeof(visit));
bool result = DFS_check(0);
if (result)
for (i=0;i<n;i++)
if (!visit[i])
result = false;
if (result)
printf("Yes!\n");
else
printf("No!\n");

system("pause");
return 0;

5. dfs演算法是什麼

DFS其實叫深度優先搜索演算法，起始它只是一種搜索的方法思路，並沒有固定的演算法格式。

作為搜索演算法的一種，DFS對於尋找一個解的NP（包括NPC）問題作用很大。但是，搜索演算法畢竟是時間復雜度是O(n!)的階乘級演算法，它的效率非常低，在數據規模變大時，這種演算法就顯得力不從心了。

DFS思路：

DFS思路是一條路走到底，撞到了牆再回頭。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點並重復以上過程，整個進程反復進行直到所有節點都被訪問為止，屬於盲目搜索。

6. 採用鄰接表存儲，拓撲排序演算法的時間復雜度為多少

要看使用什麼樣的拓撲排序，最好的方法是輸出DFS的逆序，這樣的演算法復雜度是O(V+L),V是頂點個數，L是邊個數。

7. DFS的效率

作為搜索演算法的一種，DFS對於尋找一個解的NP（包括NPC）問題作用很大。但是，搜索演算法畢竟是時間復雜度是O(n!)的階乘級演算法，它的效率比較低，在數據規模變大時，這種演算法就顯得力不從心了。
關於深度優先搜索的效率問題，有多種解決方法。最具有通用性的是剪枝（prunning），也就是去除沒有用的搜索分支。有可行性剪枝和最優性剪枝兩種。此外，對於很多問題，可以把搜索與動態規劃（DP,dynamic programming)、完備匹配（匈牙利演算法）等高效演算法結合。