队列(queue)是一种特殊的线性表,只允许在表的一端进行插入操作而在另一端进行删除的线性表。进行插入操作的端称为队尾,进行删除操作的一端称为队头。队列中没有数据元素时称为空队列。 队列的操作是按照先进先出(first in first out)或后进后出(last in last out)的原则进行的。因此,队列又被称为FIFO表。它的实现方式主要有顺序队列、链队列两种。   队列的抽象数据模型 数据元素:可以为任意类型,只要同属于一种数据类型即可; 数据关系:数据元素之间呈线性关系; 数据操作:对队列…

2020年9月21日 0条评论 15点热度 阅读全文

最短路径的概念 最短路径的问题是比较典型的应用问题。在图中,确定了起始点和终点之后,一般情况下都可以有很多条路径来连接两者。而边或弧的权值最小的那一条路径就称为两点之间的最短路径,路径上的第一个顶点为源点,最后一个顶点为终点。 图的最短路径的算法有很多,本文主要介绍狄克斯特拉(Dijkstra)提出的一种按照长度递增的次序产生的最短路径的算法。   Dijkstra算法介绍 Dijkstra算法的特点 Dijkstra算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题,算法最终得到一个最短路…

2018年4月7日 0条评论 14点热度 阅读全文

图的遍历是指从图中的任一顶点出发,对图中的所有顶点访问一次并且只访问一次。图的遍历是图的一种基本操作,图中的许多其他操作也都是建立在遍历的基础之上。在图中,没有特殊的顶点被指定为起始顶点,图的遍历可以从任何顶点开始。图的遍历主要有深度优先搜索和广度优先搜索两种方式。   深度优先搜索算法 算法的思想 从图中的某一个顶点x出发,访问x,然后遍历任何一个与x相邻的未被访问的顶点y,再遍历任何一个与y相邻的未被访问的顶点z……依次类推,直到到达一个所有邻接点都被访问的顶点为止;然后,依次回退到尚有邻接点未被访问…

2018年4月7日 0条评论 2点热度 阅读全文