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;
}
『貳』 數據結構圖的遍歷 1)先任意創建一個圖； 2)圖的DFS,BFS的遞歸和非遞歸演算法的實現 3)要求用有向圖和無向圖
//DFS,無向圖+有向圖，鄰接矩陣實現。
//你的東西太多了。一個一個問吧。而且200分太少了。你這么多種情況。至少也得寫8種吧。
#include<string>
#include<string.h>
#include<stdio.h>
#include<vector>
#include<iostream>
#include<set>
#include<math.h>
#include<map>
#include<algorithm>
#include<queue>
usingnamespacestd;
constintMAX=210000;
intmat[10][10];
boolvis[10]={false};
voidDFS(ints,intn)
{
inti;
vis[s]=true;
printf("%d",s);
for(i=0;i<n;i++)
{
if(mat[s][i]&&!vis[i])
{
DFS(i,n);
}
}
}
intmain()
{
inti,n;
intj;
n=10;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
mat[i][j]=1;
}
DFS(0,n);
return0;
}
/*
*/
『叄』 深度優先法(DFS)演算法
從根節點開始，順著它的某一子節點往下搜，所以再下一個是這個子節點的某一子節點，所以是個遞歸形式，當搜到子節點為NULL或者已經訪問過了，於是回退到上一次的節點，若它還有沒訪問過的子節點繼續往下搜，重復上述。當最後退回到根節點時，說明全部訪問完畢，遍歷完成。
『肆』 數據結構C語言版 圖的遍歷 DFS和BFS演算法，用鄰接矩陣儲存 急阿在線等 求大神指點
#include <iostream>
#include<string.h>
#include<stack>
#include<queue>
const int Max=100;
const int VISITED=101010;
const int UNVISITED=111111;
const int AFFINITY=101010;
const int INFINITY=111111;
using namespace std;
class Edge
{
public:
int start;
int end;
int weight;
Edge(int st=0,int en=0,int w=0):start(st),end(en),weight(w){}
bool operator>(Edge oneEdge){return weight>oneEdge.weight?true:false;}
bool operator<(Edge oneEdge){return weight<oneEdge.weight?true:false;}
bool operator!=(Edge oneEdge)
{
if(weight!=oneEdge.weight||start!=oneEdge.start||end!=oneEdge.end)
return true;
return false;
}
};
class AdjGraf
{
private:
int verticesNum;
int edgeNum;
int **matrix;
int *Mark;
public:
AdjGraf(int vert)
{
int i=0,j=0;
verticesNum=vert;
matrix=(int**)new int*[vert];
for(i=0;i<vert;i++)
matrix[i]=new int[vert];
Mark=new int[vert];
for(i=0;i<vert;i++)
for(j=0;j<vert;j++)
{
matrix[i][j]=0;
}
for( int m=0;m<verticesNum;m++)
Mark[m]=UNVISITED;
}
~AdjGraf();
//返回與頂點oneVertex相關聯的第一條邊
Edge FirstEdge(int oneVertex);
//返回與邊PreEdge有相同關聯頂點oneVertex的下一條邊
Edge NextEdge( Edge preEdge);
//添加一條邊
void setEdge(int fromVertex,int toVertex,int weight);
//刪一條邊
void delEdge(int fromVertex,int toVertex);
//如果oneEdge是邊則返回TRUE，否則返回FALSE
bool IsEdge( Edge oneEdge)
{
if(oneEdge.start>=0&&oneEdge.start<verticesNum&&
oneEdge.end>=0&&oneEdge.end<verticesNum)
return true;
else return false;
}
//返回邊oneEdge的始點
int FromVertex(Edge oneEdge){return oneEdge.start;}
//返回邊oneEdge的終點
int ToVertex(Edge oneEdge){return oneEdge.end;}
//返回邊oneEdge的權
int Weight(Edge oneEdge){return oneEdge.weight;}
void visit(int i){cout<<i+1<<" ";}
void BFS(int i=1);
void DFS(int i);
void DFSTraverse(int v);
void DFSNoReverse(int f=1);
Edge UNVISITEDEdge(int f);
};
AdjGraf::~AdjGraf()
{
for(int i=0;i<verticesNum;i++)
delete[]matrix[i];
delete[]matrix;
}
Edge AdjGraf::FirstEdge(int oneVertex)
{ int i;
Edge tempEdge;
tempEdge.start=oneVertex;
for( i=0;i<verticesNum;i++)
if(matrix[oneVertex][i]!=0)
break;
tempEdge.end=i;
tempEdge.weight=matrix[oneVertex][i];
return tempEdge;
}
Edge AdjGraf ::NextEdge( Edge preEdge)
{
Edge tempEdge;
tempEdge.start=preEdge.start;
int i=0;
for(i=preEdge.end+1;i<verticesNum;i++)
if(matrix[preEdge.start][i]!=0)
break;
tempEdge.end=i;
tempEdge.weight=matrix[preEdge.start][i];
return tempEdge;
}
void AdjGraf::setEdge(int fromVertex,int toVertex,int weight)
{
if(matrix[fromVertex-1][toVertex-1]==0)
edgeNum++;
matrix[fromVertex-1][toVertex-1]=weight;
}
void AdjGraf::delEdge(int fromVertex,int toVertex)
{
if(matrix[fromVertex][toVertex]==0)
edgeNum--;
matrix[fromVertex][toVertex]=0;
}
/*************遞歸實現深度優先****************/
void AdjGraf::DFS(int i)
{
visit(i);
Mark[i]=VISITED;
for(Edge e=FirstEdge(i);IsEdge(e);e=NextEdge(e))
if(Mark[ToVertex(e)] == UNVISITED)
DFS(ToVertex(e));
}
void AdjGraf::DFSTraverse(int v)
{
v--;
int i;
for(i=0;i<verticesNum;i++)
Mark[i]=UNVISITED;
for(i=v;i<v+verticesNum;i++)
if (Mark[i]== UNVISITED)
DFS(i);
}
Edge AdjGraf::UNVISITEDEdge(int f)
{ int i;
for( Edge e=FirstEdge(f);IsEdge(e);e=NextEdge(e))
if(Mark[e.end]==UNVISITED)
return e;
return Edge(verticesNum,verticesNum,0) ;
}
/*************非遞歸實現深度優先**************/
void AdjGraf::DFSNoReverse(int f)
{
f--;
int i,counter=0,j,flag;
stack<int>Temp;
for(i=0;i<verticesNum;i++)
Mark[i]=UNVISITED;
flag=f;
while(counter<12)
{
while(flag!=verticesNum&&IsEdge(UNVISITEDEdge(flag))||!Temp.empty())
{
// Edge tempEdge=UNVISITEDEdge(j);
while(flag!=verticesNum&&Mark[flag]==UNVISITED)
{
visit(flag);
Mark[flag]=VISITED;
Temp.push(flag);
flag=UNVISITEDEdge(flag).end;
}
if(!Temp.empty())
{
flag=UNVISITEDEdge(Temp.top()).end;
Temp.pop();
}
}
if(Mark[counter]==UNVISITED) flag=counter;
else counter++;
}
}
/*************非遞歸實現廣度優先**************/
void AdjGraf::BFS(int v)
{
int i;
v--;
for( i=0;i<verticesNum;i++)
Mark[i]=UNVISITED;
queue<int>tempqueue;
i=0;
/*********v先從指定位置開始，然後從v=0,1,2......
依次檢查是否有孤立結點*****************/
while(i<verticesNum)
{
tempqueue.push(v);
while(!tempqueue.empty())
{
v=tempqueue.front();
tempqueue.pop();
if(Mark[v]==UNVISITED)
{
visit(v);
Mark[v]=VISITED;
for(Edge e=FirstEdge(v);IsEdge(e);e=NextEdge(e))
{
v=ToVertex(e);
tempqueue.push(v);
}
}
}
/***********防止出現孤立點****************/
if(Mark[i]==VISITED) i++;
else v=i;
}
}
int main()
{
AdjGraf Graph(12);
Graph.setEdge(1,2,1);
Graph.setEdge(2,1,1);
Graph.setEdge(1,3,5);
Graph.setEdge(3,1,5);/** V1 V12 V11 */
Graph.setEdge(2,4,3);/** / \ / \ */
Graph.setEdge(4,2,3);/** v2 v3 V10 V9 */
Graph.setEdge(2,5,7);/** / \ / \ */
Graph.setEdge(5,2,7);/** v4 v5 v6-v7 */
Graph.setEdge(4,8,4);/** \ / */
Graph.setEdge(8,4,4);/** v8 */
Graph.setEdge(5,8,3);
Graph.setEdge(8,5,3);
Graph.setEdge(3,6,2);
Graph.setEdge(6,3,2);
Graph.setEdge(3,7,1);
Graph.setEdge(7,3,1);
Graph.setEdge(6,7,6);
Graph.setEdge(7,6,6);
Graph.setEdge(12,9,6);
Graph.setEdge(9,12,6);
Graph.setEdge(12,10,6);
Graph.setEdge(10,12,6);
Graph.setEdge(11,11,6);
cout<<"DFSTraverse:"<<endl;
Graph.DFSTraverse(3);
cout<<endl;
cout<<"DFSNoReverse:"<<endl;
Graph.DFSNoReverse(3);
cout<<endl;
cout<<"BFS:"<<endl;
Graph.BFS(3);
cout<<endl;
return 0;
}
以上代碼運行環境codeblocks 程序採用DFS遞歸演算法 DFS非遞歸演算法 BFS非遞歸演算法
望採納~
『伍』 演算法分析DFS求解
上網上查一查，這樣的題我也不會。
『陸』 如何修改基於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」一致）：；
『柒』 圖的DFS遍歷 先任意創建一個圖； 圖的DFS的遞歸和非遞歸演算法的實現 用鄰接矩陣、鄰接表兩種結構存儲實現
java">packagecom.graphic;
publicclassDFS_Graph{
/**
*@paramargs
*/
publicstaticvoidmain(String[]args){
intmatrix[][]={{0,1,0,0,1},{1,0,1,1,1},
{0,1,0,1,0},{0,1,1,0,1},{1,1,0,1,0}};
DFS_Graphgraph=newDFS_Graph();
graph.init(matrix);
}
inttime=0;
GNodearray[];
publicvoidinit(intmatrix[][]){
array=newGNode[matrix.length];
for(inti=0;i<array.length;i++)//初始化
{
array[i]=newGNode(i);
}
for(inti=0;i<array.length;i++){
if(array[i].color.equals("w"))
{
DFS(array[i],matrix,array);
for(intj=0;j<array.length;j++)
{
if(j>0)
{
System.out.println(array[j].id+"color="+array[j].color
+"d_time="+array[j].d_time+"f_time="
+array[j].f_time+"par="+array[j].par.id);
}
else
{
System.out.println(array[j].id+"color="+array[j].color
+"d_time="+array[j].d_time+"f_time="
+array[j].f_time);
}
}
System.out.println();
System.out.println();
}
}
//DFS(array[0],matrix,array);
}
publicvoidDFS(GNodeu,intmatrix[][],GNodearray[]){
u.color="g";
time++;
u.d_time=time;
for(inti=0;i<matrix.length;i++){
if(matrix[u.id][i]==1&&array[i].color.equals("w")){
array[i].par=u;
DFS(array[i],matrix,array);
}
}
u.color="b";
time++;
u.f_time=time;
}
}
classGNode{
Stringcolor;//color=black沒有訪問，//color=gray正在訪問//color=black已經訪問結束了
intid;
intd_time;
intf_time;
GNodepar;
publicGNode(){
}
publicGNode(intid){
this.color="w";
this.d_time=0;
this.f_time=0;
this.par=null;
this.id=id;
}
}
別人寫的代碼你可能不容易理解的。給你個參考吧：演算法導論第二版22章，圖的基本演算法，裡面有關於圖的DFS和BFS演算法。代碼是用偽代碼寫的，但是講解很詳細，慢慢看，就當做學習的過程吧。
『捌』 分別用DFS和BFS演算法給電腦設置AI(JAVA)
有必勝策略的吧。。狀態空間的上限是3^9也就是不到20000實際上沒有這么多。所以直接採用BFS標記會比較好。演算法的話就是填充表，把表（九個格子）填為必勝、必敗，己勝，開始的時候全部標為必敗，再從勝狀態開始向回BFS（或者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);
}
}
}
『拾』 c++DFS演算法問題。
這個題是比較基本的DFS問題，建議你自己多看多試一下，自己做出來意義更大一點。我想提供給你另外一種思路，時間復雜度更低，對於每個坐標（X，Y）可以從（x-1，y）和（x，y-1）到達，所以到這一點的可能數就是到達兩個先驅點的方案數量的和，把黑洞設置成0就行了