Question

有没有关于深度优先搜索和广度优先搜索（深搜和宽搜）的ppt啊？语言：pascal

最好各有一道例题和代码（伪代码也可以）...快一点...今天以前要...

Answer 1

我有PPT 可是很难给你，这是我的QQ：1132883808 你加我吧，然后我再发给你。
深优例题：N皇后问题
算法框架（递归基本算法）
Procedure DFS(dep);
begin
For i:=1 to max_i do {共有max_i种可能情况}
If 某种可能符合条件 then begin
采用这种可能情况；
if 达到目标 then 输出
else dfs(dep+1)；
把这种情况取消；{回溯}
end;
end;

广优例题：找迷宫的最短路径
Program BFS; {Breadth-First-Search}
const
migong:array [1..5,1..5] of integer=((0,0,-1,0,0), (0,-1,0,0,-1),
(0,0,0,0,0), (0,-1,0,0,0), (-1,0,0,-1,0));
{迷宫数组,-1表示墙}
fangxiang:array [1..4,1..2] of -1..1=((1,0),(0,1),(-1,0),(0,-1));
{方向增量数组}
type node=record
lastx:integer; {上一位置坐标}
lasty:integer;
nowx:integer; {当前位置坐标}
nowy:integer;
pre:byte; {本结点由哪一步扩展而来}
dep:byte; {本结点是走到第几步产生的}
end;
var
lujing:array[1..25] of node; {记录走法数组}
closed,open,x,y,r:integer;

procedure output; {见后面输出一}
var i,j:integer;
begin
for i:=1 to 5 do begin
for j:=1 to 5 do
write(migong[i,j]:4); writeln;end;
i:=open;
repeat
with lujing[i] do
write(nowy:2,',',nowx:2,' <--');
i:=lujing[i].pre;
until lujing[i].pre=0;
with lujing[i] do
write(nowy:2,',',nowx:2);
end;

procedure output1; {见后面输出二}
var i,j:integer;
procedure digui(i:integer);
begin
if lujing[i].pre<>0 then digui(lujing[i].pre);
with lujing[i] do
write(nowy:2,',',nowx:2,'-->');
end;

begin
for i:=1 to 5 do begin
for j:=1 to 5 do
write(migong[i,j]:4); writeln;end;
i:=open;
digui(i);
end;
{主程序}
begin
with lujing[1] do begin {初始化第一步}
lastx:=0; lasty:=0; nowx:=1;nowy:=1;pre:=0;dep:=1;end;
closed:=0;open:=1;migong[1,1]:=1;
repeat
inc(closed); {队列首指针加1,取下一结点}
for r:=1 to 4 do begin {以4个方向扩展当前结点}
x:=lujing[closed].nowx+fangxiang[r,1]; {扩展形成新的坐标值}
y:=lujing[closed].nowy+fangxiang[r,2];
if not ((x>5)or(y>5) or (x<1) or (y<1) or (migong[y,x]<>0)) then begin
{未出界,未走过则可视为新的结点}
inc(open); {队列尾指针加1}
with lujing[open] do begin {记录新的结点数据}
nowx:=x; nowy:=y;
lastx:=lujing[closed].nowx;{新结点由哪个坐标扩展而来}
lasty:=lujing[closed].nowy;
dep:=lujing[closed].dep+1; {新结点走到第几步}
pre:=closed; {新结点由哪个结点扩展而来}
end;
migong[y,x]:=lujing[closed].dep+1; {在地图上作标记}
if (x=5) and (y=5) then begin {输出找到的第一种方案}
writeln('ok,thats all right');output;halt;end;
end;
end;
until closed>=open; {直到首指针大于等于尾指针,即所有结点已扩展完}
end.

Answer 2

给你一个作为参考吧

#include <iostream>

#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");
}
另外,团IDC网上有许多产品团购,便宜有口碑