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