数据结构——树的深搜算法

2022-11-04 13:25:02

树的深度搜索（DFS）算法

一些概念

图的遍历

从图中某一顶点出发访遍图中其余顶点，且使每一个顶点有且仅被访问一次。

图的遍历的意义

是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。

图的遍历通常有两种方法，即深度优先搜索和广度优先搜索

下面介绍深度优先搜索（DFS Depth_First Search）

事先准备：

因为图的遍历要求每个顶点有且只被访问一次，所以就需要一个辅助数组visited[](可用bool类型或其他类型)来代表该顶点是否被访问过。

算法流程：

邻接矩阵存储方式

①将所有点设置为未被访问状态；

②用下标v，按顶点向量数组的顺序访问每个未被访问的点；

③对于邻接矩阵，将下标为v的元素设置为已访问，并输出该点信息（这里用输出代表访问），遍历下标第v行的邻接矩阵元素，遇到非零并且未被访问过的下标w时，跳转到第w行；

④重复执行第③步。

邻接表存储方式

①将所有点设置为未被访问状态；

②用下标v，按顶点向量表的顺序访问每个未被访问的点；

③对于邻接表的表结点，将下标为v的元素设置为已访问，并输出该点信息（这里用输出代表访问），遍历下标第v个元素所在的邻接表的表结点，遇到未被访问过的结点时，跳转到该结点所在行w；

④重复执行第③步。

邻接矩阵存储方式C语言实现

void DFS(MGraph G, int v, bool visited[])//深度搜索 
{
    visited[v] = true;//将点ｖ设置为已访问 
    cout<<G.vexs[v];
    for(int w = 0; w < G.vexnum; w++)
    {
        if((G.arcs[v][w] == 1) && !visited[w])
            DFS(G, w, visited);
    }
} 

void DFSTravrese(MGraph G, bool visited[])
{
    for(int i = 0 ; i < G.vexnum; i++)//初始化访问数组信息 
        visited[i] = false;
    for(int v = 0; v < G.vexnum; v++)
    {
        if(!visited[v])
            DFS(G, v, visited);
    }
}

邻接表存储方式C语言实现

void DFS(ALGraph G, bool visited[], int v)
{
    visited[v] = true;
    cout<<setw(5)<<G.vertices[v].data;
    ArcNode *p;
    for(p = G.vertices[v].firstarc; p; p = p->nextarc)
    {
        if(!visited[p->adjvex])
            DFS(G, visited, p->adjvex);    
    }    
}

void DFSTraverse(ALGraph G, bool visited[])
{
    for(int i = 0 ; i < G.vexnum; i++)
        visited[i] = false;
    for(int i = 0; i < G.vexnum; i++)
    {
        if(!visited[i])
        {
            cout<<endl;
            DFS(G, visited, i);    
        }
    } 
}

例子分析

连通图

邻接矩阵表达法运行结果如下：

图的顶点数和边数： 8 9
图的顶点信息：
1 2 3 4 5 6 7 8
图的邻接矩阵：

0 1 1 0 0 0 0 0
1 0 0 1 1 0 0 0
1 0 0 0 0 1 1 0
0 1 0 0 0 0 0 1
0 1 0 0 0 0 0 1
0 0 1 0 0 0 1 0
0 0 1 0 0 1 0 0
0 0 0 1 1 0 0 0

该图的出度信息：
2 3 3 2 2 2 2 2
该图的入度信息：
2 3 3 2 2 2 2 2
深度搜索结果如下：
1 2 4 8 5 3 6 7

分析如下：

在DFSTravrese函数中v=0，即 1 未被访问，进入DFS函数，visited[0]变为true，打印 1 ；

在邻接矩阵中，与 1 邻接点为 2 ，进入第二行，进入DFS函数，visited[1]变为true，打印 2；

在第二行中， 1 已被访问过，下一次循环， 4 未被访问，进入第四行，进入DFS函数，visited[3]变为true，打印 4；

在第四行中，2 已被访问，下一次循环， 8 未被访问，进入第八行，进入DFS函数，visited[7]变为true，打印 8；

在第八行中， 4 已被访问，下一次循环， 5 未被访问，进入第五行，进入DFS函数，visited[4]变为true，打印 5；

在第五行中， 2 和 8 已被访问，返回第八行；

在第八行中，没有未被访问的点，返回第四行；

在第四行中，没有未被访问的点，返回第二行；

在第二行中，没有未被访问的点，返回第一行；

在第一行中， 3 未被访问，进入第三行，进入DFS函数，visited[2]变为true，打印 3；

在第三行中， 6 未被访问，进入第六行，进入DFS函数，visited[5]变为true，打印 6；

在第六行中， 7 未被访问，进入第七行，进入DFS函数，visited[6]变为true，打印 7；

在第七行中，没有未被访问的点，返回第六行；

在第六行中，没有未被访问的点，返回第三行；

在第三行中，没有未被访问的点，返回第一行；

在第一行中，没有未被访问的点，返回DFSTravrese函数；

v>0的点中已没有未被访问的点，深搜结束。

非连通图

邻接表表达法运行结果如下：

图的顶点数和边数： 13 13
图的顶点信息：
A B C D E F G H I J K L M
图的邻接表：
A的邻接点：L F C B
B的邻接点：M A
C的邻接点：A
D的邻接点：E
E的邻接点：D
F的邻接点：A
G的邻接点：K H I
H的邻接点：K G
I的邻接点：G
J的邻接点：M L
K的邻接点：H G
L的邻接点：J M A
M的邻接点：J L B

该图的出入度情况如下：

入度信息：
4 2 1 1 1 1 3 2 1 2 2 3 3
出度信息：
4 2 1 1 1 1 3 2 1 2 2 3 3
深度搜索结果如下：

A L J M B F C
D E
G K H I

分析如下：

在DFSTravrese函数中v=0，即A未被访问，进入DFS函数，visited[0]变为true，打印 A；