扩展矩阵leetcode
扩展矩阵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])