图深度搜索算法

Ⅰ 深度优先搜索的详细解释

事实上，深度优先搜索属于图算法的一种，英文缩写为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时，那么从队列头取一个顶点，并使其成为当前顶点。