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)、完备匹配（匈牙利算法）等高效算法结合。