扩展矩阵leetcode 慕课网《玩转算法系列--图论精讲》笔记 明确变量的语义!!! 忘记的概念 图的基本表示 联通分量(2-2 8:13) 树是一种无环图(2-2 10:26) 联通的无环图是树(2-2 11:27) 联通图的生成树包含所有顶点(2-2 12:38) 通过删边可以使原本的联通图不在联通(2-2 14:40) 只有联通图才有生成树(2-2 15:20) 邻接表空间复杂度表示 O(V+E),不能用 O(E),当 E=0 的时候就不对了(2-7 05:11) 邻接表查询两点是否相邻优化:使用 HashSet(哈希表) 或者 TreeSet(红黑树)(2-7 13:35) 由于 Golang 中没有内置的 TreeSet 红黑树,这里就使用 map (哈希表)了 :/ 可以使用深度优先遍历 验证图是否联通、是否有环 二分图检测 寻找图中的桥 寻找图中的割点 哈密尔顿路径 拓扑排序 深度优先遍历的应用 求联通分量的个数 (4-1) visited[0 .. V] = false; for (int v = 0; v < V; v ++) { if (!visited[v])