技术标签: 算法 java 图论 最短路径 Java高阶数据结构 数据结构
图的最短路径问题!
图的基础知识博客:传送门
最短路径问题: 从在带权图的某一顶点出发,找出一条通往另一顶点的最短路径,最短也就是沿路径各边的权值总 和达到最小。
一共会讲解三种算法
单源最短路径问题: 给定一个图G = ( V , E ) G=(V,E)G=(V,E),求源结点s ∈ V 到图中每个结点v ∈ V 的最短路径。
多源最短路径问题: 就是找到每个顶点到除本身的顶点的最短路径
两顶点不连通,则不存在最短路径–>∞
在后面的讲解中,就不要联想到邻接矩阵了,这样脑子CPU都要烧烂了,代码实现需要邻接矩阵,而不是图就长成矩阵这么抽象的样子。
看原图去分析思考就行了,记住边的代码表达即可
如果你本来就是这样的,那真的太棒了
注意:带负权的图,可能可以找到最短路径,也可能找不到
判断方法:
则说明:一张图的最短路径,一定满足边数<= n-1
原因:
因为可以通过这个负权回路,导致一些最短路径趋近于负无穷大
(带负权一定要是有向图,无向图的话,负权边一定构成两个顶点的负权回路)
以下算法代码实现简单,重点看算法思想!
定义:(不懂没关系,最后我有详细的证明)
定义一个dist数组,这个数组记录出发点到其他点的最短路径
定义一个path数组,代表每个顶点的前一个节点
定义一个操作:“松弛”
松弛一个顶点,就是将其连通的所有边进行以下操作:
设此顶点为i,连通终点为j
判断:dist[i] + weight(i, j) < dist[j]
至于为什么叫松弛,这也是英译过来的。
一开始小范围的这个操作,只能涉及一些边和一些顶点,就像弹簧被压得很紧,这个操作会带向更多的边,弹簧也没那么紧了~
不理解也没所谓,不要纠结这个动词,不要纠结这个叫法!
步骤:
可以有两种理解方式:
获得最短路径:
例子:
动图演示:
来源:【算法】最短路径查找—Dijkstra算法_哔哩哔哩_bilibili
一样短会怎么样呢?
至少对这个顶点后续的延伸是没区别的,因为0到j的距离都一样,后续该怎么延伸出去还是怎么延伸出去
重要原因:图没有负权
我们按照算法思路先走一走
那么我们就断言第一代最短路径中最短的那条路径,就是“正确的”
- 这也是携带了为什么Dijkstra只能解决带非负权图的原因
- 就是因为,它的算法的前提,就是没有负权!
第一代最短路径最短那那条L,就不可能通过任何方式让其更短
- 因为这个点的其他路径就只能是第二代,或者更多
- 而这条路径,是通过第一代最短路径的另一些边的,而这些边本身就比L大,并且此后路径的边都是正的,必然比L大
那么我们就断言第一代最短路径中最短的那条路径L2,就是“正确的”
同样的道理,这条路径要么是一条边的,要么是两条边的
刚才为什么不一起选择7这个顶点呢?
- 【0到1】 比 【0到7】 短,所以可能【0到1】在到其他顶点,再回到7这个顶点
在第二代最短路径中,刚才的0松弛操作保证了目前看来最短路径为一条边的和最短路径为两条边的顶点在dist值最小
你会发现,如果你不对刚才的更新的顶点进行松弛,而是重复松弛之前的顶点,没有任何顶点更新,没有任何作用,则刚才的松弛操作,已经保证了这一点
而你可以这样理解,松弛就相当于在对账核对,核对完后,保证这一点
(这是本文章的核心思想)
- 即,局部范围内,他们是最短路径(在现在能触及的范围内,他们的dist值是正确的)
- 即,以出发点为标准,最多延伸两条边的子图范围内,他们都是最短路径
- 这个子图不包含所有的“两条边的路径”,不包含的部分也不需要出现,因为没有负权,包含在内的“两条边的路径”,是由上一次的最短路径顶点延伸出来的,那么这个条包含在子图内的“两条边的路径”,一定是比不包含的要短~
这一次,最短的是【0到7】,同样的原因,可以断言7此时是正确的最短路径
- 刚才的证明了此时7是这个范围内的最短路径,这就够了
- 后续不会再有到7路径更短的顶点了(别的路径只能增加)
同样的,以出发点为标准,最多延伸三条边的子图(<=3,一样的,不一定包含所有的“三边路径”和“两边路径”,一定包含“更有权威的”路径)范围内,他们都是最短路径
- 选择顶点6(此时顶点6)~
- 因为后续到这顶点就只能增了~
依照这个思路下去,所有顶点被标记,结束!
以【0到4】为例子
【0到4】=【0到5】+【5到4】
所以,一个最短路径的子路径为别的顶点的最短路径,所以可以通过下标的往回“跳”,得到真实路径
证明完毕~
/**
*
* @param src 出发点
* @param dist 要求把最短路径长存放在这个数组里
* @param path 要求将前面点存放在这个数组里
*/
public void dijkstra(char src, int[] dist, int[] path) {
//获取顶点下标
int srcIndex = getIndexOfV(src);
//初始化dist
Arrays.fill(dist, Integer.MAX_VALUE);
dist[srcIndex] = 0;//起始点
//初始化path
Arrays.fill(path, -1);
path[srcIndex] = srcIndex;//如果是前一个顶点是本身的话,则说明到达起始点
//定义visited数组
int n = arrayV.length;
boolean[] visited = new boolean[n];
//开始标记与松弛操作了
//由于我们知道每次循环都会标记一个,那么循环次数就知道了,所以我们就用特定的for循环去写
for (int i = 0; i < n; i++) {
//找dist最小值
int index = srcIndex;//这个无所谓
int min = Integer.MAX_VALUE;
for (int j = 0; j < n; j++) {
if(!visited[j] && dist[j] < min) {
index = j;
min = dist[j];
}
}
//标记
visited[index] = true;
//松弛
for (int j = 0; j < n; j++) {
//被必要松弛到标记的顶点的,因为没用(再之前的证明中),你要也可以
if(!visited[j] && matrix[index][j] != Integer.MAX_VALUE
&& dist[index] + matrix[index][j] < dist[j]) {
//松弛导致的更新操作,更新其路径为【0,index】延伸一条边【index,j】
dist[j] = dist[index] + matrix[index][j];
path[j] = index;
}
}
}
}
测试:
打印路径和路径长的方法:
public void printShortPath(char vSrc,int[] dist,int[] pPath) {
//1. 获取顶点下标
int srcIndex = getIndexOfV(vSrc);
int n = arrayV.length;
//2、遍历pPath数组 的n个 值,
// 每个值到起点S的 路径都打印一遍
for (int i = 0; i < n; i++) {
//自己到自己的路径不打印
if(i != srcIndex) {
ArrayList<Integer> path = new ArrayList<>();
int parentI = i;
while (parentI != srcIndex) {
path.add(parentI);
parentI = pPath[parentI];
}
path.add(srcIndex);
//翻转path当中的路径
Collections.reverse(path);
for (int pos : path) {
System.out.print(arrayV[pos] +" -> ");
}
System.out.println(dist[i]);
}
}
}
测试案例:
public static void testGraphDijkstra() {
String str = "syztx";
char[] array = str.toCharArray();
GraphByMatrix g = new GraphByMatrix(str.length(),true);
g.initArrayV(array);
g.addEdge('s', 't', 10);
g.addEdge('s', 'y', 5);
g.addEdge('y', 't', 3);
g.addEdge('y', 'x', 9);
g.addEdge('y', 'z', 2);
g.addEdge('z', 's', 7);
g.addEdge('z', 'x', 6);
g.addEdge('t', 'y', 2);
g.addEdge('t', 'x', 1);
g.addEdge('x', 'z', 4);
/*
搞不定负权值
String str = "sytx";
char[] array = str.toCharArray();
GraphByMatrix g = new GraphByMatrix(str.length(),true);
g.initArrayV(array);
g.addEdge('s', 't', 10);
g.addEdge('s', 'y', 5);
g.addEdge('t', 'y', -7);
g.addEdge('y', 'x', 3);
*/
int[] dist = new int[array.length];
int[] parentPath = new int[array.length];
g.dijkstra('s', dist, parentPath);
g.printShortPath('s', dist, parentPath);
}
public static void main(String[] args) {
testGraphDijkstra();
}
本质原理一样:
定义存放在堆里面的类:
class Point {
int index;
int minPath;
}
每次松弛都向堆里面放这个对象(而不是改变堆里面对应index的值)
取堆顶元素
如果这个元素被标记过,达咩,不要(continue)
如果这个元素没有被标记过,哟西,标记它,并且对其进行松弛操作
而优化后是适合稀疏图的,因为松弛入堆操作的次数可以认为是C常数,那么复杂度为O(N*log2N)
定义Point类:
static class Point {
int indexV;
int distValue;
public Point(int indexV, int distValue) {
this.indexV = indexV;
this.distValue = distValue;
}
}
核心方法:
/**
*
* @param src 出发点
* @param dist 要求把最短路径长存放在这个数组里
* @param path 要求将前面点存放在这个数组里
*/
public void pQDijkstra(char src,int[] dist,int[] path) {
//获得顶点下标
int srcIndex = getIndexOfV(src);
//初始化dist
Arrays.fill(dist, Integer.MAX_VALUE);
dist[srcIndex] = 0;//起始点
//初始化path
Arrays.fill(path, -1);
path[srcIndex] = srcIndex;//如果是前一个顶点是本身的话,则说明到达起始点
//定义visited数组
int n = arrayV.length;
boolean[] visited = new boolean[n];
//定义小根堆
PriorityQueue<Point> queue = new PriorityQueue<Point>(
(o1, o2) -> {
return o1.distValue - o2.distValue;
}
);
queue.offer(new Point(srcIndex, 0));
while(!queue.isEmpty()) {
Point point = queue.poll();
int index = point.indexV;
//被标记过,达咩!
if(visited[index]) {
continue;
}
//标记
visited[index] = true;
//松弛
for (int j = 0; j < n; j++) {
//被必要松弛到标记的顶点的,因为没用(再之前的证明中),你要也可以
if(!visited[j] && matrix[index][j] != Integer.MAX_VALUE
&& dist[index] + matrix[index][j] < dist[j]) {
//松弛导致的更新操作,更新其路径为【0,index】延伸一条边【index,j】
dist[j] = dist[index] + matrix[index][j];
path[j] = index;
queue.offer(new Point(j, dist[j]));
}
}
}
}
测试:
g.pQDijkstra('s', dist, parentPath);
g.printShortPath('s', dist, parentPath);
public static void main(String[] args) {
testGraphDijkstra();
}
结果一致:
如果把Dijkstra算法称为深度优先,那么Bellman-Ford算法就是广度优先,也更加直接与粗暴
与Dijkstra算法不同,其可以解决带负权的图的最短路径问题!
用到Dijkstra用过的操作:
不同的是它的算法步骤:
获得最短路径:
例子:
动图演示:
来源:【熊羊一锅鲜】Ep.13 单源最短路径Bellman-Ford算法及SPFA算法_哔哩哔哩_bilibili
一些点在Dijkstra的证明那已经讲过了
你也会发现,一开始如果先松弛的不是出发点,或者是“已经有路径的顶点”,这个松弛操作是没有意义的,因为这个顶点的dist值为∞
这一点,是 通过松弛操作来保证 的,原本Dijkstra算法没有保证这个子图的完整性,而BF算法由于每次都是松弛所有顶点,所以这个子图是完整的~
如第一代子图(第一次循环的结果):
如第二代子图(第二次循环的结果):
如第三代子图(第三次循环的结果):
你可能有一个错觉:这不是已经涉及所有顶点了吗,那么这就是在全局范围内的正确?
否,因为这里限制路径长最大是“三条边”,在这个限制下是正确的
- 例如【0到6】最短为三步,再走一步到7确实是11<12但是,这就是四步了呀
如第四代子图(第四次循环的结果):
到了第五代子图的时候(第五次循环的结果):
其实 被松弛涉及到的顶点i有更新的条件 是:顶点j(顶点j松弛后涉及到了顶点i)更新过
而你也发现了这个算法产生了大量的没用操作
- 如果先对“后面”的顶点松弛,可能没有作用
- 假设此次是第n次循环,那么一个顶点目前最短路径边数小于等于n-2的顶点
- 例如第二次循环的时候,出发点没必要松弛
- 第三次循环的时候,最短路径边数为1的顶点没有必要松弛
- 因为松弛完后最多为两条边,而两条边的时候在第二代子图(第二次循环结果)中,已经是得到最短的了
- 所以没有必要!
你可能会觉得,先松弛出发点,那么可能“后面的顶点”也会链式的被更新到
而我们只需要保证这一个严格成立即可
第N代最短路径中“边最长为N”的子图范围内,各个顶点的dist值在这个局部范围内【限制路径最多有N条边】是正确的,是最短的
最坏的情况下,就是完全“逆行”,即使这样,每一代都能够满足这一点
动图分析:(抽象)
答:不用,理由就是到达第N - 1次循环,结果是第N-1代子图,这已经到达了“全局范围”,所有顶点的dist值最短路径都是正确的。
所有的路径本身就小于等于N - 1,在最后一次循环更新的顶点,则说明其路径达到最长值:n-1条边
松弛的作用结果是延伸刚才的路径,那么刚才的路径已经是边数最大,松弛不会成功,没有必要继续松弛了
如果是带负权回路的,继续松弛一直都会更新
证明完毕~
//这也是判断是否有负权回路的算法
public boolean bellmanFord(char src,int[] dist,int[] path) {
//获得顶点下标
int srcIndex = getIndexOfV(src);
//初始化dist
Arrays.fill(dist, Integer.MAX_VALUE);
dist[srcIndex] = 0;//起始点
//初始化path
Arrays.fill(path, -1);
path[srcIndex] = srcIndex;//如果是前一个顶点是本身的话,则说明到达起始点
int n = arrayV.length;
//循环n-1次,每次松弛一个顶点
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
if(matrix[j][k] != Integer.MAX_VALUE &&
matrix[j][k] + dist[j] < dist[k]) {
dist[k] = matrix[j][k] + dist[j];
path[k] = j;
}
}
}
}
//检测负权回路
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
//至于一样短的情况下,无所谓,这就是最短路径不唯一呗~
//
if (matrix[i][j] != Integer.MAX_VALUE
&& matrix[i][j] + dist[i] < dist[j]) {
return false; //false代表了有负权回路
}
}
}
return true;
}
测试案例:
public static void testGraphBellmanFord() {
String str = "syztx";
char[] array = str.toCharArray();
GraphByMatrix g = new GraphByMatrix(str.length(),true);
g.initArrayV(array);
g.addEdge('s', 't', 6);
g.addEdge('s', 'y', 7);
g.addEdge('y', 'z', 9);
g.addEdge('y', 'x', -3);
g.addEdge('z', 's', 2);
g.addEdge('z', 'x', 7);
g.addEdge('t', 'x', 5);
g.addEdge('t', 'y', 8);
g.addEdge('t', 'z', -4);
g.addEdge('x', 't', -2);
//负权回路实例
// g.addEdge('s', 't', 6);
// g.addEdge('s', 'y', 7);
// g.addEdge('y', 'z', 9);
// g.addEdge('y', 'x', -3);
// g.addEdge('y', 's', 1);
// g.addEdge('z', 's', 2);
// g.addEdge('z', 'x', 7);
// g.addEdge('t', 'x', 5);
// g.addEdge('t', 'y', -8);
// g.addEdge('t', 'z', -4);
// g.addEdge('x', 't', -2);
int[] dist = new int[array.length];
int[] parentPath = new int[array.length];
boolean flg = g.bellmanFord('s', dist, parentPath);
if(flg) {
g.printShortPath('s', dist, parentPath);
}else {
System.out.println("存在负权回路");
}
}
public static void main(String[] args) {
testGraphDijkstra();
}
测试一个不带负权回路的案例:
测试带负权回路的:
刚才提到:
那么我们只需要松弛更新了的顶点就好了呀,
结合BF的视角:
- 每一次循环更新的顶点,设他们的集合为set1
- 下一次循环更新的顶点,设他们的集合为set2
要想满足BF算法的思想:
- set1的整体要在set2的整体前松弛完才行
- 才能有第一代子图—第二代子图—第三代子图这样的效果
所以用到数据结构:队列
步骤就是:
显然,这个算法没法判断负权回路的存在,会死循环下去~
public void queueBellmanFord(char src,int[] dist,int[] path) {
//获得顶点下标
int srcIndex = getIndexOfV(src);
//初始化dist
Arrays.fill(dist, Integer.MAX_VALUE);
dist[srcIndex] = 0;//起始点
//初始化path
Arrays.fill(path, -1);
path[srcIndex] = srcIndex;//如果是前一个顶点是本身的话,则说明到达起始点
int n = arrayV.length;
//定义一个队列
Queue<Integer> queue = new LinkedList<>();
queue.offer(srcIndex);
//开始循环松弛
while(!queue.isEmpty()) {
int top = queue.poll();
for (int i = 0; i < n; i++) {
if (matrix[top][i] != Integer.MAX_VALUE
&& matrix[top][i] + dist[top] < dist[i]) {
dist[i] = matrix[top][i] + dist[top];
path[i] = top;
queue.offer(i);
}
}
}
}
测试:
public static void testGraphBellmanFord() {
String str = "syztx";
char[] array = str.toCharArray();
GraphByMatrix g = new GraphByMatrix(str.length(),true);
g.initArrayV(array);
g.addEdge('s', 't', 6);
g.addEdge('s', 'y', 7);
g.addEdge('y', 'z', 9);
g.addEdge('y', 'x', -3);
g.addEdge('z', 's', 2);
g.addEdge('z', 'x', 7);
g.addEdge('t', 'x', 5);
g.addEdge('t', 'y', 8);
g.addEdge('t', 'z', -4);
g.addEdge('x', 't', -2);
int[] dist = new int[array.length];
int[] parentPath = new int[array.length];
g.queueBellmanFord('s', dist, parentPath);
g.printShortPath('s', dist, parentPath);
}
public static void main(String[] args) {
testGraphDijkstra();
}
M是边的数量,N是顶点的个数
则BF算法的时间复杂度为O(N * M),而大部分情况下SPFA算法的时间复杂度为O(M),最坏情况是O(N * M)
如果是稠密图的话,M会变得很大很大,两个算法的时间复杂度都会变得很大!
但是,值得注意的是:根据相邻顶点之间的权值,要记录下来每个顶点“一条边的路径”!否则这个算法没有用武之地
并且:最外层循环的循环遍历的应该对应的是中间节点
如果外两层是i,j循环(路线【i到j】),然后最内层循环是k循环(中间节点),这样子是很局限的,因为这i到j再k循环结束后,就被确定了唯一的最短路径,而不是在单单这一次就确定了,这是很不合理的。
- 因为在后面的变化中,i到j的路线,是很有可能被改变的,而这种写法,后续是没法改掉的!
正确的应该是最外层是k循环(中间节点),内两层是i,j循环(路线【i到j】),这样才能保证路径一定能被发现,并且后续【i到j】的路径也能会应变,直到全部循环结束而被确立下来~
定义:
左图为:一个连通图
右图为:它的dist二维数组(初始状态,未开始算法)
可见时间复杂度为:O(N3)
推荐:Ep.23 弗洛伊德Floyd-Warshall算法_哔哩哔哩_bilibili
public void floydWarShall(int[][] dist, int[][] path) {
//初始化dist和path
int n = arrayV.length;
for (int i = 0; i < n; i++) {
Arrays.fill(dist[i], Integer.MAX_VALUE);
Arrays.fill(path[i], -1);
}
//每一个顶点的第一代子图,记录在dist和path中,现在局部的最短路径
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(matrix[i][j] != Integer.MAX_VALUE) {
dist[i][j] = matrix[i][j];
path[i][j] = i;//这一行的上一个就是i
}else {
path[i][j] = -1;//不存在路径
}
if(i == j) {
dist[i][j] = 0;
path[i][j] = j;//跳回本身
}
}
}
//进行算法,每个顶点都当一回中介点
//每个顶点都被当做一次起始点,终点
//一个点即使起始点有时中介点又是终点,好像也无所谓
//只要满足那个方程!
//顺序完全没关系~
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
//规定k代表的是中介点,i为起始点,j为终点
boolean flag = dist[i][k] != Integer.MAX_VALUE
&& dist[k][j] != Integer.MAX_VALUE
&& dist[i][k] + dist[k][j] < dist[i][j];
//取不取等无所谓,只是不同最短路径的区别罢了
if (flag) {
dist[i][j] = dist[i][k] + dist[k][j];
path[i][j] = path[k][j];//【i,j】以【k,j】为子路径
}
}
}
}
}
测试:
public static void testGraphFloydWarShall() {
String str = "12345";
char[] array = str.toCharArray();
GraphByMatrix g = new GraphByMatrix(str.length(),true);
g.initArrayV(array);
g.addEdge('1', '2', 3);
g.addEdge('1', '3', 8);
g.addEdge('1', '5', -4);
g.addEdge('2', '4', 1);
g.addEdge('2', '5', 7);
g.addEdge('3', '2', 4);
g.addEdge('4', '1', 2);
g.addEdge('4', '3', -5);
g.addEdge('5', '4', 6);
int[][] dist = new int[array.length][array.length];
int[][] path = new int[array.length][array.length];
g.floydWarShall(dist,path);
for (int i = 0; i < array.length; i++) {
g.printShortPath(array[i],dist[i],path[i]);
//把一行一行传过去~
//一行代表一个顶点到其他顶点的最短路径
}
}
public static void main(String[] args) {
testGraphFloydWarShall();
}
文章到此结束!谢谢观看
可以叫我 小马,我可能写的不好或者有错误,但是一起加油鸭!这就是最短路径问题的全部内容了,如果有什么不懂可以留言/私信讨论!
文章浏览阅读1k次。通过使用ajax方法跨域请求是浏览器所不允许的,浏览器出于安全考虑是禁止的。警告信息如下:不过jQuery对跨域问题也有解决方案,使用jsonp的方式解决,方法如下:$.ajax({ async:false, url: 'http://www.mysite.com/demo.do', // 跨域URL ty..._nginx不停的xhr
文章浏览阅读2k次。关于在 Oracle 中配置 extproc 以访问 ST_Geometry,也就是我们所说的 使用空间SQL 的方法,官方文档链接如下。http://desktop.arcgis.com/zh-cn/arcmap/latest/manage-data/gdbs-in-oracle/configure-oracle-extproc.htm其实简单总结一下,主要就分为以下几个步骤。..._extproc
文章浏览阅读1.5w次。linux下没有上面的两个函数,需要使用函数 mbstowcs和wcstombsmbstowcs将多字节编码转换为宽字节编码wcstombs将宽字节编码转换为多字节编码这两个函数,转换过程中受到系统编码类型的影响,需要通过设置来设定转换前和转换后的编码类型。通过函数setlocale进行系统编码的设置。linux下输入命名locale -a查看系统支持的编码_linux c++ gbk->utf8
文章浏览阅读750次。今天准备从生产库向测试库进行数据导入,结果在imp导入的时候遇到“ IMP-00009:导出文件异常结束” 错误,google一下,发现可能有如下原因导致imp的数据太大,没有写buffer和commit两个数据库字符集不同从低版本exp的dmp文件,向高版本imp导出的dmp文件出错传输dmp文件时,文件损坏解决办法:imp时指定..._imp-00009导出文件异常结束
文章浏览阅读143次。当下是一个大数据的时代,各个行业都离不开数据的支持。因此,网络爬虫就应运而生。网络爬虫当下最为火热的是Python,Python开发爬虫相对简单,而且功能库相当完善,力压众多开发语言。本次教程我们爬取前程无忧的招聘信息来分析Python程序员需要掌握那些编程技术。首先在谷歌浏览器打开前程无忧的首页,按F12打开浏览器的开发者工具。浏览器开发者工具是用于捕捉网站的请求信息,通过分析请求信息可以了解请..._初级python程序员能力要求
文章浏览阅读7.6k次,点赞2次,收藏6次。@Service标注的bean,类名:ABDemoService查看源码后发现,原来是经过一个特殊处理:当类的名字是以两个或以上的大写字母开头的话,bean的名字会与类名保持一致public class AnnotationBeanNameGenerator implements BeanNameGenerator { private static final String C..._@service beanname
文章浏览阅读6.9w次,点赞73次,收藏463次。1.前序创建#include<stdio.h>#include<string.h>#include<stdlib.h>#include<malloc.h>#include<iostream>#include<stack>#include<queue>using namespace std;typed_二叉树的建立
文章浏览阅读7.1k次。在Asp.net上使用Excel导出功能,如果文件名出现中文,便会以乱码视之。 解决方法: fileName = HttpUtility.UrlEncode(fileName, System.Text.Encoding.UTF8);_asp.net utf8 导出中文字符乱码
文章浏览阅读2.1k次,点赞4次,收藏23次。第一次实验 词法分析实验报告设计思想词法分析的主要任务是根据文法的词汇表以及对应约定的编码进行一定的识别,找出文件中所有的合法的单词,并给出一定的信息作为最后的结果,用于后续语法分析程序的使用;本实验针对 PL/0 语言 的文法、词汇表编写一个词法分析程序,对于每个单词根据词汇表输出: (单词种类, 单词的值) 二元对。词汇表:种别编码单词符号助记符0beginb..._对pl/0作以下修改扩充。增加单词
文章浏览阅读773次。我在使用adb.exe时遇到了麻烦.我想使用与bash相同的adb.exe shell提示符,所以我决定更改默认的bash二进制文件(当然二进制文件是交叉编译的,一切都很完美)更改bash二进制文件遵循以下顺序> adb remount> adb push bash / system / bin /> adb shell> cd / system / bin> chm..._adb shell mv 权限
文章浏览阅读6.8k次,点赞12次,收藏125次。1. 单目相机标定引言相机标定已经研究多年,标定的算法可以分为基于摄影测量的标定和自标定。其中,应用最为广泛的还是张正友标定法。这是一种简单灵活、高鲁棒性、低成本的相机标定算法。仅需要一台相机和一块平面标定板构建相机标定系统,在标定过程中,相机拍摄多个角度下(至少两个角度,推荐10~20个角度)的标定板图像(相机和标定板都可以移动),即可对相机的内外参数进行标定。下面介绍张氏标定法(以下也这么称呼)的原理。原理相机模型和单应矩阵相机标定,就是对相机的内外参数进行计算的过程,从而得到物体到图像的投影_相机-投影仪标定
文章浏览阅读2.2k次。文章目录Wayland 架构Wayland 渲染Wayland的 硬件支持简 述: 翻译一篇关于和 wayland 有关的技术文章, 其英文标题为Wayland Architecture .Wayland 架构若是想要更好的理解 Wayland 架构及其与 X (X11 or X Window System) 结构;一种很好的方法是将事件从输入设备就开始跟踪, 查看期间所有的屏幕上出现的变化。这就是我们现在对 X 的理解。 内核是从一个输入设备中获取一个事件,并通过 evdev 输入_wayland