圖深度搜索演算法

Ⅰ 深度優先搜索的詳細解釋

事實上，深度優先搜索屬於圖演算法的一種，英文縮寫為DFS即Depth First Search.其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，而且每個節點只能訪問一次.
舉例說明之：下圖是一個無向圖，如果我們從A點發起深度優先搜索（以下的訪問次序並不是唯一的，第二個點既可以是B也可以是C,D），則我們可能得到如下的一個訪問過程：A->B->E（沒有路了！回溯到A)->C->F->H->G->D（沒有路，最終回溯到A,A也沒有未訪問的相鄰節點，本次搜索結束）.簡要說明深度優先搜索的特點：每次深度優先搜索的結果必然是圖的一個連通分量.深度優先搜索可以從多點發起.如果將每個節點在深度優先搜索過程中的"結束時間"排序（具體做法是創建一個list，然後在每個節點的相鄰節點都已被訪問的情況下，將該節點加入list結尾，然後逆轉整個鏈表)，則我們可以得到所謂的"拓撲排序",即topological sort.

Ⅱ 圖的深度優先搜索演算法dfs函數裡面firstadjvex是什麼意思

FirstAdiVex(G,v);
初始條件：圖G存在，v是G中某個頂點。
操作結果：返回v的第一個領接頂點，若定點在G中沒有領接頂點，則返回空。

Ⅲ 圖的深度優先搜索和廣度優先搜索演算法的實現

//圖的遍歷演算法程序

//圖的遍歷是指按某條搜索路徑訪問圖中每個結點，使得每個結點均被訪問一次，而且僅被訪問一次。圖的遍歷有深度遍歷演算法和廣度遍歷演算法，程序如下：
#include <iostream>
//#include <malloc.h>
#define INFINITY 32767
#define MAX_VEX 20 //最大頂點個數
#define QUEUE_SIZE (MAX_VEX+1) //隊列長度
using namespace std;
bool *visited; //訪問標志數組
//圖的鄰接矩陣存儲結構
typedef struct{
char *vexs; //頂點向量
int arcs[MAX_VEX][MAX_VEX]; //鄰接矩陣
int vexnum,arcnum; //圖的當前頂點數和弧數
}Graph;
//隊列類
class Queue{
public:
void InitQueue(){
base=(int *)malloc(QUEUE_SIZE*sizeof(int));
front=rear=0;
}
void EnQueue(int e){
base[rear]=e;
rear=(rear+1)%QUEUE_SIZE;
}
void DeQueue(int &e){
e=base[front];
front=(front+1)%QUEUE_SIZE;
}
public:
int *base;
int front;
int rear;
};
//圖G中查找元素c的位置
int Locate(Graph G,char c){
for(int i=0;i<G.vexnum;i++)
if(G.vexs[i]==c) return i;
return -1;
}
//創建無向網
void CreateUDN(Graph &G){
int i,j,w,s1,s2;
char a,b,temp;
printf("輸入頂點數和弧數:");
scanf("%d%d",&G.vexnum,&G.arcnum);
temp=getchar(); //接收回車
G.vexs=(char *)malloc(G.vexnum*sizeof(char)); //分配頂點數目
printf("輸入%d個頂點.\n",G.vexnum);
for(i=0;i<G.vexnum;i++){ //初始化頂點
printf("輸入頂點%d:",i);
scanf("%c",&G.vexs[i]);
temp=getchar(); //接收回車
}
for(i=0;i<G.vexnum;i++) //初始化鄰接矩陣
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=INFINITY;
printf("輸入%d條弧.\n",G.arcnum);
for(i=0;i<G.arcnum;i++){ //初始化弧
printf("輸入弧%d:",i);
scanf("%c %c %d",&a,&b,&w); //輸入一條邊依附的頂點和權值
temp=getchar(); //接收回車
s1=Locate(G,a);
s2=Locate(G,b);
G.arcs[s1][s2]=G.arcs[s2][s1]=w;
}
}
//圖G中頂點k的第一個鄰接頂點
int FirstVex(Graph G,int k){
if(k>=0 && k<G.vexnum){ //k合理
for(int i=0;i<G.vexnum;i++)
if(G.arcs[k][i]!=INFINITY) return i;
}
return -1;
}
//圖G中頂點i的第j個鄰接頂點的下一個鄰接頂點
int NextVex(Graph G,int i,int j){
if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum){ //i,j合理
for(int k=j+1;k<G.vexnum;k++)
if(G.arcs[i][k]!=INFINITY) return k;
}
return -1;
}
//深度優先遍歷
void DFS(Graph G,int k){
int i;
if(k==-1){ //第一次執行DFS時,k為-1
for(i=0;i<G.vexnum;i++)
if(!visited[i]) DFS(G,i); //對尚未訪問的頂點調用DFS
}
else{
visited[k]=true;
printf("%c ",G.vexs[k]); //訪問第k個頂點
for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))
if(!visited[i]) DFS(G,i); //對k的尚未訪問的鄰接頂點i遞歸調用DFS
}
}
//廣度優先遍歷
void BFS(Graph G){
int k;
Queue Q; //輔助隊列Q
Q.InitQueue();
for(int i=0;i<G.vexnum;i++)
if(!visited[i]){ //i尚未訪問
visited[i]=true;
printf("%c ",G.vexs[i]);
Q.EnQueue(i); //i入列
while(Q.front!=Q.rear){
Q.DeQueue(k); //隊頭元素出列並置為k
for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w))
if(!visited[w]){ //w為k的尚未訪問的鄰接頂點
visited[w]=true;
printf("%c ",G.vexs[w]);
Q.EnQueue(w);
}
}
}
}

//主函數
void main(){
int i;
Graph G;
CreateUDN(G);
visited=(bool *)malloc(G.vexnum*sizeof(bool));
printf("\n廣度優先遍歷: ");
for(i=0;i<G.vexnum;i++)
visited[i]=false;
DFS(G,-1);
printf("\n深度優先遍歷: ");
for(i=0;i<G.vexnum;i++)
visited[i]=false;
BFS(G);
printf("\n程序結束.\n");
}
輸出結果為（紅色為鍵盤輸入的數據，權值都置為1）：
輸入頂點數和弧數:8 9
輸入8個頂點.
輸入頂點0:a
輸入頂點1:b
輸入頂點2:c
輸入頂點3:d
輸入頂點4:e
輸入頂點5:f
輸入頂點6:g
輸入頂點7:h
輸入9條弧.
輸入弧0:a b 1
輸入弧1:b d 1
輸入弧2:b e 1
輸入弧3:d h 1
輸入弧4:e h 1
輸入弧5:a c 1
輸入弧6:c f 1
輸入弧7:c g 1
輸入弧8:f g 1
廣度優先遍歷: a b d h e c f g
深度優先遍歷: a b c d e f g h
程序結束.

已經在vc++內運行通過，這個程序已經達到要求了呀~

Ⅳ 數據結構，圖的深度搜索和廣度搜索，求代碼

深度優先遍歷：
#include <stdio.h>
#include <malloc.h>

#define INFINITY 32767
#define MAX_VEX 20 //最大頂點個數

bool *visited; //訪問標志數組

//圖的鄰接矩陣存儲結構
typedef struct{
char *vexs; //頂點向量
int arcs[MAX_VEX][MAX_VEX]; //鄰接矩陣
int vexnum,arcnum; //圖的當前頂點數和弧數
}Graph;

//圖G中查找元素c的位置
int Locate(Graph G,char c){
for(int i=0;i<G.vexnum;i++)
if(G.vexs[i]==c) return i;
return -1;
}

//創建無向網
void CreateUDN(Graph &G){
int i,j,w,s1,s2;
char a,b,temp;
printf("輸入頂點數和弧數:");
scanf("%d%d",&G.vexnum,&G.arcnum);
temp=getchar(); //接收回車
G.vexs=(char *)malloc(G.vexnum*sizeof(char)); //分配頂點數目

printf("輸入%d個頂點.\n",G.vexnum);
for(i=0;i<G.vexnum;i++){ //初始化頂點
printf("輸入頂點%d:",i);
scanf("%c",&G.vexs[i]);
temp=getchar(); //接收回車
}

for(i=0;i<G.vexnum;i++) //初始化鄰接矩陣
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=INFINITY;

printf("輸入%d條弧.\n",G.arcnum);
for(i=0;i<G.arcnum;i++){ //初始化弧
printf("輸入弧%d:",i);
scanf("%c %c %d",&a,&b,&w); //輸入一條邊依附的頂點和權值
temp=getchar(); //接收回車
s1=Locate(G,a);
s2=Locate(G,b);
G.arcs[s1][s2]=G.arcs[s2][s1]=w;
}
}

//圖G中頂點k的第一個鄰接頂點
int FirstVex(Graph G,int k){
if(k>=0 && k<G.vexnum){ //k合理
for(int i=0;i<G.vexnum;i++)
if(G.arcs[k][i]!=INFINITY) return i;
}
return -1;
}

//圖G中頂點i的第j個鄰接頂點的下一個鄰接頂點
int NextVex(Graph G,int i,int j){
if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum){ //i,j合理
for(int k=j+1;k<G.vexnum;k++)
if(G.arcs[i][k]!=INFINITY) return k;
}
return -1;
}

//深度優先遍歷
void DFS(Graph G,int k){
int i;
if(k==-1){ //第一次執行DFS時,k為-1
for(i=0;i<G.vexnum;i++)
if(!visited[i]) DFS(G,i); //對尚未訪問的頂點調用DFS
}
else{
visited[k]=true;
printf("%c ",G.vexs[k]); //訪問第k個頂點
for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))
if(!visited[i]) DFS(G,i); //對k的尚未訪問的鄰接頂點i遞歸調用DFS
}
}

//主函數
void main(){
int i;
Graph G;
CreateUDN(G);
visited=(bool *)malloc(G.vexnum*sizeof(bool));
printf("\n深度優先遍歷: ");
for(i=0;i<G.vexnum;i++)
visited[i]=false;
DFS(G,-1);
printf("\n程序結束.\n");
}

輸出結果為（紅色為鍵盤輸入的數據，權值都置為1）：

輸入頂點數和弧數:8 9
輸入8個頂點.
輸入頂點0:a
輸入頂點1:b
輸入頂點2:c
輸入頂點3:d
輸入頂點4:e
輸入頂點5:f
輸入頂點6:g
輸入頂點7:h
輸入9條弧.
輸入弧0:a b 1
輸入弧1:b d 1
輸入弧2:b e 1
輸入弧3:d h 1
輸入弧4:e h 1
輸入弧5:a c 1
輸入弧6:c f 1
輸入弧7:c g 1
輸入弧8:f g 1

深度優先遍歷: a b d h e c f g
程序結束.
廣度優先遍歷：
<一>深度優先搜索(Depth-First Search—DFS)是指按照深度方向搜索,它類似於樹的先根遍歷,是樹的先根遍歷的推廣。
深度優先搜索圖的基本思想是：
假設圖G初態為所有頂點未被訪問（visited[i]=false），從G中任選一頂點vi：
⑴、從該頂點vi出發,首先訪問vi,並置visited [vi ]=true;
⑵、然後依次搜索vi的每一個鄰接點vj；
⑶、若vj未被訪問過，則以vj為新的初始出發點，重復⑴
若vj已被訪問過，則返回到vi另一個鄰接點，重復⑶
⑷、如果經過⑴、⑵、⑶後,圖中仍有未被訪問的頂點,再從中任選一頂點,重復⑴、⑵、⑶,直至所有頂點都被訪問過,遍歷結束。

<二>廣度優先搜索遍歷圖（樹的層次遍歷的推廣）
1.從圖中某頂點v出發，在訪問v之後，
2.依次訪問v的各個未曾被訪問過的鄰接點，
3.然後分別從這些鄰接點出發依次訪問它們的鄰接點，並使「先被訪問的頂點的鄰接點」先於「後被訪問的頂點的鄰接點」被訪問，直至圖中所有已經被訪問的頂點的鄰接點都被訪問到；
4.若圖中尚有頂點未曾被訪問，則另選圖中一個未曾被訪問的頂點作起始點，訪問該頂點，繼續過程2、3,直至圖中所有頂點都被訪問到為止。
(1)為避免重復訪問, 需要一個輔助數組 visited[ n]，給被訪問過的頂點加標記。
(2)為了實現逐層（按頂點的路徑長度遞增）訪問,演算法中需使用了一個隊列,以記憶正在訪問的這一層和下一層的頂點,以便於向下一層訪問。

代碼如下：

#include<iostream.h>
#include<malloc.h>
#define MAX_VERTEX_NUM 20
typedef int InfoType;
typedef int VertexType;
typedef enum{DG,DN,UDG,UDN}GraphKind;

# define MAXQSIZE 100
typedef int QElemType ;//隊列
typedef struct//隊列
{
QElemType *base; // 動態分配存儲空間
int front; // 頭指針，指向隊列頭元素
int rear; // 尾指針，指向 隊列尾元素的下一個位置
}SqQueue;

typedef struct ArcNode//圖
{
int adjex;//該弧所指向的頂點的位置
struct ArcNode *nextarc;//指向下一條弧的指針
InfoType *info;//該弧相關信息的指針
}ArcNode;

typedef struct VNode
{
VertexType data;//頂點信息
ArcNode *firstarc;//指向第一條依附該頂點的弧的指針
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct
{
AdjList vertices;//頂點
int vexnum,arcnum;//圖的當前頂點數和弧數
GraphKind kind;//圖的種類標志
}ALGraph;

int LocateVex(ALGraph G, int v)//確定v在G中位置，即頂點在G.vertices中的序號
{
int i;
for(i=0;i<G.vexnum;i++)
{
if (G.vertices[i].data==v) return i;
}
return -1;

}

// ###################生成圖G的存儲結構-鄰接表###############################################
void CreateGraph(ALGraph &G)
{
int k,sv,tv,i,j;

cout<<"請輸入圖的頂點數(eg:5)";
cin>>G.vexnum;
cout<<"請輸入圖的弧數(eg:6)";
cin>>G.arcnum;
// cout<<"請輸入圖的類型(eg:)";
// cin>>G.kind;// 輸入頂點數、邊數和圖類：1

for(k=0;k<G.vexnum;k++)// 構造頂點數組：2
{
cout<<"請輸入圖的頂點信息";
cin>>G.vertices[k].data;// 輸入頂點
G.vertices[k].firstarc=NULL;//初始化鏈表頭指針為"空"
}

cout<<"請輸入該圖的弧（v1-->v2）,例如：（v1=1,v2=3）,(v1=2,v2=4)"<<endl;
for(k=0;k<G.arcnum;k++)// 輸入各邊並構造鄰接表： 3
{
cout<<"請輸入第"<<k+1<<"條弧的始點信息sv(0<sv<G.vexnum)";
cin>>sv;
cout<<"請輸入第"<<k+1<<"條弧的終點信息tv(0<tv<G.vexnum)";
cin>>tv;// 輸入一條邊（弧）的始點和終點
cout<<endl<<endl;

i = LocateVex(G, sv);
j = LocateVex(G, tv); // (比較)確定sv和tv在G中位置，即頂點在G.vertices中的序號

while((i<0||i>=G.vexnum)||(j<0||j>=G.vexnum)) //if (sv,tv) illegal,again
{
cout<<"請輸入第"<<k+1<<"條弧的始點信息sv(0<sv<G.vexnum)";
cin>>sv;
cout<<"請輸入第"<<k+1<<"條弧的終點信息tv(0<tv<G.vexnum)";
cin>>tv;
cout<<endl<<endl;
i = LocateVex(G, sv);
j = LocateVex(G, tv); // (比較)確定sv和tv在G中位置，即頂點在G.vertices中的序號

} //while end

ArcNode *p;
p=(ArcNode*)malloc(sizeof(ArcNode));
if(!p)
{
cout<<"Overflow!"; // 存儲分配失敗
return ;
}

p->adjex=j;// 對弧結點賦鄰接點"位置「
p->nextarc=G.vertices[i].firstarc;//頭插法，將tv結點插入到第i個單鏈表中
p->info=NULL;
G.vertices[i].firstarc=p;// 插入鏈表G.vertices[i]
}
}

//################有向表的深度優先遍歷#####################################################################
void DFS(ALGraph G,int v,int visited[])
{
int w;
ArcNode *p;
cout<<G.vertices[v].data<<"->";//訪問第v+1個頂點；
visited[v]=1;
p=G.vertices[v].firstarc;
if(p!=NULL)
w=p->adjex;//w是v的下一個鄰接點的位置，即第v+1個頂點的下一個頂點是第w+1個頂點；
if (p!=NULL)//如果有鄰接點w
{
if(visited[w]==0)//如果w沒訪問過
{
DFS(G,w,visited);
}
else//若訪問過，則訪問v的下一個鄰接點，並返回至判斷是否存在該鄰接點
{
p=p->nextarc;//G.vertices[v].firstarc=G.vertices[v].firstarc->nextarc;
if(p!=NULL) w=p->adjex;//w=G.vertices[v].firstarc->adjex;
}
}
}

void DFSTraverse(ALGraph G)
{

int v,visted[MAX_VERTEX_NUM];
for (v=0;v<G.vexnum;v++)
{
visted[v]=0;
}
for (v=0;v<G.vexnum;v++)
{
if(visted[v]==0)
DFS(G,v,visted);
}

}

//#############廣度優先搜索遍歷######################################################################
//~~~~~~~~~~~~輔助隊列~~~~~~~~~~~~~~~~~~~~~~~~~
int InitQueue (SqQueue &Q)// 構造一個空隊列Q
{
Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));
if(!Q.base)
{
cout<<endl<<"Overflow ! "; // 存儲分配失敗

return 0;
}

Q.front=Q.rear=0;
return 1;
}

int EnQueue(SqQueue &Q,QElemType e)// 插入元素e為Q的新的隊尾元素
{
if ((Q.rear+1)%MAXQSIZE==Q.front)//①判滿
{
cout<<"Error ! The SqQeueu is full ! ";
return 0;
}
Q.base[Q.rear]=e;// ②插入隊尾
Q.rear=(Q.rear+1)%MAXQSIZE;//③隊尾指針後移
return 1;
}

int DeQueue(SqQueue &Q,QElemType &e)// 若隊列不空，則刪除Q的隊頭元素，用e返回其值，並返回OK; 否則返回ERROR
{
if (Q.rear==Q.front)
{
cout<<endl<<"Error ! It's empty!";
return 0;
}
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
return(e);
}
int QueueEmpty(SqQueue Q)
{
if(Q.front==Q.rear)
return (1);
else
return (0);
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
void BFS(ALGraph G,int v,int visited[],SqQueue &Q)
{
int u,w;

ArcNode *p;
cout<<G.vertices[v].data<<"->";//訪問第v+1個頂點；
visited[v]=1;
EnQueue(Q,v);// v入隊列
while (!QueueEmpty(Q))
{
DeQueue(Q,u);// 隊頭元素出隊並置為u
p=G.vertices[v].firstarc;
if(p!=NULL)
w=p->adjex;
for (;p!=NULL;)
{
if (visited[w]==0)
{
cout<<G.vertices[w].data<<"->";
visited[w]=1;
EnQueue(Q, w); // 訪問的頂點w入隊列
}
p=p->nextarc;
if (p!=NULL)
w=p->adjex;
}
}
}

void BFSTraverse(ALGraph G)
{
SqQueue Q;
int v,visted[MAX_VERTEX_NUM];
for (v=0;v<G.vexnum;v++)
{
visted[v]=0;//初始化訪問標志
}
InitQueue(Q);// 置空的輔助隊列Q
for ( v=0; v<G.vexnum; ++v )
{
if(visted[v]==0)// v 尚未訪問
BFS(G,v,visted,Q);// 調用BFS()
}
}

//###############main函數#################
void main()
{
ALGraph G;
CreateGraph(G);
cout<<"深度優先遍歷如下："<<endl;
DFSTraverse(G);
cout<<"End !"<<endl<<endl<<"...OK!...";
cout<<endl<<endl<<"廣度優先遍歷如下："<<endl;
BFSTraverse(G);
cout<<"End !"<<endl<<endl<<"...OK!...";

}

Ⅳ 簡述深度優先搜索遍歷的方法。

簡述深度優先搜索遍歷的方法？深度優先搜索演算法(Depth-First-Search, DFS)，最初是一種用於遍歷或搜索樹和圖的演算法，在LeetCode中很常見，雖然感覺不難，但是理解起來還是有點難度的。

簡要概括，深度優先的主要思想就是「不撞南牆不回頭」，「一條路走到黑」，如果遇到「牆」或者「無路可走」時再去走下一條路。

思路
假如對樹進行遍歷，沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支，當達到邊際時回溯上一個節點再進行搜索。如下圖的一個二叉樹。


首先給出這個二叉樹的深度優先遍歷的結果(假定先走左子樹)：1->2->4->5->3->6->7

那是怎樣得到這樣的結果呢？
根據深度優先遍歷的概念：沿著這樹的某一分支向下遍歷到不能再深入為止，之後進行回溯再選定新的分支。

定義節點

class TreeNode{
int val;
TreeNode left;
TreeNode right;
}
遞歸的方式

分別對左右子樹進行遞歸，一直到底才進行回溯。如果不了解遞歸可以參考我的博客你真的懂遞歸嗎？。

class Solution{
public void (TreeNode root){
if(root == null){
return;
}
System.out.print(root.val +"->");
(root.left);
(root.right);
}
}
迭代的方式

上面實現了遞歸方式的深度優先遍歷，也可以利用棧把遞歸轉換為迭代的方式。

但是為了保證出棧的順序，需要先壓入右節點，再壓左節點。

class Solution{
public void (TreeNode root){
if(root == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
System.out.print(node.val + "->");
if(node.right != null){
stack.push(node.right);
}
if(node.left != null){
stack.push(node.left);
}
}
}
}
接著再列舉個利用深度優先遍歷的方式的題目

掃雷
給定一個表示游戲板的二維字元矩陣，'M'表示一個未挖出的地雷，'E'表示一個未挖出的空方塊，'B' 代表沒有相鄰（上，下，左，右，和所有4個對角線）地雷的已挖出的空白方塊，數字（'1' 到 '8'）表示有多少地雷與這塊已挖出的方塊相鄰，'X' 則表示一個已挖出的地雷。

根據以下規則，返回相應位置被點擊後對應的面板：

如果一個地雷（'M'）被挖出，游戲就結束了- 把它改為'X'。
如果一個沒有相鄰地雷的空方塊（'E'）被挖出，修改它為（'B'），並且所有和其相鄰的方塊都應該被遞歸地揭露。
如果一個至少與一個地雷相鄰的空方塊（'E'）被挖出，修改它為數字（'1'到'8'），表示相鄰地雷的數量。
如果在此次點擊中，若無更多方塊可被揭露，則返回面板。
示例

輸入:

[['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'M', 'E', 'E'],
['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'E', 'E', 'E']]

Click : [3,0]

輸出:

[['B', '1', 'E', '1', 'B'],
['B', '1', 'M', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]
思路：根據給定的規則，當給定一個Click坐標，當不為雷的時候以此坐標為基點向四周8個方向進行深度遍歷，把空格E填充為B，並且把與地雷M相連的空方塊標記相鄰地雷的數量。

注意 ：



在這個題中可以沿著8個方向遞歸遍歷，所有要注意程序中，採用了兩個for循環可以實現向8個方向遞歸。

Ⅵ 什麼是深度優先搜索

深度優先搜索是一種在開發爬蟲早期使用較多的方法。它的目的是要達到被搜索結構的葉結點(即那些不包含任何超鏈的HTML文件) 。在一個HTML文件中，當一個超鏈被選擇後，被鏈接的HTML文件將執行深度優先搜索，即在搜索其餘的超鏈結果之前必須先完整地搜索單獨的一條鏈。深度優先搜索沿著HTML文件上的超鏈走到不能再深入為止，然後返回到某一個HTML文件，再繼續選擇該HTML文件中的其他超鏈。當不再有其他超鏈可選擇時，說明搜索已經結束.
事實上,深度優先搜索屬於圖演算法的一種,英文縮寫為DFS即Depth First Search.其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止,而且每個節點只能訪問一次.
在我們遇到的一些問題當中，有些問題我們不能夠確切的找出數學模型，即找不出一種直接求解的方法，解決這一類問題，我們一般採用搜索的方法解決。搜索就是用問題的所有可能去試探，按照一定的順序、規則，不斷去試探，直到找到問題的解，試完了也沒有找到解，那就是無解，試探時一定要試探完所有的情況（實際上就是窮舉）； 對於問題的第一個狀態，叫初始狀態，要求的狀態叫目標狀態。 搜索就是把規則應用於實始狀態，在其產生的狀態中，直到得到一個目標狀態為止。 產生新的狀態的過程叫擴展（由一個狀態，應用規則，產生新狀態的過程） 搜索的要點：（1）初始狀態； （2）重復產生新狀態； （3）檢查新狀態是否為目標，是結束，否轉（2）； 如果搜索是以接近起始狀態的程序依次擴展狀態的，叫寬度優先搜索。 如果擴展是首先擴展新產生的狀態，則叫深度優先搜索。 深度優先搜索 深度優先搜索用一個數組存放產生的所有狀態。 （1） 把初始狀態放入數組中，設為當前狀態； （2） 擴展當前的狀態，產生一個新的狀態放入數組中，同時把新產生的狀態設為當前狀態； （3） 判斷當前狀態是否和前面的重復，如果重復則回到上一個狀態，產生它的另一狀態； （4） 判斷當前狀態是否為目標狀態，如果是目標，則找到一個解答，結束演算法。 （5） 如果數組為空，說明無解。 對於pascal語言來講，它支持遞歸，在遞歸時可以自動實現回溯（利用局部變數）所以使用遞歸編寫深度優先搜索程序相對簡單，當然也有非遞歸實現的演算法。 搜索是人工智慧中的一種基本方法，是一項非常普遍使用的演算法策略，能夠解決許許多多的常見問題，在某些情況下我們很難想到高效的解法時，搜索往往是可選的唯一選擇。按照標準的話來講：搜索演算法是利用計算機的高性能來有目的的窮舉一個問題的部分或所有的可能情況，從而求出問題的解的一種方法。 搜索雖然簡單易學易於理解，但要掌握好並寫出速度快效率高優化好的程序卻又相當困難，總而言之，搜索演算法靈活多變，一般的框架很容易寫出，但合適的優化卻要根據實際情況來確定。在搜索演算法中，深度優先搜索（也可以稱為回溯法）是搜索演算法里最簡單也最常見的，今天我們就從這里講起，下面的內容假設讀者已經知道最基本的程序設計和簡單的遞歸演算法。

這是我找的資料，希望能幫到你~~

Ⅶ 深度優先搜索演算法解釋下

深度優先搜索演算法（Depth-First-Search），是搜索演算法的一種。是沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支。當節點v的所有邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點並重復以上過程，整個進程反復進行直到所有節點都被訪問為止。屬於盲目搜索。深度優先搜索是圖論中的經典演算法，利用深度優先搜索演算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。

Ⅷ 深度優先和廣度優先 的區別 ，用法。

1、主體區別

深度優先搜索是一種在開發爬蟲早期使用較多的方法。它的目的是要達到被搜索結構的葉結點(即那些不包含任何超鏈的HTML文件)。

寬度優先搜索演算法（又稱廣度優先搜索）是最簡便的圖的搜索演算法之一，這一演算法也是很多重要的圖的演算法的原型。

2、演算法區別

深度優先搜索是每次從棧中彈出一個元素，搜索所有在它下一級的元素，把這些元素壓入棧中。並把這個元素記為它下一級元素的前驅，找到所要找的元素時結束程序。

廣度優先搜索是每次從隊列的頭部取出一個元素，查看這個元素所有的下一級元素，把它們放到隊列的末尾。並把這個元素記為它下一級元素的前驅，找到所要找的元素時結束程序。

3、用法

廣度優先屬於一種盲目搜尋法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能位置，徹底地搜索整張圖，直到找到結果為止。

深度優先即在搜索其餘的超鏈結果之前必須先完整地搜索單獨的一條鏈。深度優先搜索沿著HTML文件上的超鏈走到不能再深入為止，然後返回到某一個HTML文件，再繼續選擇該HTML文件中的其他超鏈。

(8)圖深度搜索演算法擴展閱讀：

實際應用

BFS在求解最短路徑或者最短步數上有很多的應用，應用最多的是在走迷宮上，單獨寫代碼有點泛化，取來自九度1335闖迷宮一例說明，並給出C++/Java的具體實現。

在一個n*n的矩陣里走，從原點（0,0）開始走到終點（n-1,n-1），只能上下左右4個方向走，只能在給定的矩陣里走，求最短步數。n*n是01矩陣，0代表該格子沒有障礙，為1表示有障礙物。

int mazeArr[maxn][maxn]; //表示的是01矩陣int stepArr = {{-1,0},{1,0},{0,-1},{0,1}}; //表示上下左右4個方向，int visit[maxn][maxn]; //表示該點是否被訪問過，防止回溯，回溯很耗時。核心代碼。基本上所有的BFS問題都可以使用類似的代碼來解決。

Ⅸ 數據結構 圖的深度遍歷演算法

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
#define MAX_SIZE 100
int visited[MAX_SIZE];
typedef struct ArcNode{
char adjvex;
ArcNode *nextarc;
}ArcNode;
typedef struct VertexNode{
char data;
ArcNode *firstarc;
}VertexNode;
typedef struct{
VertexNode vexs[MAX_SIZE];
int arcnum,vexnum;
}Graph;
void visit(char ch)
{
printf("%c ",ch);
}
int Loc(Graph G,char ch)
{ int i;
for(i=1;i<=G.vexnum;i++)
{
if(ch==G.vexs[i].data)
return i;
}
}
void creatGraph(Graph *h)
{
ArcNode *p;
int i,j;
char n,m;
printf("輸入弧數和定點數:\n");
scanf("%d %d%*c",&h->arcnum,&h->vexnum);
printf("輸入%d個頂點（A~Z）:\n",h->vexnum);
for(i=1;i<=h->vexnum;i++)
{
scanf("%c%*c",&h->vexs[i].data);
h->vexs[i].firstarc=NULL;
}
printf("%d個弧,輸入弧尾和弧頭\n",h->arcnum);
for(i=1;i<=h->arcnum;i++)
{
scanf("%c %c",&n,&m);
getchar();
j=Loc(*h,n);
p=(ArcNode *)malloc(sizeof(ArcNode));
p->adjvex=m;
p->nextarc=h->vexs[j].firstarc;
h->vexs[j].firstarc=p;

p=(ArcNode *)malloc(sizeof(ArcNode));
j=Loc(*h,m);
p->adjvex=n;
p->nextarc=h->vexs[j].firstarc;
h->vexs[j].firstarc=p; //無向圖
}
}
void DFS(Graph G,char ch)
{ ArcNode *p;
int i;
i=Loc(G,ch);
visit(ch);
visited[i]=1;
p=G.vexs[i].firstarc;
while(p!=NULL)
{
if(!visited[p->adjvex-'A'+1])
DFS(G,p->adjvex);
p=p->nextarc;
}
}
int main()
{
Graph G;
char ch,j;
memset(visited,0,sizeof(visited));
creatGraph(&G);
printf("輸入要開始搜索的頂點\n");
scanf("%c",&ch);
printf("深搜:");
DFS(G,ch);
system("pause");
}
這個是鄰接表的DFS至於鄰接矩陣的DFS，想想我還是寫一下吧void dfs(int v0){ visited[v0]=1; printf("%d",v0); for(int i=1;i<=g.vexnum;i++) if(!visited[i]) { printf("%d",i); visited[i]=1; dfs(i); }}

Ⅹ 對圖採用深度優先搜索，採用的數據結構是： 。

廣度優先用隊列，深度優先用棧。把圖的深度優先搜索遍歷過程中所經歷的邊保留，其餘的彼岸進行刪除，生成的樹為深度優先樹。

深度優先搜索法有遞歸以及非遞歸兩種設計方法。一般當搜索深度較小、問題遞歸方式比較明顯時，用遞歸方法設計好，可以使得程序結構更簡捷易懂。當搜索深度較大時，當數據量較大時，由於系統堆棧容量的限制，遞歸容易產生溢出，用非遞歸方法設計比較好。

(10)圖深度搜索演算法擴展閱讀：

注意事項：

在深度優先搜索中，演算法表現得好像要盡快地遠離起始點似的。相反在廣度優先搜索中，演算法好像要盡可能地靠近起始點，首先訪問起始頂點的所有鄰接點，然後再訪問較遠的區域，是用隊列來實現的。

訪問下一個未來訪問的鄰接點，這個頂點必須是當前頂點的鄰接點，標記它，並把它插入到隊列中，如果因為已經沒有未訪問頂點而不能執行規則1時，那麼從隊列頭取一個頂點，並使其成為當前頂點。