1. Toy模板网首页
  2. > Toy博客

数据结构与算法基础-学习-24-图的遍历之DFS（深度优先搜索）和BFS（广度优先搜索）

7月前 作者：阳光九叶草LXGZXJ 分类：Toy博客 阅读(52) 违法举报

这篇具有很好参考价值的文章主要介绍了数据结构与算法基础-学习-24-图的遍历之DFS（深度优先搜索）和BFS（广度优先搜索）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

目录

一、遍历定义

二、遍历实质

三、DFS

四、BFS

五、宏定义

六、自定义类型

七、函数实现

1、DFS（邻接矩阵实现）

2、DFS（邻接表实现）

3、BFS（邻接矩阵实现）

4、BFS（邻接表实现）

5、打印邻接矩阵遍历顺序

 6、打印邻接表遍历顺序

八、遍历算法效率分析

1、DFS

2、BFS

九、Linux编译测试

一、遍历定义

从已给的连通图中某一顶点出发，沿着一些边访问遍图中所有顶点，且使每个顶点仅被访问一次，就叫做的图的遍历，它是图的基本运算。

二、遍历实质

找每个顶点的邻接点的过程。

三、DFS

深度优先搜索，英文全称Depth First Search。如下图进行举例说明。

dfs遍历和bfs遍历,# 数据结构与算法基础学习,深度优先,宽度优先,数据结构,算法,c语言

这里以邻接矩阵表示无向图进行举例，生成内容如下：

[2023-5]--[ Debug ]--Printf AMGraph                     :
VertexArray    : [A ,B ,C ,D ,E ]
ArcArray       :
[32767 ,20    ,30    ,10    ,32767 ]
[20    ,32767 ,32767 ,32767 ,50    ]
[30    ,32767 ,32767 ,40    ,32767 ]
[10    ,32767 ,40    ,32767 ,60    ]
[32767 ,50    ,32767 ,60    ,32767 ]
CurVertexNum   : 5
CurArcNum      : 12

 我们还需要维护一个Visit数组，用于确认访问过的节点有哪些，0表示没有访问过，1表示访问过。

dfs遍历和bfs遍历,# 数据结构与算法基础学习,深度优先,宽度优先,数据结构,算法,c语言

 例如我们从E出发，Visit数组变为：

dfs遍历和bfs遍历,# 数据结构与算法基础学习,深度优先,宽度优先,数据结构,算法,c语言

从邻接矩阵上看，E->B和E->D，DFS算法是一条道走到黑，先扫到B节点，又发现B节点没有被访问，所以先走E->B。

[32767 ,50    ,32767 ,60    ,32767 ]

Visit数组变为：

dfs遍历和bfs遍历,# 数据结构与算法基础学习,深度优先,宽度优先,数据结构,算法,c语言

从邻接矩阵上看B的情况，可以走B->A和B->E，先发现的A节点，又发现A节点没有被访问，所以先走B->A。

[20    ,32767 ,32767 ,32767 ,50    ]

Visit数组变为：

dfs遍历和bfs遍历,# 数据结构与算法基础学习,深度优先,宽度优先,数据结构,算法,c语言

从邻接矩阵上看A的情况，可以走A->B和A->C，A->D，先发现的B节点，又发现B节点被访问过，所以跳过，再看C节点发现没有被访问，所以先走A->C。

[32767 ,20    ,30    ,10    ,32767 ]

Visit数组变为：

dfs遍历和bfs遍历,# 数据结构与算法基础学习,深度优先,宽度优先,数据结构,算法,c语言

从邻接矩阵上看C的情况，可以走C->A和C->D，先发现的A节点，又发现A节点被访问过，所以跳过，再看D节点发现没有被访问，所以先走C->D。

[30    ,32767 ,32767 ,40    ,32767 ]

Visit数组变为：

dfs遍历和bfs遍历,# 数据结构与算法基础学习,深度优先,宽度优先,数据结构,算法,c语言

 最后发现Visit数组中的所有节点被访问完，退出程序。

四、BFS

广度优先搜索，英文全称Breadth First Search，BFS类似于树的层次遍历，我们可以将图逆时针旋转90度，如下图进行举例说明。

dfs遍历和bfs遍历,# 数据结构与算法基础学习,深度优先,宽度优先,数据结构,算法,c语言

旋转后：

dfs遍历和bfs遍历,# 数据结构与算法基础学习,深度优先,宽度优先,数据结构,算法,c语言

这里以邻接矩阵表示无向图进行举例，生成内容如下：

[2023-5]--[ Debug ]--Printf AMGraph                     :
VertexArray    : [A ,B ,C ,D ,E ]
ArcArray       :
[32767 ,20    ,30    ,10    ,32767 ]
[20    ,32767 ,32767 ,32767 ,50    ]
[30    ,32767 ,32767 ,40    ,32767 ]
[10    ,32767 ,40    ,32767 ,60    ]
[32767 ,50    ,32767 ,60    ,32767 ]
CurVertexNum   : 5
CurArcNum      : 12

和DFS一样我们也需要维护一个Visit数组，用于确认访问过的节点有哪些，0表示没有访问过，1表示访问过。

dfs遍历和bfs遍历,# 数据结构与算法基础学习,深度优先,宽度优先,数据结构,算法,c语言

我们还需要维护一个队列，没错思路和层次遍历一样。

 例如我们还是从E出发，Visit数组变为：

dfs遍历和bfs遍历,# 数据结构与算法基础学习,深度优先,宽度优先,数据结构,算法,c语言

队列变为：

[2023-5]--[ Debug ]--SqQueue Data   :
Data           : [ 4 ]
FrontIndex     : 0
RearIndex      : 1
SqQueueLen     : 1

从邻接矩阵上看E，E->B和E->D，BFS算法是广度优先，会先把E可以访问的节点先都走一遍，判断BD是否被访问，都没有被访问，那就依次访问E->B和E->D。

[32767 ,50    ,32767 ,60    ,32767 ]

Visit数组变为：

dfs遍历和bfs遍历,# 数据结构与算法基础学习,深度优先,宽度优先,数据结构,算法,c语言

队列弹出E，压入BD变为：

[2023-5]--[ Debug ]--SqQueue Data   :
Data           : [ 1 ,3 ]
FrontIndex     : 1
RearIndex      : 3
SqQueueLen     : 2

队列中弹出B，从邻接矩阵上看B的情况，可以走B->A和B->E，发现A节点没有被访问,压入队列中，E被访问过，不压入，所以走B->A。

[20    ,32767 ,32767 ,32767 ,50    ]

Visit数组变为：

dfs遍历和bfs遍历,# 数据结构与算法基础学习,深度优先,宽度优先,数据结构,算法,c语言

 队列，弹出B，压入A变为：

[2023-5]--[ Debug ]--SqQueue Data   :
Data           : [ 3 ,0 ]
FrontIndex     : 2
RearIndex      : 4
SqQueueLen     : 2

弹出D,从邻接矩阵上看D的情况，可以走D->A和D->C，D->E，发现A节点被访问过，所以跳过，再看C节点发现没有被访问，所以先走D->C，发现所有节点都被访问，退出程序。

[10    ,32767 ,40    ,32767 ,60    ]

Visit数组变为：

dfs遍历和bfs遍历,# 数据结构与算法基础学习,深度优先,宽度优先,数据结构,算法,c语言

五、宏定义

#define MAX_INT_TYPE_NUM      32767 //网中代表无穷大，也代表顶点个数。
#define MAX_VERTEX_NUM        10000 //顶点数组中存放顶点的最大个数。
#define NET_DIRECTION_FLAG    0     //有向网的标志
#define NET_UNDIRECTION_FLAG  1     //无向网的标志

//DFS,BFS
#define VISITED_FLAG          1
#define NOT_VISITED_FLAG      0

六、自定义类型

//DFS,BFS
typedef struct AccessSeqType
{
    VertexIndexType Array[MAX_VERTEX_NUM];
    VertexIndexType ArraySize;
}AccessSeqType;

这是一个访问顺序数组，方便查看访问顺序的。

邻接矩阵和邻接表的定义和相关代码可以参考之前的文章《数据结构与算法基础-学习-23-图之邻接矩阵与邻接表》

七、函数实现

1、DFS（邻接矩阵实现）

void DepthFirstSearchUseAMGraph(AMGraph* AMG, VertexIndexType VertexIndex, VertexIndexType* VisitedArray, AccessSeqType* AccessSeq)
{
    AccessSeq->Array[AccessSeq->ArraySize] = VertexIndex;
    AccessSeq->ArraySize++;

    VisitedArray[VertexIndex] = VISITED_FLAG;
    VertexIndexType ColIndex;

    if(AccessSeq->ArraySize == AMG->CurVertexNum)//如果所有结点访问完成，退出。
    {
        return;
    }
    //GlobalCnt++;
    
    for(ColIndex = 0; ColIndex < AMG->CurVertexNum; ColIndex++)
    {
        //GlobalCycleCnt++;
        if(AMG->ArcArray[VertexIndex][ColIndex] != MAX_INT_TYPE_NUM && VisitedArray[ColIndex] == NOT_VISITED_FLAG)
        {
            DepthFirstSearchUseAMGraph(AMG, ColIndex, VisitedArray, AccessSeq);
            if(AccessSeq->ArraySize == AMG->CurVertexNum)//如果所有结点访问完成，退出。
            {
                break;
            }
        }
    }
}
参数名 描述
AMG 邻接矩阵。
VertexIndex 从哪个顶点索引号开始搜索。
VisitedArray 顶点访问数组。
AccessSeq 顶点访问顺序数组。

2、DFS（邻接表实现）

void DepthFirstSearchUseAGraph(AGraph* AG, VertexIndexType VertexIndex, VertexIndexType* VisitedArray, AccessSeqType* AccessSeq)
{
    AccessSeq->Array[AccessSeq->ArraySize] = VertexIndex;
    AccessSeq->ArraySize++;

    VisitedArray[VertexIndex] = VISITED_FLAG;
    //GlobalCnt++;

    if(AccessSeq->ArraySize == AG->VertexNum)//如果所有结点访问完成，退出。
    {
        return;
    }
    
    ArcNode* TmpArcNode = AG->Vertices[VertexIndex].FirstArcNodePtr;;
 
    while(TmpArcNode != NULL)
    {
        //GlobalCycleCnt++;
        if(VisitedArray[TmpArcNode->EndVertexIndex] == NOT_VISITED_FLAG)
        {
            DepthFirstSearchUseAGraph(AG, TmpArcNode->EndVertexIndex, VisitedArray, AccessSeq);
            if(AccessSeq->ArraySize == AG->VertexNum)//如果所有结点访问完成，退出。
            {
                break;
            }
        }
        TmpArcNode = TmpArcNode->NextNodePtr;
    }
}
参数名 描述
AG 邻接表。
VertexIndex 从哪个顶点索引号开始搜索。
VisitedArray 顶点访问数组。
AccessSeq 顶点访问顺序数组。

3、BFS（邻接矩阵实现）

void BreadthFirstSearchUseAMGraph(AMGraph* AMG, VertexIndexType VertexIndex, VertexIndexType* VisitedArray, AccessSeqType* AccessSeq)
{
    JudgeAllNullPointer(VisitedArray);
    JudgeAllNullPointer(AccessSeq);

    SqQueue* SQ              = NULL;
    VertexIndexType* TmpElem = (VertexIndexType*)MyMalloc(sizeof(VertexIndexType));
    VertexIndexType  i       = 0;

    InitSqQueue(&SQ,INT_TYPE_FLAG);//初始化循环顺序队   
    EnterSqQueue(SQ, &VertexIndex);//将第一个结点压入循环顺序队。
    VisitedArray[VertexIndex]              = VISITED_FLAG;
    AccessSeq->Array[AccessSeq->ArraySize] = VertexIndex;
    AccessSeq->ArraySize++;

    while(GetSqQueueLen(SQ) != 0)
    {
        PrintfSqQueue(SQ);
        LeaveSqQueue(SQ, TmpElem);
        for(i = 0; i < AMG->CurVertexNum; i++)
        {
            if(AMG->ArcArray[*TmpElem][i] != MAX_INT_TYPE_NUM && VisitedArray[i] == NOT_VISITED_FLAG)
            {
                EnterSqQueue(SQ, &i);
                VisitedArray[i]                        = VISITED_FLAG;
                AccessSeq->Array[AccessSeq->ArraySize] = i;
                AccessSeq->ArraySize++;
                if(AccessSeq->ArraySize == AMG->CurVertexNum)//如果所有结点访问完成，退出。
                {
                    break;
                }
            }
        }
        if(AccessSeq->ArraySize == AMG->CurVertexNum)//如果所有结点访问完成，退出。
        {
            break;
        }
    }

    DestroySqQueue(&SQ);
    free(TmpElem);
    TmpElem = NULL;

    Log("Breadth First Search Use AMGraph OK\n",Debug);
}
参数名 描述
AMG 邻接矩阵。
VertexIndex 从哪个顶点索引号开始搜索。
VisitedArray 顶点访问数组。
AccessSeq 顶点访问顺序数组。

感觉访问顺序数组满退出这一块，两次break，写成goto是不是好些，大家有想法的可以指点小弟一二。

4、BFS（邻接表实现）

void BreadthFirstSearchUseAGraph(AGraph* AG, VertexIndexType VertexIndex, VertexIndexType* VisitedArray, AccessSeqType* AccessSeq)
{
    JudgeAllNullPointer(VisitedArray);
    JudgeAllNullPointer(AccessSeq);

    SqQueue* SQ              = NULL;
    VertexIndexType* TmpElem = (VertexIndexType*)MyMalloc(sizeof(VertexIndexType));
    ArcNode*         TmpNode = NULL;

    InitSqQueue(&SQ,INT_TYPE_FLAG);//初始化循环顺序队   
    EnterSqQueue(SQ, &VertexIndex);//将第一个结点压入循环顺序队。
    VisitedArray[VertexIndex]              = VISITED_FLAG;
    AccessSeq->Array[AccessSeq->ArraySize] = VertexIndex;
    AccessSeq->ArraySize++;

    while(GetSqQueueLen(SQ) != 0)
    {
        LeaveSqQueue(SQ, TmpElem);
        TmpNode                                = AG->Vertices[*TmpElem].FirstArcNodePtr;
        while(TmpNode != NULL)
        {
            if(VisitedArray[TmpNode->EndVertexIndex] == NOT_VISITED_FLAG)
            {
                EnterSqQueue(SQ, &(TmpNode->EndVertexIndex));
                VisitedArray[TmpNode->EndVertexIndex]  = VISITED_FLAG;
                AccessSeq->Array[AccessSeq->ArraySize] = TmpNode->EndVertexIndex;
                AccessSeq->ArraySize++;
                if(AccessSeq->ArraySize == AG->VertexNum)//如果所有结点访问完成，退出。
                {
                    break;
                }
            }
            TmpNode = TmpNode->NextNodePtr;
        }
        if(AccessSeq->ArraySize == AG->VertexNum)//如果所有结点访问完成，退出。
        {
            break;
        }
    }

    DestroySqQueue(&SQ);
    free(TmpElem);
    TmpElem = NULL;
    Log("Breadth First Search Use AGraph OK\n",Debug);
}
参数名 描述
AG 邻接表。
VertexIndex 从哪个顶点索引号开始搜索。
VisitedArray 顶点访问数组。
AccessSeq 顶点访问顺序数组。

5、打印邻接矩阵遍历顺序

Status AMGraphTraverse(void (*Func)(AMGraph*,VertexIndexType,VertexIndexType*, AccessSeqType*),AMGraph* AMG, VertexIndexType VertexIndex)
{
    JudgeAllNullPointer(AMG);

    VertexIndexType* VisitedArray = (VertexIndexType*)MyCalloc(AMG->CurVertexNum, sizeof(VertexIndexType));
    AccessSeqType* AccessSeq      = (AccessSeqType*)MyCalloc(1, sizeof(AccessSeqType));
    AccessSeq->ArraySize          = 0;

    Func(AMG, VertexIndex, VisitedArray, AccessSeq);

    char* string = (char*)MyCalloc(STR_TYPE_SIZE, sizeof(char));
    CopyStr* PS  = (CopyStr*)malloc(sizeof(CopyStr));
    InitCopyStr(PS);
    ExecCopyStr(PS,"Traverse Use AMGraph               : [");
    VertexIndexType i;
    for(i = 0; i < AccessSeq->ArraySize; i++)
    {
        sprintf(string,"%d ,", AccessSeq->Array[i]);
        ExecCopyStr(PS,string);
    }
    PS->String[PS->StrEffectiveLen-1] = ']';
    ExecCopyStr(PS,"\n");

    free(AccessSeq);
    free(VisitedArray);
    AccessSeq    = NULL;
    VisitedArray = NULL;

    PS->String[PS->StrEffectiveLen] = '\0';
    Log(PS->String, Debug);
    DestroyCopyStr(PS);
    free(string);
    string       = NULL;
    return SuccessFlag;
}
参数名 描述
Func DFS或BFS函数指针。
AMG 邻接矩阵。
VertexIndex 从哪个顶点索引号开始搜索。

 6、打印邻接表遍历顺序

Status AGraphTraverse(void (*Func)(AGraph*,VertexIndexType,VertexIndexType*,AccessSeqType*),AGraph* AG, VertexIndexType VertexIndex)
{
    JudgeAllNullPointer(AG);

    VertexIndexType* VisitedArray = (VertexIndexType*)MyCalloc(AG->VertexNum, sizeof(VertexIndexType));
    AccessSeqType* AccessSeq      = (AccessSeqType*)MyCalloc(1, sizeof(AccessSeqType));
    AccessSeq->ArraySize          = 0;

    Func(AG, VertexIndex, VisitedArray, AccessSeq);

    char* string = (char*)MyCalloc(STR_TYPE_SIZE, sizeof(char));
    CopyStr* PS  = (CopyStr*)malloc(sizeof(CopyStr));
    InitCopyStr(PS);
    ExecCopyStr(PS,"Traverse Use AGraph                : [");
    VertexIndexType i;
    for(i = 0; i < AccessSeq->ArraySize; i++)
    {
        sprintf(string,"%d ,", AccessSeq->Array[i]);
        ExecCopyStr(PS,string);
    }
    PS->String[PS->StrEffectiveLen-1] = ']';
    ExecCopyStr(PS,"\n");

    free(AccessSeq);
    free(VisitedArray);
    AccessSeq    = NULL;
    VisitedArray = NULL;

    PS->String[PS->StrEffectiveLen] = '\0';
    Log(PS->String, Debug);
    DestroyCopyStr(PS);
    free(string);
    string       = NULL;
    return SuccessFlag;
}
参数名 描述
Func DFS或BFS函数指针。
AG 邻接表。
VertexIndex 从哪个顶点索引号开始搜索。

八、遍历算法效率分析

1、DFS

用邻接矩阵表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为O(n^2)。

用邻接表表示图，虽然有2e个表结点，但只需要扫描e个结点即可完成遍历，加上访问n个头节点的时间，时间复杂度为O(n+e)。文章来源地址https://www.toymoban.com/news/detail-777714.html

2、BFS

使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（n个元素），总的时间代价为O(n^2)。

用邻接表表示图，虽然有2e个表结点，但只需要扫描e个结点即可完成遍历，加上访问n个头节点的时间，时间复杂度为O(n+e)。

九、Linux编译测试

[gbase@czg2 Graph]$ make
gcc -Wall -Wextra -O3 ../Log/Log.c /APP/Tpl/Home/Default/PublicFunction/PublicFunction.c /APP/Tpl/Home/Default/PublicFunction/SqQueue/SqQueue.c Graph.c MinimumSpanningTree.c main.c -o TestGraph -I ../Log/ -I /APP/Tpl/Home/Default/PublicFunction/ -I ../Select/ -I /APP/Tpl/Home/Default/PublicFunction/SqQueue/
[gbase@czg2 Graph]$ ./TestGraph 
[2023-5]--[ Info  ]--Create Net Data                    : OK
[2023-5]--[ Info  ]--Create Undirection Net Use AMGraph : OK
[2023-5]--[ Debug ]--Printf AMGraph                     :
VertexArray    : [A ,B ,C ,D ,E ]
ArcArray       :
[32767 ,20    ,30    ,10    ,32767 ]
[20    ,32767 ,32767 ,32767 ,50    ]
[30    ,32767 ,32767 ,40    ,32767 ]
[10    ,32767 ,40    ,32767 ,60    ]
[32767 ,50    ,32767 ,60    ,32767 ]
CurVertexNum   : 5
CurArcNum      : 12
[2023-5]--[ Info  ]--Create Undirection Net Use AGraph  : OK
[2023-5]--[ Debug ]--Printf AGraph                      :
A : [(2, 30, 0x6f18b0),(1, 20, 0x6f1870),(3, 10, (nil))]
B : [(4, 50, 0x6f18d0),(0, 20, (nil))]
C : [(3, 40, 0x6f1910),(0, 30, (nil))]
D : [(4, 60, 0x6f1950),(2, 40, 0x6f1890),(0, 10, (nil))]
E : [(3, 60, 0x6f1990),(1, 50, (nil))]
VertexNum      : 5
ArcNum         : 12
[2023-5]--[ Debug ]--Traverse Use AMGraph               : [4 ,1 ,0 ,2 ,3 ]
[2023-5]--[ Debug ]--Traverse Use AGraph                : [4 ,3 ,2 ,0 ,1 ]
[2023-5]--[ Debug ]--Init SqQueue Normal
[2023-5]--[ Debug ]--Enter SqQueue Normal
[2023-5]--[ Debug ]--SqQueue Data   :
Data           : [ 4 ]
FrontIndex     : 0
RearIndex      : 1
SqQueueLen     : 1
Flag           : INT_TYPE_FLAG
[2023-5]--[ Debug ]--Leave SqQueue Normal
[2023-5]--[ Debug ]--Enter SqQueue Normal
[2023-5]--[ Debug ]--Enter SqQueue Normal
[2023-5]--[ Debug ]--SqQueue Data   :
Data           : [ 1 ,3 ]
FrontIndex     : 1
RearIndex      : 3
SqQueueLen     : 2
Flag           : INT_TYPE_FLAG
[2023-5]--[ Debug ]--Leave SqQueue Normal
[2023-5]--[ Debug ]--Enter SqQueue Normal
[2023-5]--[ Debug ]--SqQueue Data   :
Data           : [ 3 ,0 ]
FrontIndex     : 2
RearIndex      : 4
SqQueueLen     : 2
Flag           : INT_TYPE_FLAG
[2023-5]--[ Debug ]--Leave SqQueue Normal
[2023-5]--[ Debug ]--Enter SqQueue Normal
[2023-5]--[ Debug ]--Destroy SqQueue Normal
[2023-5]--[ Debug ]--Breadth First Search Use AMGraph OK
[2023-5]--[ Debug ]--Traverse Use AMGraph               : [4 ,1 ,3 ,0 ,2 ]
[2023-5]--[ Debug ]--Init SqQueue Normal
[2023-5]--[ Debug ]--Enter SqQueue Normal
[2023-5]--[ Debug ]--Leave SqQueue Normal
[2023-5]--[ Debug ]--Enter SqQueue Normal
[2023-5]--[ Debug ]--Enter SqQueue Normal
[2023-5]--[ Debug ]--Leave SqQueue Normal
[2023-5]--[ Debug ]--Enter SqQueue Normal
[2023-5]--[ Debug ]--Enter SqQueue Normal
[2023-5]--[ Debug ]--Destroy SqQueue Normal
[2023-5]--[ Debug ]--Breadth First Search Use AGraph OK
[2023-5]--[ Debug ]--Traverse Use AGraph                : [4 ,3 ,1 ,2 ,0 ]
[2023-5]--[ Info  ]--Destory Net Data                   : OK
[2023-5]--[ Info  ]--Destory Undirection Net Use AMGraph: OK
[2023-5]--[ Info  ]--Destory Undirection Net Use AGraph : OK

到了这里，关于数据结构与算法基础-学习-24-图的遍历之DFS（深度优先搜索）和BFS（广度优先搜索）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 算法数据结构——图的遍历之深度优先搜索算法（Depth First Search）

    算法数据结构——图的遍历之深度优先搜索算法（Depth First Search）

    深度优先搜索算法 （Depth First Search）：英文缩写为 DFS。是一种用于搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走。 深度优先搜索采用了回溯思想，该算法沿着树的深度遍历树的节点，会尽可能深的搜索树的分支。当节点 v 的所在边都己被探寻过，搜

    2024年02月09日
    浏览(32)
  • 【数据结构与算法】图的基本概念 | 邻接矩阵和邻接表 | 广度优先遍历和深度优先遍历

    【数据结构与算法】图的基本概念 | 邻接矩阵和邻接表 | 广度优先遍历和深度优先遍历

    🌠 作者：@ 阿亮joy. 🎆 专栏：《数据结构与算法要啸着学》 🎇 座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根 图是由顶点集合及顶点间的关系组成的一种数据结构：G = (V， E) ，其中： 顶点集合V = {x|x属于某

    2024年02月04日
    浏览(56)
  • 图的数据结构，系统学习图的基本概念、定义和建立，学会邻接矩阵、邻接表以及实现六度空间案例，遍历图的方式——广度、深度访问

    图的数据结构，系统学习图的基本概念、定义和建立，学会邻接矩阵、邻接表以及实现六度空间案例，遍历图的方式——广度、深度访问

    图 ：G = (V,E) Graph = (Vertex, Edge) V：顶点（数据元素）的有穷非空集合； E：边的有穷集合。 有向图 ：每条边都是有方向的     无向图 ：每条边都是无方向的   完全图 ：任意两点之间都有一条边相连    无向完全图：n个顶点，n(n-1)/2条边 无向完全图：n个顶点，n(n-1)条边 稀疏

    2023年04月22日
    浏览(30)
  • 数据结构 | 图的遍历

    数据结构 | 图的遍历

    使用邻接矩阵法存储图的信息，其中 一维矩阵 Vexs[] 存储节点信息 二维矩阵 Edges[][] 存储边的信息 一维矩阵 visited[] 记录当前节点是否被访问过，用于后面的遍历 本文所使用的图的结构如下： 对应的 Vexs[] 为：A,B,C,D,E,F（对应的数组下标从0到5） 对应的 Edges[][] 如下： 图的

    2024年02月04日
    浏览(28)
  • 24考研数据结构-图的存储结构邻接矩阵

    24考研数据结构-图的存储结构邻接矩阵

    【1】顶点的结点结构 ——————— | data | firstarc | ——————— data数据域：储存顶点vi firstarc链域：指向链表中第一个结点 【2】弧的结点结构 —————————— | adjvex | info | nextarc | —————————— adjvex邻接点域：与顶点vi邻接的点在图中的位置 info数据域

    2024年02月14日
    浏览(41)

  • 数据结构--5.3图的遍历（广度优先遍历）

    广度优先遍历：         广度优先遍历（BreadthFirstSearch），又称为广度优先搜索，简称BFS。 要实现对图的广度遍历，我们可以利用队列来实现。  （参考队列）（上述为结构）

    2024年02月10日
    浏览(31)
  • 【数据结构】图的广度优先遍历

    【数据结构】图的广度优先遍历

    广度优先遍历，类似于树的层次遍历，又是熟悉的队列实现。首先将第一个顶点添加到队列中，然后讲该顶点的所有邻接顶点都加入队列中，再将该顶点输出。如此重复直到遍历完整个图。 Q:队列，用于存放顶点。 front,rear:队头和队尾指针，用于入队和出队。 p:工作指针，用

    2024年02月05日
    浏览(32)
  • 【数据结构】图的创建与遍历

    【数据结构】图的创建与遍历

    图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。 线性表 ：线性关系，由直接前驱和直接后继组成。 树 ：层次关系，由父结点和孩子结点组成，每个结点最多有一个父结点（根

    2023年04月22日
    浏览(31)
  • 【数据结构】图的存储与遍历

    【数据结构】图的存储与遍历

    图是由顶点集合及顶点间的关系组成的一种数据结构：G = (V， E) 在有向图中，顶点对x, y是有序的，顶点对x，y称为顶点x到顶点y的一条边(弧)，x, y和y, x是两条不同的边。 在无向图中，顶点对(x, y)是无序的，顶点对(x,y)称为顶点x和顶点y相关联的一条边，这条边没有特定方向，

    2024年02月22日
    浏览(31)
  • 【数据结构】图的定义，存储，遍历

    【数据结构】图的定义，存储，遍历

    🎊专栏【数据结构】 🍔喜欢的诗句：更喜岷山千里雪 三军过后尽开颜。 🎆音乐分享【Dream It Possible】 大一同学小吉，欢迎并且感谢大家指出我的问题🥰 目录 🍔前言 🎁图的定义   🏳️‍🌈有向完全图 🏳️‍🌈无向完全图 🎁存储结构 🏳️‍🌈邻接矩阵  🎈代码

    2024年02月06日
    浏览(62)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包