Лекция №13. Графы: сильно связные компоненты и остовные деревья. Предмет "Структуры и алгоритмы обработки данных"

  • Published on
    13-Dec-2014

  • View
    3.148

  • Download
    7

Embed Size (px)

DESCRIPTION

 

Transcript

<ul><li> 1. . .. : : , . , www.grebenshikov.ru </li></ul> <p> 2. , . , - u, v V v u .1 3. G G, - , .2 4. DFS 3 5. FindStrongComp(G) 1 DF S(G) f [u] u 2 R Reverse(G) G 3 SortByF (R) R f [u] 4 DF S(R): DFS- R . 4 6. 5 7. : F indStrongComp(G) G. 6 8. : - .: (, ).: ( , ). : , E = V 2, .: .7 9. 8 10. - G1 = (V 1, E1, w1) G = (V, E, w), E1 E, V 1 = V, w1 = w. - - . w(G) =w(u, w). (u,w)E 9 11. 10 12. , . GenericMST(G, w) 1 A0 2 while A 3do A (u, v) 4 A A {(u, v)} 5 return A 11 13. (S, V S) G = (V, E) .12 14. (u, v) E (S, V S), S, V S. A , A ., , , - , - . 13 15. G = (V, E) - - w, E. A - E, - G, (S, V S) - G, , (u, v) - , (S, V S). (u, v) A. .14 16. 15 17. - Create Set(u) - u.F ind Set(u) - , - u.U nion(u, v) - , - u v. - . 16 18. 17 19. E V , . - (V V ) = (V logV ) = (ElogE) - (ElogE). E . - (V ) = (logV ) = (logE)T (G) = (ElogE) 18 20. : 19 21. 20 22. : 21 23. : T (G) = V + V logV + (logV + deg(u)logV ) = V + V logV + (V +uV 2E)logV = (ElogV )22 24. (Baruvka)23 25. David M. Mount, The Lecture notes: Design and Analysisof Computer Algorithms. [ ] / Dept. ofComputer Science, University of Maryland, 2004. - : http://www.cs.umd.edu/ mount/451/Lects/451lects.pdf. - .39-49 ., ., ., . -: , 2- . - . : - , 2007. .644-662. 24 </p>

Recommended

View more >