首页 > 代码库 > 周总结(2017.2.16):第一周算法学习。
周总结(2017.2.16):第一周算法学习。
周总结：算法学习总结之DFS和BFS
一：DFS算法
目的：达到被搜索结构的叶节点。
定义：假定给定图G的初态是所有的定点都没有访问过，在G中任选一定点V为初始出发点，首先访问出发点并标记，然后依次从V出发搜索V的每个相邻点W，若W未曾出现过，则对W进行深度优先遍历（DFS），知道所有和V有路径相通的定点被访问。
如果从V0开始寻找一条长度为4的路径的话：
思路步骤：
先寻找V0的所有相邻点:dis{v1,v2,v3}，V1没有访问过，所以对V1进行深度遍历并将V1标记为访问过，此时路径长度为1，然后找到V1的邻点：dis={V2}，继续对V2进行深度遍历，此时长度为2，时dis={}，发现dis为空，退回V1，发现V1没有其他邻点（因为V2已经被标记过）退回V0，发现邻点就只剩下V3，长度等于2，对V3进行深度遍历并将V3标记，邻点dis = {V4,V5}，V4没有访问过，对V4进行深度遍历并将V4标记，长度为3，邻点dis={}，退回V3，发现邻点V5，最后找到V6，发现长度=4，满足题意。
自我总结：DFS是一种递归调用，就像你遇见了一个洞，洞里有许多分叉的洞口，你要对你走的每一步预先判定之后的路才能找到最合适的路。
伪代码：
1 bool DFS(int n,int d) 2 if(End(n,d)) //满足结束条件 3 return true; 4 for(Node nextNode int n){ 5 if(!visited[nextNode]){ 6 visited[nextNode] = true; 7 if(DFS(nextNode,n+1)){ 8 //做一些事 9 //return true; 10 } 11 } 12 visited[nextNode] = false; 13 } 14 return false; 15 }
通过本身的递归调用，可以不断的调整深度，知道最后找到想要的深度或者无法找到。对是否访问过做动态的调整，方便找到最后的路径。
例题：六角填数（很简单的DFS例题）:题目就不写了
直接上代码：
#include"stdio.h"
int a[13] = {0};
int v[13] = {0};
void Jude();
void DFS(int x);
void main(){
a[1] = 1;a[2] = 8;a[12] = 3;
v[1] = 1;v[8] = 1;v[3] = 1;
DFS(1);
}
void DFS(int x){
int i = 0;
if(x==1 || x==2 || x==12){
DFS(x+1);
}
if(x==13){
Jude();
}
for(i=1;i<13;i++){
if(v[i]==0){
v[i] = 1;
a[x] = i;
DFS(x+1);
v[i] = 0;
}
}
}
void Jude(){
int i = 0;
int b[6] = {0};
b[0] = a[1]+a[3]+a[6]+a[8];
b[1] = a[1]+a[4]+a[7]+a[11];
b[2] = a[2]+a[3]+a[4]+a[5];
b[3] = a[2]+a[6]+a[9]+a[12];
b[4] = a[5]+a[7]+a[10]+a[12];
b[5] = a[8]+a[9]+a[10]+a[11];
for(i=1;i<6;i++){
if(b[i] != b[i-1]){
return ;
}
}
printf("a[6] = %d",a[6]);
}
(测试了，代码没有任何问题。)
二：BFS算法
宽度优先算法属于盲目搜索法，是从根节点开始，沿着树的宽度遍历树的节点，如果所有的节点都被访问，则算法终止。
流程：设置起始位置节点为V0，末尾节点为Vd，将V0放入灰色集合体中(将要访问的节点)，从灰色集合体中取出元素Vn，标记为黑色，然后观察Vn的所有临界点放入集合Neighbor集合中，观察Neighbor中有没有Vd，如果没有就将Neighbor中元素放入灰色集合体中。直到找到Vd或者所有节点被遍历。
参考维基百科的图片：
图片看起来更加的形象化，a为起始点h(图片可能出了点错)末尾点。
伪代码(直接拿了维基百科的)：
/**
* ADDQ (Q, p) - p PUSH 入 Q
* DELQ (Q) - POP Q 並返回 Q 頂
* FIRSTADJ (G,v) - v 的第一個鄰接點，找不到則返回 -1
* NEXTADJ (G,v) - v 的下一個鄰接點，找不到則返回 -1
* VISIT (v) - 訪問 v
* visited [] - 是否已訪問
*/
/* 廣度优先搜索算法 */
void BFS(VLink G[], int v) {
int w;
/* 訪問 v 並入隊 */
VISIT(v);
visited[v]=1;
ADDQ(Q,v);
/* 對隊列 Q 的各元素 */
while(!EMPTYQ(Q)) {
v=DELQ(Q);
w=FIRSTADJ(G,v);
/* 的各鄰接點 */
do {
/* 進行訪問和入隊 */
if(visited[w] == 0) {
VISIT(w);
ADDQ(Q,w);
visited[w]=1;
}
} while (w=NEXTADJ(G,v)) != -1)
}
}
/* 對圖G=(V,E)進行廣度優先搜索的主算法 */
void TRAVEL_BFS(VLink G[], bool visited[], int n) {
int i;
// 清零標記數組
for(i = 0; i < n; i ++)
visited[i] = 0;
for(i = 0; i < n; i ++)
if(visited[i] == 0)
BFS(G,i);
}
代码看起来有点不好理解， 因为用了栈的概念，而在c语言中，可以讲栈用数组进行一个代替。
总结:BFS是一种盲目的搜索法，是通过遍历所有的邻节点的邻接点来找到你想要的结果。
例题：走迷宫：
#include "stdio.h"
#include "stdlib.h"
int dir[4][2]={1,0, //x+1,y
-1,0, //x-1,y
0,1, //x,y+1
0,-1}; //x,y-1
//可走的四个方向
struct node{
int x;
inty;
};
struct node queue[50]; //queue记录可走的点
struct node record[5][5];//record记录改点的前驱
void bfs()
{
int head,tail,i;
struct node cur;
struct node next;//cur为当前位置，next为下一个位置
head=tail=0;
cur.x=queue[tail].x;
cur.y=queue[tail].y;
tail++;
while(head<tail)
{
cur=queue[head++];
for(i=0;i<4;i++)
{
next.x=cur.x+dir[i][0];
next.y=cur.y+dir[i][1];
if(next.x>=0&&next.y>=0&&next.x<5&&next.y<5&&map[next.x][next.y]==0) //0为可走路线，不能跑出地图范围
{
record[next.x][next.y].x=cur.x;
record[next.x][next.y].y=cur.y;//记录next的前驱，即next的坐标（因为next记录的是第一个到达该地点的前驱，随后被标记走过，故不用担心被后来的前驱坐标所覆盖）
if(next.x==4&&next.y==4)
return ;
else
{
map[next.x][next.y]=1;//标记走过
queue[tail++]=next;
}
}
}
}
}
int main()
{
int i,j,k,m,n;
struct node cur;
for(i=0;i<5;i++)
for(j=0;j<5;j++)
scanf("%d",&map[i][j]);
cur.x=0;
cur.y=0;
map[0][0]=1;
queue[0]=cur;
bfs();
k=0;
queue[k].x=4;
queue[k++].y=4;
i=j=4;
while(i!=0||j!=0)//根据record的记录，从后往前回溯其路径，并存在queue中
{
m=i;n=j;
i=record[m][n].x;
j=record[m][n].y;
queue[k].x=i;
queue[k++].y=j;
}
for(i=k-1;i>=0;i--)//输出路径
printf("(%d, %d)\n",queue[i].x,queue[i].y);
return 0;
}
代码取自：http://blog.sina.com.cn/s/blog_7e5541250100ssue.html
思路很清晰，注释也很清楚。可以参考下那篇博客(膜拜大神)。
希望各位能够留下自己的想法，我们可以一起交流。我是菜鸟，但我相信，我会变强的。
FIGHTING..............
周总结(2017.2.16):第一周算法学习。