爱做不做 - 第五季 - 图遍历1
需积分: 0 156 浏览量
2022-08-03
22:31:53
上传
评论
收藏 600KB PDF 举报
1ÊÙ ã©)
5.1 öS
Problem 5.1.1 (DFS/BFS decompositions)
‰½˜‡k•ãÚ˜‡Ã•ã§©OÞ~DFSÚBFS$ŠL§§ˆ«>Ú:XÚ"
Problem 5.1.2
ž‰ÑDFSŽ{ÄuÒ£š48¤¢y"
Problem 5.1.3
3k•ãG = (V, E)þ$1DFSŽ{§¿…P¹uy (:Úlm(:žm" éuk>(u, v)Œ
±*f[v] < d[u]"÷vù^‡>´e¡=«a.>º£‰Ñ{‡`²¤
(i) Tree Edge (ii) Back Edge (iii) Forward Edge (iv) Cross Edge
Problem 5.1.4
y²½n7.1
1
"
Problem 5.1.5
y²µ˜‡k•ãcondensation´Ã‚"
Problem 5.1.6
rëÏ©|Ž{¥ügÝ`k|¢¥§´Ä?¿˜‡ÑŒ±£{ü¤O†•˜‡2Ý`k|
¢ºž`²Ï"
Problem 5.1.7
éÑëÏãÝ`k|¢äŠ!:´•:¿‡^‡§¿y²\(Ø"
Problem 5.1.8
éué•:Ž{§XJbackЩz•∞£½ö2(n + 1)¤ Ø´dicoverT ime[v]ž§Ž{´Ä„
(º`²\nd"
Problem 5.1.9
XJòé•:Ž{test^‡U•back ≥ discoverT ime[v]§@oëÏ¡Ž{´Ä„(ºXJ
(§)ºÏ¶XJØ(§‰Ñ‡~"
1
žë•Sara Baase and Allen Van Gelder. Computer Algorithms-Introduction to Design and Analysis(Ž{O†©Û)
1347•1n^
27
评论0