数据结构基础--图(下)

1-1在一个有权无向图中,若b到a的最短路径距离是12,且c到b之间存在一条权为2的边,则c到a的最短路径距离一定不小于10。
这肯定是对的,a-b最小是12的话,假设a-c最小是x,那么x+2>=12(为啥?因为你经过c到b的距离不可能大于最短路径)

2-1我们用一个有向图来表示航空公司所有航班的航线。下列哪种算法最适合解决找给定两城市间最经济的飞行路线问题?
两城市之间最短路径问题用Dijkstra算法喽

2-2数据结构中Dijkstra算法用来解决哪个问题?
重复做题,最为致命。

2-3若要求在找到从S到其他顶点最短路的同时,还给出不同的最短路的条数,我们可以将Dijkstra算法略作修改,增加一个count数组:count v记录S到顶点V的最短路径有多少条。则count v应该被初始化为:
count s=1;对于其他顶点V则令count v=0,很简单嘛,自己和自己的最短路径就不用再考虑了。

2-4使用迪杰斯特拉(Dijkstra)算法求下图中从顶点1到其他各顶点的最短路径,依次得到的各最短路径的目标顶点是

最好是拿张纸画一画,挺简单。从1点开始有两条路,更新到v2和v5的距离,然后到v5的距离4小于到v2的距离5,所以在从v5开始重复操作,最后等所有的都遍历过来了就完事了,然后看看是谁先变为最短路径的,列出来即可

2-5在一个有权无向图中,如果顶点b到顶点a的最短路径长度是10,顶点c与顶点b之间存在一条长度为3的边。那么下列说法中有几句是正确的?

  • c与a的最短路径长度就是13
  • c与a的最短路径长度就是7
  • c与a的最短路径长度不超过13
  • c与a的最短路径不小于7

这题和第一个简直是一个模子刻出来的,还是列个不等式先,设a-c为x,那么x+3>=10(为什么前面说过一次了),得到x大于等于7,这是一种情况,那x最大是几呢?因为a-b的最短定了,b-c定了,所以最大就是10 + 3 = 13了,所以这里有两句话正确
2-6给定有权无向图的邻接矩阵如下,其最小生成树的总权重是:

呃,千万别还原图,直接画一下最小生成树就好了,什么,不会?Prime算法和Kruskal算法了解一下,这里就选简单的Prime算法说吧
首先我们根据邻接矩阵的值取最短的边放入我们的最小生成树,每次都取最小的边,如果和之前的构成回路了就舍弃掉,这样最后连通起来,就得到了最小生成树啦

2-9给定有权无向图如下。关于其最小生成树,下列哪句是对的?

  • 最小生成树不唯一,其总权重为23
  • 最小生成树唯一,其总权重为20
  • 边(B, F)一定在树中,树的总权重为23
  • 边(H, G)一定在树中,树的总权重为20

会Prime就完事了,怎么判断是不是唯一呢?这个还挺麻烦的,简单说一下吧,当我们在利用Prime遍历边的时候,一旦遇见权值相同而且还不能用到你现在图里的就给你选的那个边做个标记(注意是你用的那个,不是重复的那些),而最后求的的MST如果没有这样的边就说明了生成树唯一,如果有标记了的边,那么就把这些边去了再看看能不能凑出一个MST来。
这题判断是否唯一很简单,因为最后一步9的时候就有好几条线可以用,所以一定不唯一

2-13下图为一个AOV网,其可能的拓扑有序序列为

拓扑有序排列怎么玩呢?很简单,就是不停的删除入度为0的结点和其相关的边就好了。比如在这个题目里,我们先删除的应该是A,然后接着看,删除后B、D的入度变为了0,选择其中一个删除,重复直至所有的顶点都被我们取出来即可。

2-14若将n个顶点e条弧的有向图采用邻接表存储,则拓扑排序算法的时间复杂度是
n+e,记住吧

2-14若将n个顶点e条弧的有向图采用邻接表存储,则拓扑排序算法的时间复杂度是:

分享一个技巧,首先一开始只有A没有入度,所以开头一定是A,其次,B没有出度,所以B一定是最后一个,也就是A。。。B,我们删除A、B循环这个思想就完事了。
这里删除之后发现有个单独的e和另外一个图,那么e随时都可以插入所以就是3种位置,删除e,剩下的bc只有一种情况。
随意就是3种了。