深度优先：深度优先 是从一个顶点开始访问，如果可以访问到下一个未访问过的顶点，就以下一个顶点继续访问，如果不可以访问到下一个未访问过的顶点，则会返回到上一个顶点，继续上述操作
广度优先：广度优先 是从一个顶点开始访问，把它所有可以访问到的未访问过的顶点加入队列，通过head++，继续访问
#pragma mark - - 顶点访问顺序
/**
1
/ | \
2 3 5
|
4
有这样5个顶点，从顶点1开始访问，问 使用深度优先搜索和广度优先搜索，顶点的访问顺序
*/
#pragma mark - - 深度优先搜索 顶点访问顺序
/*
以这题而言：从顶点1开始访问，先访问到顶点2，再以顶点2开始访问，可以访问到顶点4，此时以顶点4开始访问，顶点4无法访问到一个未访问过的顶点（1，2，4顶点已经被访问），则退回到顶点2，以顶点2开始访问，而顶点2又无法访问到一个未访问过的顶点，会退回到顶点1，以顶点1开始访问，顶点1可以访问到顶点3（顶点2已经被访问），此时会以顶点3开始访问，顶点3无法访问到一个未访问过的顶点，退回到顶点1，顶点1继续访问，访问到顶点5
则最终的访问顺序为 1 2 4 3 5
*/
/*
e[6][6] 是一个二维数组，e[i][j] 表示顶点i到顶点j的距离，e[i][j] =999,表示顶点i无法到达顶点j
e[i][j]=0 表示 顶点i和顶点j的距离为0（即顶点i j重合，i，j是同一个顶点）
*/
int sum=0;
int n=5;
-(void)test1 {
int e[6][6];
for (int i=0; i<6; i++) {
for (int j=0; j<6; j++) {
if (i==j) {
e[i][j] =0;
}else {
e[i][j] =999;
}
}
}
e[1][2]=1;
e[2][1]=1;
e[1][3]=1;
e[3][1]=1;
e[1][5]=1;
e[5][1]=1;
e[2][4]=1;
e[4][2]=1;
int book[10] ={0};
book[1]=1;
dfs(1, e, book);
}
// 深度优先
void dfs(int cur,int e[6][6], int book[]) {
NSLog(@"深度优先:%d",cur);
sum ++;
if (sum == n) {
return ;
}
for (int i=1; i<=n; i++) {
if (e[cur][i]==1 && book[i]==0 ) {
book[i] =1;
dfs(i,e,book);
}
}
return ;
}
#pragma mark - - 广度优先访问顺序
/*
广度优先：广度优先 是从一个顶点开始访问，把它所有可以访问到的未访问过的顶点加入队列，通过head++，继续访问
*/
/*
以这题而言：从顶点1开始访问，它可以访问到顶点2 顶点3 顶点5，则把顶点2 3 5加入队列，head++;以顶点2开始访问，可以访问到顶点4，加入队列，head++；此时5个顶点都已经访问过，退出循环。
最终结果为 1 2 3 5 4
一定要head++，head++，才能继续往下扩展
*/
// 广度优先
-(void)test2 {
// 初始化 二维数组 e
int e[6][6]={999};
int book[10] ={0};
e[1][1]=0;
e[2][2]=0;
e[3][3]=0;
e[4][4]=0;
e[5][5]=0;
e[1][2]=1;
e[2][1]=1;
e[1][3]=1;
e[3][1]=1;
e[1][5]=1;
e[5][1]=1;
e[2][4]=1;
e[4][2]=1;
int cur;
// 初始化队列
int que[100];
int head=1;
int tail=1;
// 入队1号点
que[tail]=1;
tail ++;
book[1]=1;
int n=5;
while (head<tail && tail<=n) {
cur = que[head];
for (int i=1; i<=n; i++) {
if (e[cur][i]==1 && book[i]==0) {
book[i] =1;
// 入队
que[tail] = i;
tail ++;
}
// 已全部入队
if (tail>n) {
break ;
}
}
head ++; // head++ 才能继续往下扩展
}
for (int i=1; i<tail; i++) {
NSLog(@"广度优先：%d",que[i]);
}
}
