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

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

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

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