数据结构（图的遍历和马踏棋盘算法）

图的遍历

有两种方法：深度优先，广度优先

深度优先遍历

• 约定左手原则，在没有遇到重复顶点的情况下，分叉路口是从向右手边走，每走过一个顶点就做一个记号
• 如果分叉路所通向的结点已经全部走过，则返回上一个结点（回溯）
• 由此方法，直到返回这个顶点是结束

邻接矩阵中实现思路：

• 从A[0][0]开始，连向第一行中的第一个为1的元素A[ i ][ j ]；
• 然后跳到第 j 行继续找到第一个为1的元素，并确定这个元素是否走过，如果走过，则返回上一次跳转的行；第0行所对应结点全部走过

代码实现

#include <stdio.h>
#include <malloc.h>
#define SIZE 9

void user(char *lin,int n){
    printf("%c  ",lin[n]);
}

void depthTraversal(char *lin,int (*arr)[SIZE],int n){
    int i=0,j=n;
    static int tab[]={0,0,0,0,0,0,0,0,0};
    tab[j]=1;
    user(lin,j);
    for(i=0;i<SIZE;i++){
        if(i==j)
            continue;
        if(*(*(arr+j)+i)==1 && tab[i]==0)
            depthTraversal(lin,arr,i);
    }
}

void main(){
    char lin[]={‘A‘,‘B‘,‘C‘,‘D‘,‘E‘,‘F‘,‘G‘,‘H‘,‘I‘};
    int arr[9][9]={
           {0,1,0,0,0,1,0,0,0},
           {1,0,1,0,0,0,1,0,1},
           {0,1,0,1,0,0,0,0,1},
           {0,0,1,0,1,0,1,1,1},
           {0,0,0,1,0,1,0,1,0},
           {1,0,0,0,1,0,1,0,0},
           {0,1,0,1,0,1,0,1,0},
           {0,0,0,1,1,0,1,0,0},
           {0,1,1,1,0,0,0,0,0}
        };
    depthTraversal(lin,arr,0);
    printf("\n");
}

马踏棋盘算法

问题概述：在国际棋盘（8*8）中将‘马’放在任意指定的方框中，按照‘马’走‘日’的规则将马进行移动。要求每个方格只能进入一次，最终使马走遍棋盘64个方格。

解决方法：利用深度遍历的方法（回溯）；使马遇到死路时就回溯，直到走遍棋盘；

注：在(n*n)的棋盘上，当 n ≥ 5且为偶数时，以任一点都有解

#include <stdio.h>
#include <malloc.h>
#define X 8
#define Y 8

int arr[X][Y];

int nextxy(int *x,int*y,int count){
    switch(count){
        case 0:
            if(*x+2<=X-1 && *y-1>=0 && arr[*x+2][*y-1]==0){
                *x+=2;
                *y-=1;
                return 1;
            }
            break;
        case 1:
            if(*x+2<=X-1 && *y+1<=Y-1 && arr[*x+2][*y+1]==0){
                *x+=2;
                *y+=1;
                return 1;
            }
            break;
        case 2:
            if(*x+1<=X-1 && *y-2>=0 && arr[*x+1][*y-2]==0){
                *x+=1;
                *y-=2;
                return 1;
            }
            break;
        case 3:
            if(*x+1<=X-1 && *y+2<=Y-1 && arr[*x+1][*y+2]==0){
                *x+=1;
                *y+=2;
                return 1;
            }
            break;
        case 4:
            if(*x-2>=0 && *y-1>=0 && arr[*x-2][*y-1]==0){
                *x-=2;
                *y-=1;
                return 1;
            }
            break;
        case 5:
            if(*x-2>=0 && *y+1<=Y-1 && arr[*x-2][*y+1]==0){
                *x-=2;
                *y+=1;
                return 1;
            }
            break;
        case 6:
            if(*x-1>=0 && *y-2>=0 && arr[*x-1][*y-2]==0){
                *x-=1;
                *y-=2;
                return 1;
            }
            break;
        case 7:
            if(*x-1>=0 && *y+2<=Y-1 && arr[*x-1][*y+2]==0){
                *x-=1;
                *y+=2;
                return 1;
            }
            break;
        default:
            break;
    }
    return 0;
}

void Print(){
    int i,j;
    for(i=0;i<X;i++){
        for(j=0;j<Y;j++){
            printf("%d\t",arr[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

//(x,y)为位置坐标
//tag是标记变量，也用于记录步骤
int TravelBoard(int x,int y,int tag){
    int x1=x,y1=y;
    int i=0;
    int flag=0;//记录当前位置的选者是否会导致失败
    arr[x][y]=tag;
    if(X*Y==tag){
        Print();//打印
        return 1;
    }
    //找到马下一个可走的坐标（x1,y1）,如果找到flag=1,否者为0
    flag=nextxy(&x1,&y1,i);
    while(0==flag &&i<8){
        i++;
        flag=nextxy(&x1,&y1,i);
    }

    while(flag){//这里的flag记录是否结束（失败）
        if(TravelBoard(x1,y1,tag+1)){
            return 1;
        }

        //这个位置会导致后面碰壁失败，需要回溯到上个位置
        x1=x;
        y1=y;
        i++;
        flag=nextxy(&x1,&y1,i);
        while(0==flag &&i<8){
            i++;
            flag=nextxy(&x1,&y1,i);
        }
    }
    if(flag==0){
        arr[x][y]=0;
    }
    return 0;
}

void main(){
    int i,j;
    for(i=0;i<X;i++){
        for(j=0;j<Y;j++){
            arr[i][j]=0;
        }
    }
    printf("请输入起始位置的行：");
    scanf("%d",&i);
    printf("请输入起始位置的列：");
    scanf("%d",&j);
    //建议用两行一列测试

    if(!TravelBoard(i,j,1)){
        printf("马踏棋盘失败");
    }
}

广度优先遍历

其实广度优先遍历，类似与树的层序遍历

方法：

• 任意选一顶点，放入队列中；
• 在队列中让第一个位置进行操作，遍历这个顶点的所有连接的顶点，依次加入到这个队列中（加入时做好标记以免重复添加）；删除刚刚操作的队头顶点
• 重复 ② 步骤，直到队列中全部结点出队列