小朋友学数据结构（16）：基于邻接矩阵的的深度优先遍历和广度优先遍历

谁践踏了优雅 2022-05-08 02:38 173阅读 0赞

观察下面两个无向图：

![1.png][]

这两个图其实是一样的，只是画法不同罢了。第一张图更有立体感，第二张图更有层次感，并且把A点置为顶点（事实上图的任何一点都可以做为顶点）。

# 一、用数组来存放顶点 #

vexs[0] = ‘A’
    vexs[1] = ‘B’
    vexs[2] = ‘C’
    vexs[3] = ‘D’
    vexs[4] = ‘E’
    vexs[5] = ‘F’
    vexs[6] = ‘G’
    vexs[7] = ‘H’
    vexs[8] = ‘I’

# 二、用邻接矩阵来表示边 #

![2.png][]

上面这个矩阵中，0表示每个顶点没有到达自己的路径。1表示两个顶点之间有路径，无穷大表示两个顶点之间没有路径。  
假如按照程序计数习惯，行或列都从0数起。  
第0行第0列为0，表示A到它本身之间没有路径（这是人为规定的，因为A到它自身不需要路径）。  
第0行第1列为1，表示顶点A和B之间有路径。  
第0行第5列为1，表示顶点A和顶点F之间有路径。  
第0行其他列为无穷大，表示A到其它点之间没有路径。  
……  
因为是无向图，邻接矩阵必然有两个特点：  
① 对角线（左上角到右下角）上的元素值全为0.表示每个点到它自身没有（或不需要）路径。  
② 其它的元素关于对角线对称。  
上面的邻接矩阵，在编程时可以用二维数组来实现：

arc[0][1] = arc[1][0] = 1;
     arc[0][5] = arc[5][0] =1;
    
     arc[1][2] = arc[2][1] = 1;
     arc[1][6] = arc[6][1] = 1;
     arc[1][8] = arc[8][1] = 1;
    
     arc[2][3] = arc[3][2] = 1;
     arc[2][8] = arc[8][2] = 1;
    
     arc[3][4] = arc[4][3] = 1;
     arc[3][6] = arc[6][3] = 1;
     arc[3][7] = arc[7][3] = 1;
     arc[3][8] = arc[8][3] = 1;
    
     arc[4][5] = arc[5][4] = 1;
     arc[4][7] = arc[7][4] = 1;
    
     arc[5][6] = arc[6][5] = 1;
    
     arc[6][7] = arc[7][6] = 1;

# 三、深度优先遍历 #

可以使用递归的方法进行深度遍历。  
观察图（1）中的左图，假如从顶点A开始，从A找到相邻的B，从B找到相邻的C，从C找到相邻的D，从D找到相邻的E，从E找到邻接点F，从F找到相邻的G，从G找到相邻的H。  
H有三个相邻的点D、E、G。这三个点都已经遍历过了。所以回退到上一顶点G。  
G有三个相邻的顶点D、F、H。这三个点也都已经遍历过了。回退到上一顶点F。  
F有两个相邻的顶点E、G，都已经遍历过了。回退到上个顶点E。  
E点有两个相邻的顶点D、F，都已经遍历过了。回退到上个顶点D。  
D点有五个相邻的顶点C、E、H、G、I。除了I外，其余四个顶点已经遍历过了。所以这一次遍历I。  
I遍历完之后回到D点，从D点回到C点。  
C点有三个相邻的顶点B、D、I，都已经遍历过了，回退到B点。  
B点有四个相邻的顶点A、C、G、I，都已经遍历过了，回退到A点。  
A点有两个相邻的顶点B、F，都已经遍历过了。递归都此结束。  
得到深度优先遍历的顺序为：A B C D E F G H I

# 四、广度优先遍历 #

广度优先遍历需要借助于另外的数据结构队列。当把图中的顶点放到队列中时，表示这个顶点被遍历了（可以把顶点的值打印出来）。  
用图1中的右图来分析广度优先遍历更方便，因为右图的层次结构更明显。

![3.png][]

起初，把点A放入队列中，A被遍历。如上图中的（1）所示。  
接着把队首元素A出队，把A的下一层的顶点B和F移进队列，B和F被遍历。如上图中的（2）所示。  
队首元素B出队，B的下一层顶点C，G，I相继入队，C、G和I被遍历。如上图中的（3）所示。  
队首元素F出队，F的下一层顶点E入队，E被遍历。如上图中的（5）所示。  
队首元素C出队，C的下一层顶点D入队，D被遍历。如上图中的（6）所示。  
队首元素G出队，G的下一层有两个顶点：D和H。D已在队列里，H入队，H被遍历。如上图中的（4）所示。  
队首元素I出队，I的下一层顶点D已在队列里，没有新顶点入队。如上图中的（7）所示。  
队首元素E出队，E的下一层顶点D和H都已在队列里，没有新顶点入队。如上图中的（8）所示。  
队首元素D出队，D没有下一层顶点，所以没有新顶点入队。如上图中的（9）所示。  
队首元素H出队，H没有下一层顶点，所以没有新顶点入队。此时队列为空，遍历结束。  
最终，广度优先遍历的顺序即入队列（或出队列）的顺序：A B F C G I E D H

# 五、完整代码 #

#include "stdio.h"
    
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    #define MAXSIZE 9 /*  存储空间初始分配量 */
    #define MAXEDGE 15
    #define MAXVEX 9
    #define INFINITY 65535
    
    
    typedef int Status;  /* Status 是函数的类型,其值是函数结果状态代码，如 OK 等 */
    typedef int Boolean; /* Boolean 是布尔类型,其值是 TRUE 或 FALSE */
    typedef char VertexType; /*  顶点类型应由用户定义 */
    typedef int EdgeType; /*  边上的权值类型应由用户定义 */
    
    
    typedef struct
    {
        VertexType vexs[MAXVEX]; /*  顶点表 */
        EdgeType arc[MAXVEX][MAXVEX];/*  邻接矩阵，可看作边表 */
        int numVertexes, numEdges; /*  图中当前的顶点数和边数 */
    }MGraph;
    
    
    /*  用到的队列结构与函数********************************** */
    /*  循环队列的顺序存储结构 */
    typedef struct
    {
        int data[MAXSIZE];
        int front;	/* 头位置标识，相当于头指针 */
        int rear;	/* 尾位置标识，相当于尾指针。若队列不为空，指向队列尾元素的下一个位置 */
    }Queue;
    
    
    /*  初始化一个空队列 Q */
    Status InitQueue(Queue *Q)
    {
        Q->front=0;
        Q->rear=0;
    
        return	OK;
    }
    
    
    /*  若队列 Q 为空队列,则返回 TRUE,否则返回 FALSE */
    Status QueueEmpty(Queue Q)
    {
        if(Q.front==Q.rear) /*  队列空的标志 */
            return TRUE;
        else
            return FALSE;
    }
    
    
    /*  若队列未满，则插入元素 e 为 Q 新的队尾元素 */
    Status EnQueue(Queue *Q,int e)
    {
        if ((Q->rear+1)%MAXSIZE == Q->front)  /*  队列满的判断 */
            return ERROR;
    
        Q->data[Q->rear]=e;	/*  将元素 e 赋值给队尾 */
        Q->rear=(Q->rear+1)%MAXSIZE;/* rear 指针向后移一位置，若到最后则转到数组头部 */
    
        return	OK;
    }
    
    
    /*  若队列不为空，则删除 Q 中队头元素，用e返回其值 */
    Status DeQueue(Queue *Q,int *e)
    {
        if (Q->front == Q->rear)	/*  队列空的判断 */
            return ERROR;
    
        *e=Q->data[Q->front];	/*  将队头元素赋值给 e */
        Q->front=(Q->front+1)%MAXSIZE; /* front 指针向后移一位置，若到最后则转到数组头部 */
    
        return	OK;
    }
    
    
    void CreateMGraph(MGraph *G)
    {
        int i, j;
    
        G->numEdges=15;
        G->numVertexes=9;
    
        /*  读入顶点信息，建立顶点表 */
        G->vexs[0]='A';
        G->vexs[1]='B';
        G->vexs[2]='C';
        G->vexs[3]='D';
        G->vexs[4]='E';
        G->vexs[5]='F';
        G->vexs[6]='G';
        G->vexs[7]='H';
        G->vexs[8]='I';
    
        for (i = 0; i < G->numVertexes; i++)/*  初始化图 */
        {
            for ( j = 0; j < G->numVertexes; j++)
            {
                G->arc[i][j]=0;
            }
        }
    
        G->arc[0][1]=1;
        G->arc[0][5]=1;
    
        G->arc[1][2]=1;
        G->arc[1][6]=1;
        G->arc[1][8]=1;
    
        G->arc[2][3]=1;
        G->arc[2][8]=1;
    
        G->arc[3][4]=1;
        G->arc[3][6]=1;
        G->arc[3][7]=1;
        G->arc[3][8]=1;
    
        G->arc[4][5]=1;
        G->arc[4][7]=1;
    
        G->arc[5][6]=1;
    
        G->arc[6][7]=1;
    
        for(i = 0; i < G->numVertexes; i++)
        {
            for(j = i; j < G->numVertexes; j++)
            {
                G->arc[j][i] =G->arc[i][j];
            }
        }
    }
    
    Boolean visited[MAXVEX]; /*  访问标志的数组 */
    
    /*  邻接矩阵的深度优先递归算法 */
    void DFS(MGraph G, int i)
    {
        int j;
        visited[i] = TRUE;
        printf("%c ", G.vexs[i]);/*  打印顶点，也可以其它操作 */
    
        for(j = 0; j < G.numVertexes; j++)
            if(G.arc[i][j] == 1 && !visited[j])
                DFS(G, j);/*  对未访问的邻接顶点递归调用 */
    }
    
    
    /*  邻接矩阵的深度遍历算法 */
    void DFSTraverse(MGraph G)
    {
        int i;
        for(i = 0; i < G.numVertexes; i++)
            visited[i] = FALSE; /*  初始所有顶点状态都是未访问过状态 */
    
        for(i = 0; i < G.numVertexes; i++)
            if(!visited[i]) /*  对未访问过的顶点调用 DFS，若是连通图，只会执行一次 */
                DFS(G, i);
    }
    
    
    /*  邻接矩阵的广度遍历算法 */
    void BFSTraverse(MGraph G)
    {
        int i, j;
        Queue Q;
    
        for(i = 0; i < G.numVertexes; i++)
            visited[i] = FALSE;
    
        InitQueue(&Q);	/*  初始化一辅助用的队列 */
    
        for(i = 0; i < G.numVertexes; i++)	/*  对每一个顶点做循环 */
        {
            if (!visited[i])   /*  若是未访问过就处理 */
            {
                visited[i]=TRUE;	/*  设置当前顶点访问过 */
                printf("%c ", G.vexs[i]);/*  打印顶点，也可以其它操作 */
                EnQueue(&Q,i);	/*  将此顶点入队列 */
    
                while(!QueueEmpty(Q)) /*  若当前队列不为空 */
                {
                    DeQueue(&Q,&i);   /*  将队对元素出队列，赋值给 i */
                    for(j=0;j<G.numVertexes;j++)
                    {
                        /*  判断其它顶点若与当前顶点存在边且未访问过	*/
                        if(G.arc[i][j] == 1 && !visited[j])
                        {
                            visited[j]=TRUE;	/*  将找到的此顶点标记为已访问*/
                            printf("%c ", G.vexs[j]);   /*  打印顶点 */
                            EnQueue(&Q,j);	/*  将找到的此顶点入队列	*/
                        }
                    }
                }
            }
        }
    }
    
    
    int main(void)
    {
        MGraph G;
        CreateMGraph(&G);
    
        printf("\n 深度遍历：");
        DFSTraverse(G);
    
        printf("\n 广度遍历：");
        BFSTraverse(G);
    
        return 0;
    }

运行结果：

深度遍历：A B C D E F G H I
    广度遍历：A B F C G I E D H

> 了解小朋友学编程请加QQ307591841（微信与QQ同号），或QQ群581357582。  
> 关注公众号请扫描二维码  
> ![qrcode\_for\_kidscode\_258.jpg][qrcode_for_kidscode_258.jpg]

[1.png]: /images/20220508/b8cdb429f79f4d0da4dbe28486af3a0f.png
[2.png]: /images/20220508/87a78c886ccf43cb875a5caa935722ab.png
[3.png]: /images/20220508/9079d347c50844f8973f48a08bb2ca3b.png
[qrcode_for_kidscode_258.jpg]: /images/20220508/1354207f04854773914401d31c47cfc7.png