dfs算法入栈的过程

Ⅰ 写出以深度优先的搜索法的DFS程序过程，不用递归方法，而是使用一个栈来实现

代码给出比较麻烦.给个思想吧.
需要一个数组记录每个节点是否被访问过.设为tag[]吧
需要一个栈保存避免递归, 设为stack[]
1.节点i入栈stack[]
2.置tag[i]为1表示i被访问过了.
3.while(栈非空)
{
if(stack顶的元素还有没有被访问的节点j)
访问节点j, tag[j]=1, 节点j入栈;
else
顶部节点出栈;
}

Ⅱ 入栈顺序是1234,出栈序列有哪几种

4个元素的全排列共有24种，栈要求符合后进先出，按此衡量排除后即得：

1234√，1243√，1324√，1342√，1423×，1432√，2134√，2143√，2314√ ，2341√，

2413×，2431√，3124×，3142×，3214√，3241√，3412×，3421√，4123×，4132×，

4213×，4231×，4312×，4321√。

14种可能，10种不可能。

(2)dfs算法入栈的过程扩展阅读

栈的典型应用有算术表达式的检查和背包问题等，实际上，凡属符合后进先出原则的问题，都可以用栈来处理。

1、算术表达式中括号作用域合法性的检查

括号作用域的检查是栈的典型实例。检查一个算术表达式中使用的括号是否正确，应从下面两个方面考虑：

1）左右括号的数目应该相等；

2）每一个左括号都一定有一个右括号与之匹配。

算法思想：括号作用域检查的原则是，对表达式从左到右扫描。当遇到左括号时，左括号入栈；当遇到右括号时，首先将栈顶元素弹出栈，再比较弹出元素是否与右括号匹配，若匹配，则操作继续；否则，查出错误，并停止操作。

2、背包问题

问题：假设有n件质量分配为w1，w2，...，wn的物品和一个最多能装载总质量为T的背包，能否从这n件物品中选择若干件物品装入背包，使得被选物品的总质量恰好等于背包所能装载的最大质量，即wi1+wi2+...+wik=T。若能，则背包问题有解，否则无解。

算法思想：首先将n件物品排成一列，依次选取；若装入某件物品后，背包内物品的总质量不超过背包最大装载质量时，则装入（进栈）；否则放弃这件物品的选择，选择下一件物品试探，直至装入的物品总和正好是背包的最大转载质量为止。这时我们称背包装满。

若装入若干物品的背包没有满，而且又无其他物品可以选入背包，说明已装入背包的物品中有不合格者，需从背包中取出最后装入的物品（退栈），然后在未装入的物品中挑选，重复此过程，直至装满背包（有解），或无物品可选（无解）为止。

具体实现：设用数组weight[1..N]，stack[1,N]分别存放物品重量和已经装入背包（栈）的物品序号，MaxW表示背包的最大装载量。每进栈一个物品，就从MaxW中减去该物品的质量,设i为待选物品序号。

若MaxW-weight[i]>=0，则该物品可选；若MaxW-weight[i] < 0，则该物品不可选,且若i>n，则需退栈，若此时栈空，则说明无解。

Ⅲ dfs算法是什么

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

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

DFS思路：

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

Ⅳ 怎么给小白讲解存储系统

仅供参考

给小白讲解网络存储系统，给小白讲解网络存储系统主要是让他们明确地认识到同一处系统变多变少的过程。
1.从图中某个顶点v出发，访问v;
2.找出刚访问过得顶点的第一个未被访问的邻接点，访问该顶点。以该顶点为新顶点，重复此步骤，直至访问过的顶点没有未被访问的邻接点为止。
3.返回前一个访问过的且乃有未被访问的邻接点的顶点，找出下一个未被访问的邻接点，访问该顶点。
4.重复（2）（3），直至所以的顶点都被访问过，搜索结束。

深度优先搜索遍历连通图
1）从图中某个顶点出发，访问v，并置visited[v]的值为true.
2) 依次检查v的所有的邻接点w，如果visited[w]的值为false,再从w出发进行递归遍历，直至图中所有的顶点都被访问过。
代码实现如下：
bool visited[maxn];//访问标志数组，初值为false;void DFS(Graph G,int v){//从顶点v出发递归的深度优先遍历图G
cout<<v;
visited[v] = true;
for(顶点v的第一个邻接顶点w;w >= 0;下一个邻接点)
if(!visited[w]) DFS(G,w);//对v尚未访问的邻接点w递归调用DFS;}

那么对于非连通图的遍历，我们可以看做是一个个连通分量，循环调用多少次，那么就有多少个连通分量。 用深度优先遍历非连通图
void DFS(Graph G){//对非连通图G做深度优先遍历
for(v = 0;v < G.num;++v) visited[v] = false;
for(v = 0;v < G.num; ++v)//循环调用连通图遍历
if(!visited[v]) DFS(G,v);// 对未访问的顶点调用DFS；}

我们知道，在调用DFS之前，我们需要选择合适的存储方式把我们的图存起来。
常见的存图方式有如下：
采用邻接矩阵表示图的深度优先搜索遍历
void DFS(Graph G,int v){//图G为邻接矩阵类型，从第v个顶点出发深度优先搜索遍历图G
cout<<v;
visited[v] = 1;
for(w = 0 ;w < G.num;w++)//依次检查邻接矩阵v所在的行
if((G.arcs[v][w] != 0)&&(!visted[w]))//G.arcs[v][w]表示w是v的邻接点，如果w未被访问，则递归调用DFS
DFS(G,w);}

采用邻接表表示的图深度优先搜索遍历
void DFS(Graph G,int v){
cout<<v;
visited[v] = 1;
p = G.vertices[v].firstarc;//p指向v的边链表的第一个节点
while(p != NULL){//边链表非空

w = p -> adjvex;//如果w是v的邻接点
if(!visited[w]) DFS(G,w);//如果w未访问，则递归调用DFS；

p = p -> nextarc;//指向下一个边结点
}}

好了，最基础的理论知识我们已经了解完了，接下来我们要跟深一步了解这个算法，并写代码做题了
DFS算法思想：一直往深处走，直到找到解或者走不下去为止；
一般DFS使用栈保存未被检测的结点，结点深度优先的次序被访问并被依次压入栈中，并以相反的次序出栈进行新的检测。
深搜解决栗子：走迷宫。不撞南墙不回头！
下面是我做题的一个基础模板！
#include<bits/stdc++.h>using namespace std;const int maxn = 100;bool vis[maxn][maxn];//访问标记int mapp[maxn][maxn];//坐标范围bool check(int x,int y){//边界条件和约束条件的判断
if(!vis[x][y] && ...)//满足条件
return 1;
else
return 0;}void DFS(int x,int y){
vis[x][y] = 1;//标记该节点被访问
if(mapp[x][y] == G){//出现目标态G
...//做相应处理
return ;
}
for(int i=0;i<4;i++){
if(check(x + dir[i][0],y+dir[i][1]))//按照规矩生成下一个节点
DFS(x + dir[i][0],y+dir[i][1]);
}
return ;//没有下层搜索节点，回溯}int main(){
.....

Ⅳ 求dfs算法的pascal程序！谢谢！

我做的几道DFS题：

这是两道中国象棋的DFS：
const di:array[1..4]of integer=(1,2,2,1);
dj:array[1..4]of integer=(2,1,-1,-2);
var dep,i,j:integer;x,y:array[0..20]of integer;
procere print(dep:integer);
var r:integer;
begin
for r:=1 to dep-1 do write('(',x[r],',',y[r],')=>');
writeln('(',x[dep],',',y[dep],')');
end;
procere try(dep,i,j:integer);
var ni,nj,r:integer;
begin
for r:=1 to 4 do begin
ni:=i+di[r];nj:=j+dj[r];
if (ni<=8) and (nj<=4) and (ni>0) and (nj>0) then begin
x[dep]:=ni;y[dep]:=nj;
if (ni=8) and (nj=4) then print(dep) else try(dep+1,ni,nj);
end;
end;
end;
begin
x[0]:=0;y[0]:=0;try(1,0,0);
end.

const n=5;m=4;
fx:array [1..8,1..2] of -2..2=((1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2));
var dep,i,x,y,cont:integer;a:array [1..n,1..m] of integer;
procere output;
var x,y:integer;
begin
inc(cont);writeln;writeln('count=',cont);
for y:=1 to n do begin
for x:=1 to m do write(a[y,x]:3);writeln;
end;
end;
procere find(y,x,dep:integer);
var i,xx,yy:integer;
begin
for i:=1 to 8 do begin
xx:=x+fx[i,1];yy:=y+fx[i,2];
if (xx in [1..m]) and (yy in [1..n]) and (a[yy,xx]=0) then begin
a[yy,xx]:=dep;
if (dep=n*m) then output
else find(yy,xx,dep+1);
a[yy,xx]:=0;
end;
end;
end;
begin
cont:=0;fillchar(a,sizeof(a),0);dep:=1;write('input x,y:');readln(x,y);
if (y>n) or(x>m) then begin writeln('x,y error!');halt;end;
a[y,x]:=1;find(y,x,2);
if cont=0 then writeln('No answer!') else write('The End!');readln;
end.

一笔画问题（DFS）：
program myone;
const n=6;
type stack=record
d:array[1..32]of integer;t:integer;
end;
var s:stack;x,y,t:integer;g,v:array[1..n,1..n]of boolean;
procere print;
var i:integer;
begin
for i:=1 to s.t-1 do write(s.d[i],'->');
writeln(s.d[s.t]);
end;
function examine:boolean;
var i,j:integer;
begin
examine:=true;
for i:=1 to n do for j:=1 to n do if v[i,j]=g[i,j] then begin
examine:=false;exit;
end;
end;
procere dfs(i:integer);
var j:integer;
begin
if examine then begin print;exit;end;
for j:=1 to n do if (g[i,j])and(v[i,j]) then begin
v[i,j]:=false;v[j,i]:=false;inc(s.t);s.d[s.t]:=j;
dfs(j);v[i,j]:=true;v[j,i]:=true;dec(s.t);
end;
end;
begin
assign(input,'myone.in');reset(input);
assign(output,'myone.out');rewrite(output);
fillchar(g,sizeof(g),false);fillchar(v,sizeof(v),true);
for x:=1 to n do for y:=1 to n do begin
read(t);if t>0 then g[x,y]:=true;
end;close(input);
s.t:=1;s.d[1]:=5;dfs(5);close(output);
end.

航班问题，摘自《The Art Of Java》
program plane(input,output);
const max=100;
type al=record pass:array [1..max] of integer;total:integer; end;
ways=record tw:integer;distance:array [1..max] of integer;
wname:array [1..max] of string; end;
var city:array [0..max,0..max] of integer;fly:al;way:ways;
cityname:array [0..max] of string;v:array [0..max] of boolean;
t,i,j,n,c,co,d:integer;f:text;s1,s2,W:string;ch1,ch2:char;
function locaten(N:string):integer;
var i:integer;
begin
for i:=1 to t do if cityname[i]=N then begin
locaten:=i;exit;
end;
locaten:=-1;
end;
procere print;
var i:integer;
begin
inc(way.tw);
for i:=1 to fly.total-1 do begin
write(cityname[fly.pass[i]],' to ');
way.wname[way.tw]:=way.wname[way.tw]+cityname[fly.pass[i]]+' to '
end; writeln('LosAngeles distance is ',d);
way.wname[way.tw]:=way.wname[way.tw]+'LosAngeles distance is ';way.distance[way.tw]:=d;
end;
procere Printleast;
var i,saved,saven:integer;
begin
saved:=maxint;
for i:=1 to way.tw do if way.distance[i]<saved then begin
saved:=way.distance[i];saven:=i; end;
writeln('The nearest way is:',way.wname[saven],saved);
end;
procere try(i:integer);
var j:integer;
begin
v[i]:=true;inc(fly.total);fly.pass[fly.total]:=i;
if i=locaten('LosAngeles') then print;
for j:=1 to t do if not(v[j]) and (city[i,j]>0) then begin
inc(d,city[i,j]);try(j);
v[j]:=false;dec(d,city[i,j]);dec(fly.total);
end;
end;
begin
t:=0;s1:='';s2:='';assign(f,'E:\ff\timetable.txt');reset(f);
while not(eof(f)) do begin
read(f,ch1);
while ch1<>' ' do begin
s1:=s1+ch1;read(f,ch1);
end; read(f,ch2);
while ch2<>' ' do begin
s2:=s2+ch2;read(f,ch2);
end; readln(f,co);
if (locaten(s1)=-1) and (locaten(s2)=-1) then begin
inc(t);cityname[t]:=s1;inc(t);cityname[t]:=s2;city[t-1,t]:=co;
end;
if (locaten(s1)=-1) and (locaten(s2)<>-1) then begin
inc(t);cityname[t]:=s1;city[t,locaten(s2)]:=co;
end;
if (locaten(s1)<>-1) and (locaten(s2)=-1) then begin
inc(t);cityname[t]:=s2;city[locaten(s1),t]:=co;
end;
if (locaten(s1)<>-1) and (locaten(s1)<>-1) then city[locaten(s1),locaten(s2)]:=co;
s1:='';s2:='';
end;close(f);
reset(f);while not(eof(f)) do begin readln(f,W);write(W,'|'); end;
writeln;close(f);
for i:=1 to t do begin for j:=1 to t do write(city[i,j]:6);writeln; end;
fillchar(v,sizeof(v),false);d:=0;fly.total:=0;way.tw:=0;
try(locaten('NewYork'));printleast;readln;
end.

这是最基本的DFS题：
program allotbook;
const max=100;
var like:array [0..max,0..max] of 0..1;book:array [0..max] of integer;
flag:set of 1..100;i,j,n,c:integer;f:text;

procere print;
var i:integer;
begin
inc(c);writeln('answer',c,':');
for i:=1 to 5 do writeln(chr(64+book[i]));
end;

procere try(i:integer);
var j:integer;
begin
for j:=1 to 5 do
if not(j in flag) and (like[i,j]=1) then begin
flag:=flag+[j];book[i]:=j;
if i=5 then print else try(i+1);
flag:=flag-[j];
end
end;

begin
assign(f,'d:\book.in');reset(f);readln(f,n);
for i:=1 to n do begin
for j:=1 to n do read(f,like[i,j]);
readln(f);
end;close(f);
flag:=[];c:=0;try(1);readln;
end.

Ⅵ 简述什么是堆栈，以及堆栈中入栈，出栈的过程

堆栈其实是两种数据结构。堆栈都是一种数据项按序排列的数据结构，只能在一端
(称为栈顶(top))
对数据项进行插入和删除。要点：堆，顺序随意。栈，后进先出(Last-In/First-Out)。

针对栈这种数据结构的基本操作有两种：压栈和弹出，
在栈帧中包含两个标志----栈底和栈顶，其中栈顶标识着要push或pop
的数据的地址，而栈底则表示栈帧中最后一个数据的内存地址。

在Win32中，寄存器esp存放着栈底指针，栈是向低地址方向生长，
因此esp指向栈顶元素
堆栈对比（操作系统）：
由编译器自动分配释放，存放函数的参数值，局部变量的值等。其
操作方式类似于数据结构中的栈栈使用的是一级缓存，

通常都是被调用时处于存储空间中，调用完毕立即释放

堆（操作系统）：
一般由程序员分配释放，

若程序员不释放，程序结束时可能由OS回收，分配方式倒是类似于链表。

堆则是存放在二级缓存中，生命周期由虚拟机的垃圾回收算法来决定（并不是一旦成为孤儿对象就能被回收）。所以调用这些对象的速度要相对来得低一些

堆（数据结构）
：堆可以被看成是一棵树，如：堆排序

栈（数据结构）
：一种后进先出的的数据结构

具体不同语言有不同的描述，可查看各种语言的api

Ⅶ 数据结构问题：图的深度优先遍历中有递归的应用，要用到栈，图中顶点是如何出栈进栈的是进栈时访问还是

首先你得明白函数调用本身就是通过栈来实现的。 调用函数是入栈，而函数返回是出栈。
为什么是栈， 你要知道栈的特性是 “后进先出”或者是“先进后出”， 而对于函数调用来说， 一定会有最先调用的函数，最后才返回。 举个例子： 函数a,b,c,d的调用关系是a调用b，b又调用c，c又调用d， 那么当d函数执行完后，它会返回到c，同时c执行完成后返回到b，最后返回到a。
所以函数调用的顺序是a->b->c->d
函数返回的顺序是d->c->b->a
很明显 想要实现这种效果就要依靠栈。
因此函数调用过程是有一个叫做“调用栈”来实现的。
递归函数同理，只不过上边的a,b,c,d全变成同一个函数a->a->a->a，为了人为能区分清楚，不防给a函数加上角标，来标记是第几层调用a1->a2->a3->a4 ，返回时a4->a3->a2->a1 这就是递归函数调用返回过程。
接下来 深度优先搜索（dfs）本身就是靠函数递归调用实现的。
对于一个图来说，是由结点和边构成的， 在存储时就需要用到
struct node {
int data;
struct node * next[CNT];
}
上边只是一种简单的定义，对一个结点来说主要就是2部分， 一为它所存的数据是什么（数据域），二为它能指向哪些其它的边（指针域）。
你问了这样的问题：这些顶点怎么进出栈？又是如何访问的？
这里我要解释下访问的意义， 访问应该是对节点的数据域进行某种操作， 一定要理解这句话，是对数据域进行某种操作， 对于上边定义的结构 data就是数据域， 我需要对data进行某种操作，比如调用printf输出data， 这就是一种操作， 而只有对data进行了printf之后才能说“访问了这个结点”， 否则，单纯的使用了节点的指针域不能说访问了节点。
因此，如何访问节点的， 什么时候访问的，就要由你来定，
如果是下面这样的写法：
void dfs(struct node* n)
{
if (n->next[0] == NULL) {
return ;
}
for (int i = 0; n->next[i] != NULL; i++) {
dfs(n->next[i]);

}
printf ("%d\n", n->data);
}
你可以看到，printf是在 dfs函数递归调用 “返回”的时候才会被调用，换句话说， 图中所有节点在从开始走到不能再往下走的一个节点时(某个节点没有指向其它指点的边了），返回，同时输出该节点的data。 这种情况下是“出栈时访问”
而当printf换到if语句前头时，则是“入栈时访问”。
这如同二叉数的三种顺序遍历，前、中、后序遍历区别在于 何时访问节点
如下是前序遍历
void preorder(node* n)
{
printf(n->data);

preorder(n->left);
preorder(n->right);

}
如下是后序遍历
void afterorder(node* n)
{
afterorder(n->left);
afterorder(n->right);

printf(n->data);
}
如下是中序遍历
void inorder(node* n)
{
inorder(n->left);
printf(n->data);
inorder(n->right);
}

Ⅷ 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”一致）：；