`
lee_3do
  • 浏览: 25741 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

一些常用的数据结构(四):图

阅读更多

 队列比栈更简单,无非就是个有队头和队尾指针,两端操作的FIFO结构罢了,不写了。。。

图的广度优先遍历算法:

1.将顶点加入队列,标记为已到达

2.将队首元素出队,找到与他相邻且未标记的元素入队。

3.循环2直到队空。

深度优先遍历算法:

对于最新发现的顶点,如果它还有以此为起点而未探测到的边,就沿此边继续汉下去。当结点v的所有边都己被探寻过,搜索将回溯到发现结点v有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点,则选择其中一个作为源结点并重复以上过程,整个进程反复进行直到所有结点都被发现为止。

 

迪杰斯特拉算法描述如下:
1)arcs[i,j]表示弧<vi,vj>上的权值。若<vi,vj>不存在,则置arcs[i,j]为∞(在本程序中为MAXCOST)。S为已找到从v出发的最短路径的终点的集合,初始状态为空集。那么,从v出发到图上其余各顶点vi可能达到的最短路径长度的初值为D[i]=arcs[Locate Vex(G,v),i] vi∈V
2)选择vj,使得D[j]=Min{D[i] | vi∈V-S}
3)修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。如果D[j]+arcs[j,k]<D[k] 则修改D[k]为D[k]=D[j]+arcs[j,k]

 

分享到:
评论

相关推荐

    数据结构(严蔚敏版)

    这本书深入浅出地介绍了各种常用的数据结构以及它们的算法实现,对于理解和掌握数据结构的基础知识具有极大的帮助。 书中涵盖了以下几个关键的数据结构: 1. **线性结构**:包括数组、链表(单链表、双向链表)、...

    数据结构高分笔记

    为了更好地理解和掌握算法设计题,书中还介绍了一些常用的算法设计思想: 1. **搜索算法**: - **深度优先搜索(DFS)**:沿着图的某条路径尽可能深地搜索节点。 - **广度优先搜索(BFS)**:从根节点开始,逐层...

    数据结构实验与实训教程.rar

    7. 附录:可能包含一些参考资料、常用数据结构和算法的复杂度总结等。 通过这个实训教程,学习者将不仅了解数据结构的理论知识,还能通过实践提升编程能力,为未来的软件开发和算法设计打下坚实的基础。在学习过程...

    数据结构实验指导书.doc

    数据结构是一门核心基础课程,主要介绍线性结构、树型结构、图状结构三种逻辑结构的特点和在计算机内的存储方法,并在此基础上介绍一些典型算法及其时、空效率分析。本课程的主要任务是研究数据的逻辑关系以及这种...

    数据结构与算法分析C++描述习题答案

    8. **第8章:不相交集合** - 解释不相交集合数据结构的工作原理及其在图算法中的应用。 9. **第9章:图算法** - 探讨图的基本概念,包括图的表示方法、图遍历算法(如深度优先搜索、广度优先搜索)、最短路径算法...

    数据结构与算法分析java版

    - **章节简介**:二叉树是一种常用的非线性数据结构,本章详细介绍了其特性和应用。 - **核心知识点**: - 二叉树的基本定义及性质 - 二叉搜索树的构建与查询 - 平衡二叉树的概念与平衡策略 - 二叉树的遍历方法...

    数据结构课后习题答案

    本书涵盖了数据结构的基本概念、数学基础、算法分析、列表、栈、队列、二叉树、通用树、内部排序、文件处理与外部排序、搜索、索引、图、列表和数组复审、高级树结构、分析技巧以及计算限制等内容。 #### 二、数据...

    数据结构电子教材(C#版)

    - **全书结构**:全书共分8章,内容涵盖了数据结构的基础知识、常用数据结构(线性表、栈和队列、串和数组、树型结构、图结构)的应用、排序和查找算法及其在.NET框架中的实现。 - **第一章:基础概念介绍** - 数据...

    数据结构——c#版(国内第一本c#数据结构书)

    - **第2章至第6章**:依次介绍了线性表、栈和队列、串和数组、树型结构、图结构等常用数据结构。每章都会详细介绍各种数据结构的特点、应用场景以及实现方式,并辅以.NET框架中的相关实现示例。 - **第7、8章**:...

    数据结构C#描述教程

    - **章节分布**:全书共分为8章,涵盖了数据结构的基本概念、常用数据结构(如线性表、栈、队列、串、数组、树型结构和图结构)及其在.NET框架中的应用,以及排序和查找算法等内容。 - **重点知识点**: - 第1章...

    代码实现基于严蔚敏编著《数据结构(C语言版)》,考研专业408计算机四大课程1-数据结构.zip

    C语言中的各种数据结构都有其优缺点,下面列举一些常见的数据结构的优缺点: 数组: 优点:访问和修改元素的速度非常快,适用于需要频繁读取和修改数据的场合。 缺点:数组的长度是固定的,不适合存储大小不固定的...

    数据结构与算法分析(Java版)

    ### 数据结构与算法分析(Java版):关键知识点解析 #### 一、概述 《数据结构与算法分析(Java版)》是一本由Robert Lafore撰写的书籍,旨在通过Java编程语言来介绍实用的数据结构与算法知识。本书适用于已经具备...

    数据结构 C#版 有兴趣的可以下来学习. 对学习数据结构很有好处.

    - 第2章至第6章分别讨论了线性表、栈和队列、串和数组、树型结构和图结构等常用的数据结构及其应用,并介绍了.NET框架中的相关数据结构。 - 第7、8章分别探讨了排序和查找的常见方法及其在.NET框架中的应用。 2. ...

    BUAA数据结构期末考试通常涵盖数据结构的基本概念.pdf

    #### 二、常用数据结构 ##### 1. 线性结构 - **数组**:数组是一种使用连续内存空间来存储相同类型数据元素的数据结构。它提供了快速的随机访问能力,但插入和删除操作较为耗时。 - **链表**:链表是一种通过指针...

    严蔚敏—数据结构(教材)

    教材分为两大部分内容:前半部分讨论了线性表、栈、队列、串、数组、广义表、树和二叉树以及图等基本数据结构及其应用;后半部分则侧重于查找和排序算法的实现方法,并对这些方法进行时间上的定性或定量分析和比较。...

    殷人昆数据结构课后答案rar

    掌握基础数据结构后,可以进一步研究高级数据结构,如B树、B+树、Trie树、哈希表等,这些都是数据库和搜索引擎等领域常用的数据结构。此外,学习动态规划、贪心算法和回溯法等算法思想,也是提升解决问题能力的重要...

Global site tag (gtag.js) - Google Analytics