dfs算法

① 深度优先法(DFS)算法

从根节点开始，顺着它的某一子节点往下搜，所以再下一个是这个子节点的某一子节点，所以是个递归形式，当搜到子节点为NULL或者已经访问过了，于是回退到上一次的节点，若它还有没访问过的子节点继续往下搜，重复上述。当最后退回到根节点时，说明全部访问完毕，遍历完成。

② c++DFS算法问题。

这个题是比较基本的DFS问题，建议你自己多看多试一下，自己做出来意义更大一点。我想提供给你另外一种思路，时间复杂度更低，对于每个坐标（X，Y）可以从（x-1，y）和（x，y-1）到达，所以到这一点的可能数就是到达两个先驱点的方案数量的和，把黑洞设置成0就行了

③ 算法分析DFS求解

上网上查一查，这样的题我也不会。

④ DFS 算法 简介

Int visited[]; //初始化辅助数组,元素均为0
Void DFS(List,v,p)
{
visit(v); //访问起点
visited[v]=1; //起点已访问,0变1
while(p->link) //当存在起点的第一个邻接点时
{ p=p->link;
v=p->data;
if(!visited[v])
DFS(List,v,p); //进行递归
}
return;
}
下面是您的程序:
void DFS(List,v,p)
{
visit(v);
visited[v]=1;
while(p) //此处不该用p,应该判断它的邻接点是否存在
{
if(!visited[v])DFS(List,v,p);
p=p->link;
v=p->data; //此处的顺序肯定不对
}
return;
}

⑤ dfs算法是什么

DFS其实叫深度优先搜索算法，起始它只是一种搜索的方法思路，并没有固定的算法格式。

作为搜索算法的一种，DFS对于寻找一个解的NP（包括NPC）问题作用很大。但是，搜索算法毕竟是时间复杂度是O(n!)的阶乘级算法，它的效率非常低，在数据规模变大时，这种算法就显得力不从心了。

DFS思路：

DFS思路是一条路走到底，撞到了墙再回头。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止，属于盲目搜索。

⑥ 求有权无向图的DFS算法

深度优先遍历类似于树的先序遍历，俗称一条路走到黑，然后再考虑回溯的问题，回溯到最近访问的顶点并看它是否还有相邻顶点未访问，若无继续往前回溯。

我下面写写核心伪代码，其他诸如图的类型定义、还有你要对每个结点做的具体操作（我在代码中用visit()函数来代替了，具体做啥操作根据题目来）我就不写了。
bool visited[MSX_VERTEX_NUM]; //标记访问数组
void DFS_Traverse(Grath G) //对图G进行DFS
{
for(v=0;v<G.vexnum;++v)

{
visited[v]=false; //初始化已访问标记数据

}
for(v=0;v<G.vexnum;++v) //假设从v=0开始遍历

{
if(!visited[v])

DFS(G,v);

}

}
void DFS(Graph G,int v) //从顶点v出发，用递归的思想，深度优先遍历
{
visit(v); //这里的visit()就是对顶点v的具体操作，题目是啥就自己写啥

visited[v]=true; //标记已访问

for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))

//从最近结点开始，依次找相邻结点
{
if(!visited[w]) //w为还未访问的相邻结点

{
DFS(G,w);

}
}
}

⑦ 图的深度优先搜索算法dfs函数里面firstadjvex是什么意思

FirstAdiVex(G,v);
初始条件：图G存在，v是G中某个顶点。
操作结果：返回v的第一个领接顶点，若定点在G中没有领接顶点，则返回空。

⑧ 请问dicnic算法 有回溯吗..我看到一些博客上说dicnic 算法的 DFS有回溯，可是我感觉找到一条路就返回了了

有回溯，要将路径上的边正向边减流量，反向边加流量

非递归模板如下

intbfs(){
memset(dep,-1,sizeof(dep));

inthead=1,tail=1;
dep[sor]=0;dl[head]=sor;
while(head<=tail){
for(intp=nd[dl[head]];p!=-1;p=sid[p].next)
if((dep[sid[p].des]==-1)&&(sid[p].cap))dep[sid[p].des]=dep[dl[head]]+1,dl[++tail]=sid[p].des;
head++;
}

if(dep[tar]==-1)return(0);elsereturn(1);
}

intdinic(){
intmaxflow=0;
while(bfs()){
for(inti=0;i<=tar;i++)cur[i]=nd[i];

intu=sor,top=0;
while(1){
if(u==tar){
intmi=1e9,last;
for(inti=1;i<=top;i++)
if(sid[sta[i]].cap<mi)
{mi=sid[sta[i]].cap;last=i;}

for(inti=1;i<=top;i++)
sid[sta[i]].cap-=mi,sid[sta[i]^1].cap+=mi;
u=sid[sta[last]].fr;cur[u]=sid[cur[u]].next;top=last-1;
maxflow+=mi;
continue;
}

while((cur[u]!=-1)&&((sid[cur[u]].cap==0)||(dep[sid[cur[u]].des]!=dep[u]+1)))
cur[u]=sid[cur[u]].next;

if(cur[u]!=-1){sta[++top]=cur[u];u=sid[cur[u]].des;continue;}
else{
if(u==sor)break;
dep[u]=-1;
u=sid[sta[top--]].fr;
continue;
}
}
}
return(maxflow);
}

⑨ dfs算法是什么

dfs算法是深度优先搜索。

深度优先搜索属于图算法的一种，英文缩写为DFS。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

深度优先搜索是一种在开发爬虫早期使用较多的方法，它的目的是要达到被搜索结构的叶结点（即那些不包含任何超链的HTML文件）。

主要思想

借用一个邻接表和布尔类型数组（判断一个点是否查看过，用于避免重复到达同一个点，造成死循环等），先将所有点按一定次序存入邻接表，再通过迭代器，对邻接表的linklist和布尔数组做出操作，从而达到不重复递归遍历的效果。

⑩ 如何修改基于dfs的算法，使得可以避免对dfs生成的顶点序列进行逆序

可以把有限长非周期序列假设为一无限长周期序列的一个主直周期，即对有限长非周期序列进行周期延拓，延拓后的序列完全可以采用DFS进行处理，即采用复指数
第一题，DFS（深度优先遍历）是一个递归算法，在遍历的过程中，先访问的点被压入栈底（栈是先进后出），再说：拓扑有序是指如果点U到点V有一条弧，则在拓扑序列中U一定在V之前。深度优先算法搜索路径恰恰是一条弧，栈的输出是从最后一个被访问点开始输出，最后一个输出的点是第一个被访问的点。所以是逆的拓扑有序序列
第二题：无向图路径长度是指两个顶点之间弧的条数，如果两顶点路径长度有2条弧，则有3个顶点例如A——B——C；
第三题：A：极小连通图是一棵生成树，只有N-1条边，但是连通分量可能有N条边，例如极小连通图A—— B——C，连通分量“A”——B——C——“A”(这里的最后一个“A”跟第一个“A”一致）：；