20210510

回顾 | 数据结构-图（二）| GS2-660-C5-58~61 | 恋词U14

Table of Contents

回顾

数据结构-图的遍历-图（二）

从图中的某一顶点出发，访遍图中其余顶点，且使每一顶点仅被访问一次，这一过程就叫做图的遍历(Traversing Graph)

图的遍历算法-深度优先搜索遍历（DFS）

深度优先遍历(Depth First Search)，也有称为深度优先搜索，简称为DFS。类似于树的前序遍历

想象一下，此时站在A处（其他也可以），（面向D的方向）。给自己定一个原则，右手原则（或左手原则也可以），从A开始要走遍所有的图顶点并做上标记，开始走了噢！

image.png

不难发现其实就是一个递归的过程，再细心观察，其实就是一棵树的前序遍历（先访问根结点，再左子树，再右子树）。

void DFS(int v,AGraph *G)

{

    visit[v] = 1;

    Visit(v);

    ArcNode *q = G->adjList[v].first;

    while(q != NULL)

    {

        if (visit[q->adjv] == 0)

            DFS(q->adjv,G);

        q = q->next;

    }

}

图的遍历算法-广度优先搜索遍历（BFS）

图的广度优先遍历类似于树的层次遍历。

将之前那个图变一下形状：

image.png

那么，从顶点A出发，则与A相邻的有B、F。（假如遵守右手原则），则是A→B→F。然后B又找到下一层CIG，F又找到下一层GE（但G已经被B遍历过有标记了），即为A→B→F→C→I→G→E,然后C找到下一层D，I找到下一层D（已标记），G找到下一层H，E找到下一层H，（已标记），所以为：A→B→F→C→I→G→E→D→H

void BFS(AGraph *G, int v, int visit[maxSize])

{

    ArcNode *p;

    int que[maxSize], front = 0 , rear = 0;

    int j;

    Visit(v);

    Visit[v] = 1;

    rear = (rear+1)%maxSize;

    que[rear] = v;

    while( front != rear)

    {

        front = (front+1)%maxSize;

        j = que[front];

        p = G->adjlist[j]first;

        while( p != NULL)

        {

            if(visit[p->adjv] ==0)

            {

                visit[p->adjv];

                visit[p->adjv] = 1;

                rear = (rear + 1)%maxSize;

                que[rear] = p->adjv;

            }

            p = p->next;

        }

    }

}

GS2-660-C5-58~61

这章蛮难的，很多细节和方法以及固定的思维定势要在这一章形成。加油

恋词U14