7-2 两个疑问

来源：7-2 图的表示

慕运维2948618

2022-04-07

1、我的C++基础不是很好，请问vector是自己在内部实现了在堆中创建数组，程序结束后自动析构吗？
2、老师说稀疏图的hasEdge会比较耗时，这是因为使用的是vector。那如果使用之前学习的二分搜索树或者使用集合是不是可以使得查询变快。
3、我现在只听到7-2，那如果想取消两个点之间连接的话，使用vector不是挺麻烦的吗？

写回答

1回答

liuyubobobo

2022-04-08

已采纳

1 是的。

2 是的。如果图需要 hasEdge 操作，可以把整个图声明为 vector<set<int>> 或者 vector<unordered_set<int>>。但其实大量的图算法并不需要这个操作：）

3 是的。同 2，可以把整个图声明为 vector<set<int>> 或者 vector<unordered_set<int>>。但其实大量的图算法并不需要删边。

继续加油！：）

liuyubobobo

慕运维2948618

这就是在所有的语言的标准库中，不会有“图”这个结构的原因。在一些算法中，平行边是 concern，在另一些算法中不是；对于一些问题，需要处理平行边，对于另一些问题，不需要；所以整体，图结构是相当灵活的，需要具体问题，具体分析。不过整体，使用 set 消耗并没有那么大，所以在我的这个专门的图论课程中：https://coding.imooc.com/class/370.html，会使用 TreeSet[] 的形式做图的邻接表的存储方式。不过你学完整个课程，就会发现，从删边和查边的角度，大部分图算法其实根本不需要这个操作；如果平行边是一个 concern，其实也完全可以在数据预处理阶段把重边去掉，保证构件图的边集没有平行边。继续加油！：）

2022-04-08

共3条回复

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

查看课程

相似问题

代码疑问

回答 1

关于shiftdown方法的疑问

回答 1

对于函数定义中的p和q参数的疑问，以及对查找和合并的实际应用场景

回答 1

老师我想问一个复杂度的问题，就是我在书上看到的。

回答 1

请问老师关于快速排序的疑问

回答 1

打开慕课网App查看更多内容