本月博客排行
年度博客排行
-
第1名
青否云后端云 -
第2名
zw7534313 -
第3名
大家都说我很棒 - liyihz2008
- wy_19921005
- gengyun12
- hbxflihua
- e_e
- luxurioust
- dbagirl
- zysnba
- robotmen
- Alsmile
- gaozzsoft
- jywhltj
- cpongo1
- leslie26
- qepwqnp
- 解宜然
- cuityang
- sichunli_030
- gashero
- fantaxy025025
- zhangdaiscott
- vipbooks
- wallimn
- gdpglc
- ssydxa219
- ranbuijj
- javashop
- jickcai
- hanbaohong
- johnsmith9th
- appalese
- gaojingsong
- weiyides
- 淡看人生
- java-007
- zhangyi0618
- AVI
- laiyangdeli
- xpenxpen
- liunancun
- 龙哥IT
- conkeyn
- nychen2000
- lyndon.lin
- ouanui
- silverend
- jveqi
最新文章列表
图论 五 最短路径 最长路径
花几个算法的简易图:
一、 dijkstra算法:
dijkstra算法需要三个数据结构,a:一个存储已选节点,b:一个存储未选节点,c:一个存储需要不断更新的已经遍历的路径
算法流程:循环一下算法知道B为空:
1.选取一个节点为开始节点,遍历开始节点的连通的未访问节点
2.更新C,取C中总权重最 ...
寻找树形图中的最长路径
题目:
在一个迷宫中找距离最长的两个点。
迷宫可以看作是一个无根树,因此,这个问题等价与在一个树形图中找最远的两个节点,也叫做这个图的直径。
迷宫、树形图有个很好的特点:即任意两个节点之间的距离就是这两点之间的最短路径和最长路径,也可以说任意两个节点之间的距离一定的。
其算法为:
任选一点u为起点,对树进行BFS遍历,找出离u最远的点v。然后以v为起点,再进行BFS遍历, ...