Description 遍历一棵二叉树就是按某种次序系统地“访问”二叉树上的所有结点,并使每一个结点恰好被访问一次。所谓“访问”一个结点,是指对该结点的数据域进行某种处理,处理的内容依具体问题而定,通常比较简单。我们知道,遍历一个线性结构很容易,只须从开始结点出发顺序扫描每个结点即可。但是二叉树是一个非线性结构,每个结点可以有两个后继结点,因此需要寻找一种规律来系统地访问树中各结点。遍历运算的关键在于访问结点的“次序”,这种次序应保证二叉树上的每个结点均被访问一次且仅一次。    由定义可知,一棵二叉树由三部分组成…

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

转载链接:点击打开链接 Dijkstra算法是处理单源最短路径的有效算法,但它局限于边的权值非负的情况,若图中出现权值为负的边,Dijkstra算法就会失效,求出的最短路径就可能是错的。 这时候,就需要使用其他的算法来求解最短路径,Bellman-Ford算法就是其中最常用的一个。该算法由美国数学家理查德•贝尔曼(Richard Bellman, 动态规划的提出者)和小莱斯特•福特(Lester Ford)发明。 适用条件&范围: 单源最短路径(从源点s到其它所有顶点v); 有…

2016年7月29日 0条评论 9点热度 阅读全文

嗯图论的第二道题,刚刚有一点点入门的感觉www。 于是就把心得体会写下来啦。 题目概述: 主人公农夫有几片农场,然后农场里有各个农田(这个模型化为图的端点),然后各个农田之间有路径(这个模型化为图的边),然后有的边是正常的无向边,以及有的边是有项的虫洞。开始的时候时间为0,通过一条正常边会加时间,通过虫洞减去时间。 输入N(1-500),M(1-2500),W(1-100),然后输出能否通过一条路径回到过去,也就是模型中的负权环。 算法思想: 求负权显然的Bellman-Ford,可是还是太慢了要400多MS,不知…

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

一道裸的拓扑排序,回溯输出全部序列即可。还有就是我自己太懒,最后多出了一空行结果wa了一次,还查了半天。。。。 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #define N 310 using namespace std; int g[N][N]; int ru[N]; int vis[N]; int len…

2014年11月16日 0条评论 2点热度 阅读全文