实现程序如下 #include <iostream> #include "SparseGraph.h" #include "ReadGraph.h" #include "BellmanFord.h" using namespace std; int main() { string filename = "testG2.txt"; //string filename = "testG_negative_circle.txt"; int V = 5; SparseGraph<int> g = S…

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

(1)首先取出节点0放入队列中 (2)开始遍历,首先将列首的元素0取出队列,然后将与0相连接的节点1,2,5,6,推入队列 (3)继续将队首的元素1取出队列,然后将与节点1相连接的节点0推入队列,由于节点0已经在队列中,所以不需要操作,继续将队首的元素2取出队列,此时与2连接的节点0已经在队列中,也不进行操作;继续将队首的元素5取出队列,然后将与5连接的节点0,3,4推入队列中,由于0已经在队列中,所以只推入3和4, (4)继续取出队首的元素6,然后由于与6相连接的节点0和4都已经在队列中,所以不操作 (5)继续将…

2018年11月28日 0条评论 0点热度 阅读全文

图的遍历:深度优先遍历 (1)首先遍历节点0,与0连接的节点有1,2,5,6,那么先遍历节点1,下面再看与节点1相连的是节点0,节点0已经遍历过了,那么继续遍历节点2,与2连接的节点是0,节点0已经遍历过了,那么开始遍历节点5, (2)与5连接的节点有0,3,4,节点0已经遍历过了,那么开始遍历节点3,3没有被遍历过,记录下3,与节点3连接的节点是4和5,首先4没有被遍历过,记录下4,继续查看与4连接的节点3,5,6,前两个节点3和5都遍历过了,只有节点6没有被遍历过,把6记录下来, (3)与节点6连接的有节点0和…

2018年11月27日 0条评论 0点热度 阅读全文

package demo; /* 字符串匹配算法 */ public class StringKMP { //找出从第一个字符开始 子串T在主串S的第一个位置 如果没有则返回-1 public static int index(String S, String T) { int tag = 0; int i = 0; int j = 0; char[] s = S.toCharArray(); char[] t = T.toCharArray(); while (i < s.length &&…

2018年11月27日 0条评论 0点热度 阅读全文

本文出于微信公众号上的文章,非原创 字符匹配场景 字符串匹配是计算机的基本任务之一。举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一个字符串"ABCDABD"? 许多算法可以完成这个任务,Knuth-Morris-Pratt算法(简称KMP)是最常用的之一。它以三个发明者命名,起头的那个K就是著名科学家Donald Knuth。 这种算法不太容易理解,网上有很多解释,但读起来都很费劲。直到读到Jake Boxer的文章,我才真正理解这种算法。下面,我用自己的语言,…

2018年11月24日 0条评论 0点热度 阅读全文

部分背包问题是基于贪心法的基本思想。 何谓贪心法,只要你够贪心,就能领略贪心算法之精髓。 部分背包问题和0/1背包问题的区别就是:部分背包问题中的单个物品,可以取一部分装入背包。而0/1背包问题则是要么全部拿走,要么一无所有(这里引用了LOL卡牌大师的台词)。 那么作为一个so greed的你,肯定应该知道按照什么顺序拿物品的把。没错,看着值钱的先抢! 这里所说的值钱,指的是单位重量所产生的价值越大(即value/weight的比值越大)。那么问题很简单咯~,把"值钱"的东西排在前面,每次拿抢的时候,问问看背包君够…

2018年11月9日 0条评论 0点热度 阅读全文

部分背包问题是基于贪心法的基本思想。 何谓贪心法,只要你够贪心,就能领略贪心算法之精髓。 部分背包问题和0/1背包问题的区别就是:部分背包问题中的单个物品,可以取一部分装入背包。而0/1背包问题则是要么全部拿走,要么一无所有(这里引用了LOL卡牌大师的台词)。 那么作为一个so greed的你,肯定应该知道按照什么顺序拿物品的把。没错,看着值钱的先抢! 这里所说的值钱,指的是单位重量所产生的价值越大(即value/weight的比值越大)。那么问题很简单咯~,把"值钱"的东西排在前面,每次拿抢的时候,问问看背包君够…

2018年11月9日 0条评论 0点热度 阅读全文

二叉搜索树 二叉搜索树是二叉树的的一种,只不过多了个限制条件,即左子树节点的值都小于该点,右子树节点的值都大于该点。 定义: // 树节点 template <typename T> class Node { public: T key; Node* parent; Node* left; Node* right; Node(T k, Node* p = nullptr, Node* l = nullptr, Node* r = nullptr) : key(k), parent(p), left(l)…

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

“看毛片”算法可以说是许多人学习数据结构路上的一道坎,虽说代码并不算难,但总是写了就忘,其算法思想也是难以理解。其实多写几遍就会发现,也就那么回事。 主要思想: kmp算法主要是通过一个next数组来加速匹配的过程,这个next数组也称为失配数组。现在我们来考虑下面这种情况,母串与匹配串匹配到了如图箭头位置,但此时A和B并不匹配,怎么办呢?注意到图中蓝色部分是相等的子串,因此我们直接移动匹配串让A和C进行比较。这就实现了加速。 上面的直接移动就是利用了next数组,next数组保存的是当匹配串中这个位置失配以后,可…

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

//平衡二叉树,或者称为AVL树 #include<iostream> using namespace std; typedef int status; #define true 1 #define false 0 #define LH +1 //左高 #define EH 0 //等高 #define RH -1 //右高 //二叉链表结点结构定义 typedef struct Bitnode { int data; int bf; //储存结点的平衡因子 struct Bitnode *left,*…

2018年10月31日 0条评论 0点热度 阅读全文