[練習] graph走訪程式

當一台機器人

想要讓他走到所有想讓他去的地方

那就需要利用走訪的程式

(本魔承認有點硬要扯到機器人...)

總之

來介紹一下兩種走訪方式



深度優先搜尋(depth - first search) 簡稱DFS

簡單的說就是先找到最深的路  再退回來走其他的路

像我的範例

若是用深度優先
他會從1 -> 2 -> 4 -> 3 然後沒路了   退回4  再走5     再往後退   都沒路就結束

以下為DFS的code

#include "stdafx.h"
#define graph_Max 5
void DFS(int);
static bool graph[graph_Max][graph_Max] = {
           {0,1,1,0,0},
           {1,0,0,1,0},
           {1,0,0,1,0},
           {0,1,1,0,1},
           {0,0,0,1,0}};
static int point_name[graph_Max] = {1,2,3,4,5};
int main(){
 DFS(0);
 getchar();
 return 0;
}
bool visited[graph_Max] = {false};
void DFS(int v){
 visited[v] = true;
 printf("%d\n",point_name[v]);
 for(int i = 0; i < graph_Max; i++)
  if(graph[v][i] && !visited[i])
   DFS(i);
}

廣度優先搜尋(breath - first search) 簡稱BFS

簡單的說就是將所有可走的路先走過  再走第二次...走到全部沒路為止

像我的範例

若是用廣度優先

他會從1 -> 2 & 3  然後1沒其他路   

2 -> 4  然後2沒其他路   

3 也沒其他路

再來到4 -> 5

最後的5  也沒路了    全部都沒路   結束

以下為BFS的code

#include "stdafx.h"
#define graph_Max 5
static bool graph[graph_Max][graph_Max] = {
           {0,1,1,0,0},
           {1,0,0,1,0},
           {1,0,0,1,0},
           {0,1,1,0,1},
           {0,0,0,1,0}};
static int point_name[graph_Max] = {1,2,3,4,5};
void BFS(int);
void push(int);
int pop();
bool isEmpty();
int main()
{
 BFS(0);
 getchar();
 return 0;
}
bool visited[graph_Max] = {false};
void BFS(int v){
 visited[v] = true;
 printf("%d\n",point_name[v]);
 for(int i = 0; i < graph_Max; i++)
  if(graph[v][i] && !visited[i]){
   visited[i] = true;
   push(i);
  }
 while(!isEmpty())
  BFS(pop());
}
int queue[graph_Max];
int first = 0;
int last = 0;
void push(int x){
 if(last >= graph_Max)
  last = 0;
 queue[last++] = x;
}
int pop(){
 return queue[first++];
}
bool isEmpty(){
 return first == last;
}

以上就是本魔這次介紹的兩個走訪程式