算法 顶点访问顺序（理解 深度优先搜索和广度优先搜索的原理）

深度优先：深度优先 是从一个顶点开始访问，如果可以访问到下一个未访问过的顶点，就以下一个顶点继续访问，如果不可以访问到下一个未访问过的顶点，则会返回到上一个顶点，继续上述操作

广度优先：广度优先 是从一个顶点开始访问，把它所有可以访问到的未访问过的顶点加入队列，通过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]);
    }
    
    
}