图算法1-bfs dfs 二部图 DAG 拓扑 并查集

没有详细算法,全是看课件笔记。

bfs O(|V|+|E|)

二部图(bipartite)
bipartite graph <=> 不存在odd cycle

强连通
s可以到达t,t也可以到达s。

任意节点s,bfs G,可以到达任意节点t
任意节点s,bfs Greverse,可以到达任意节点t
则为强连通图。

强连通分量,强连通的最大子集
tarjian O(|V|+|E|)时间内可以找到所有的强连通分量

DAG(Directed Acyclic Graph)
有向无环图 <=> 拥有拓扑排序

拓扑排序 O(|V|+|E|)

并查集
蝴蝶分类问题 带偏移量的并查集
http://blog.csdn.net/mmc2015/article/details/50153739

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容