{"id":455154,"date":"2025-04-08T15:00:07","date_gmt":"2025-04-08T15:00:07","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=455154"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=455154","title":{"rendered":"<span>JavaScript: \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b. \u0427\u0430\u0441\u0442\u044c 10<\/span>"},"content":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-1\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/webt\/ma\/po\/lv\/mapolvqq4uunxfqoaviv3g9km9y.jpeg\" data-src=\"https:\/\/habrastorage.org\/webt\/ma\/po\/lv\/mapolvqq4uunxfqoaviv3g9km9y.jpeg\" data-blurred=\"true\"\/> <\/p>\n<p> \u041f\u0440\u0438\u0432\u0435\u0442, \u0434\u0440\u0443\u0437\u044c\u044f!<\/p>\n<p> <\/p>\n<p>\u0412 \u044d\u0442\u043e\u0439 \u0441\u0435\u0440\u0438\u0438 \u0441\u0442\u0430\u0442\u0435\u0439 \u043c\u044b \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u0435\u043c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b, \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0435 \u0432 <a href=\"https:\/\/github.com\/trekhleb\/javascript-algorithms\">\u044d\u0442\u043e\u043c \u0437\u0430\u043c\u0435\u0447\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u043c \u0440\u0435\u043f\u043e\u0437\u0438\u0442\u043e\u0440\u0438\u0438<\/a>. \u042d\u0442\u043e \u0434\u0435\u0441\u044f\u0442\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u0441\u0435\u0440\u0438\u0438.<\/p>\n<p> <\/p>\n<p>\u0421\u0435\u0433\u043e\u0434\u043d\u044f \u043c\u044b \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0438\u043c \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0434\u043b\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0441 \u0433\u0440\u0430\u0444\u0430\u043c\u0438.<\/p>\n<p> <\/p>\n<p>\u041a\u043e\u0434, \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0439 \u0432 \u044d\u0442\u043e\u0439 \u0438 \u0434\u0440\u0443\u0433\u0438\u0445 \u0441\u0442\u0430\u0442\u044c\u044f\u0445 \u0441\u0435\u0440\u0438\u0438, \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u0432 <a href=\"https:\/\/github.com\/harryheman\/algorithms-data-structures\">\u044d\u0442\u043e\u043c \u0440\u0435\u043f\u043e\u0437\u0438\u0442\u043e\u0440\u0438\u0438<\/a>.<\/p>\n<p> <\/p>\n<p>\u0418\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e? \u0422\u043e\u0433\u0434\u0430 \u043f\u0440\u043e\u0448\u0443 \u043f\u043e\u0434 \u043a\u0430\u0442.<\/p>\n<p><a name=\"habracut\"><\/a> <\/p>\n<ul>\n<li><a href=\"https:\/\/habr.com\/ru\/companies\/timeweb\/articles\/826424\/\">\u041f\u0435\u0440\u0432\u0430\u044f \u0447\u0430\u0441\u0442\u044c<\/a><\/li>\n<li><a href=\"https:\/\/habr.com\/ru\/companies\/timeweb\/articles\/828068\/\">\u0412\u0442\u043e\u0440\u0430\u044f \u0447\u0430\u0441\u0442\u044c<\/a><\/li>\n<li><a href=\"https:\/\/habr.com\/ru\/companies\/timeweb\/articles\/832402\/\">\u0422\u0440\u0435\u0442\u044c\u044f \u0447\u0430\u0441\u0442\u044c<\/a><\/li>\n<li><a href=\"https:\/\/habr.com\/ru\/companies\/timeweb\/articles\/836782\/\">\u0427\u0435\u0442\u0432\u0435\u0440\u0442\u0430\u044f \u0447\u0430\u0441\u0442\u044c<\/a><\/li>\n<li><a href=\"https:\/\/habr.com\/ru\/companies\/timeweb\/articles\/838794\/\">\u041f\u044f\u0442\u0430\u044f \u0447\u0430\u0441\u0442\u044c<\/a><\/li>\n<li><a href=\"https:\/\/habr.com\/ru\/companies\/timeweb\/articles\/845544\/\">\u0428\u0435\u0441\u0442\u0430\u044f \u0447\u0430\u0441\u0442\u044c<\/a><\/li>\n<li><a href=\"https:\/\/habr.com\/ru\/companies\/timeweb\/articles\/856046\/\">\u0421\u0435\u0434\u044c\u043c\u0430\u044f \u0447\u0430\u0441\u0442\u044c<\/a><\/li>\n<li><a href=\"https:\/\/habr.com\/ru\/companies\/timeweb\/articles\/856046\/\">\u0412\u043e\u0441\u044c\u043c\u0430\u044f \u0447\u0430\u0441\u0442\u044c<\/a><\/li>\n<li><a href=\"https:\/\/habr.com\/ru\/companies\/timeweb\/articles\/856046\/\">\u0414\u0435\u0432\u044f\u0442\u0430\u044f \u0447\u0430\u0441\u0442\u044c<\/a><\/li>\n<\/ul>\n<p> <\/p>\n<h1 id=\"-graf\">\u276f \u0413\u0440\u0430\u0444<\/h1>\n<p> <\/p>\n<h2 id=\"-algoritm-prima\">\u276f \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u041f\u0440\u0438\u043c\u0430<\/h2>\n<p> <\/p>\n<p><strong>\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435<\/strong><\/p>\n<p> <\/p>\n<ul>\n<li><a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9F%D1%80%D0%B8%D0%BC%D0%B0\">\u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u044f \u2014 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u041f\u0440\u0438\u043c\u0430<\/a><\/li>\n<li><a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%9C%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D0%BE%D1%81%D1%82%D0%BE%D0%B2%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE\">\u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u044f \u2014 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043e\u0441\u0442\u043e\u0432\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e<\/a><\/li>\n<li><a href=\"https:\/\/www.youtube.com\/watch?v=vPHUm874EoA\">YouTube<\/a><\/li>\n<\/ul>\n<p> <\/p>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u041f\u0440\u0438\u043c\u0430 (Prim&#8217;s algorithm) \u2014 \u044d\u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043e\u0441\u0442\u043e\u0432\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u0432\u0437\u0432\u0435\u0448\u0435\u043d\u043d\u043e\u0433\u043e \u0441\u0432\u044f\u0437\u043d\u043e\u0433\u043e \u043d\u0435\u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0433\u043e \u0433\u0440\u0430\u0444\u0430.<\/p>\n<p> <\/p>\n<p>\u041c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043e\u0441\u0442\u043e\u0432\u043d\u043e\u0435 (\u043f\u043e\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0435\u0435) \u0434\u0435\u0440\u0435\u0432\u043e (\u041c\u041e\u0414) \u0432 (\u043d\u0435\u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u043c) \u0441\u0432\u044f\u0437\u043d\u043e\u043c \u0432\u0437\u0432\u0435\u0448\u0435\u043d\u043d\u043e\u043c \u0433\u0440\u0430\u0444\u0435 \u2014 \u044d\u0442\u043e \u043e\u0441\u0442\u043e\u0432\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u044d\u0442\u043e\u0433\u043e \u0433\u0440\u0430\u0444\u0430, \u0438\u043c\u0435\u044e\u0449\u0435\u0435 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0439 \u0432\u0435\u0441, \u0433\u0434\u0435 \u043f\u043e\u0434 \u0432\u0435\u0441\u043e\u043c \u0434\u0435\u0440\u0435\u0432\u0430 \u043f\u043e\u043d\u0438\u043c\u0430\u0435\u0442\u0441\u044f \u0441\u0443\u043c\u043c\u0430 \u0432\u0435\u0441\u043e\u0432 \u0432\u0445\u043e\u0434\u044f\u0449\u0438\u0445 \u0432 \u043d\u0435\u0433\u043e \u0440\u0435\u0431\u0435\u0440.<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/s2\/h0\/7u\/s2h07ulwhcas7gedxhhwmn8elns.png\" data-src=\"https:\/\/habrastorage.org\/webt\/s2\/h0\/7u\/s2h07ulwhcas7gedxhhwmn8elns.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<p>\u0415\u0449\u0435 \u043e\u0434\u0438\u043d \u043f\u0440\u0438\u043c\u0435\u0440 \u0433\u0440\u0430\u0444\u0430 \u0438 \u0435\u0433\u043e \u041c\u041e\u0414. \u041a\u0430\u0436\u0434\u043e\u0435 \u0440\u0435\u0431\u0440\u043e \u043f\u043e\u043c\u0435\u0447\u0435\u043d\u043e \u0432\u0435\u0441\u043e\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0437\u0434\u0435\u0441\u044c \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u043f\u0440\u043e\u043f\u043e\u0440\u0446\u0438\u043e\u043d\u0430\u043b\u0435\u043d \u0434\u043b\u0438\u043d\u0435 \u0440\u0435\u0431\u0440\u0430:<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/uc\/2-\/d4\/uc2-d4w3_xp9oqu1mw6ibsjnapi.png\" data-src=\"https:\/\/habrastorage.org\/webt\/uc\/2-\/d4\/uc2-d4w3_xp9oqu1mw6ibsjnapi.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<p>\u041d\u0430 \u044d\u0442\u043e\u043c \u0440\u0438\u0441\u0443\u043d\u043a\u0435 \u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e \u0432 \u0433\u0440\u0430\u0444\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0431\u043e\u043b\u0435\u0435 \u043e\u0434\u043d\u043e\u0433\u043e \u041c\u041e\u0414.<\/p>\n<p> <\/p>\n<p><em>\u041f\u0440\u0438\u043d\u0446\u0438\u043f \u0440\u0430\u0431\u043e\u0442\u044b<\/em><\/p>\n<p> <\/p>\n<p>\u041d\u0430 \u0432\u0445\u043e\u0434 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043f\u043e\u0434\u0430\u0435\u0442\u0441\u044f \u0441\u0432\u044f\u0437\u043d\u044b\u0439 \u043d\u0435\u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u0433\u0440\u0430\u0444. \u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0440\u0435\u0431\u0440\u0430 \u0437\u0430\u0434\u0430\u0435\u0442\u0441\u044f \u0435\u0433\u043e \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c.<\/p>\n<p> <\/p>\n<p>\u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u0431\u0435\u0440\u0435\u0442\u0441\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u0430\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u0438 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0440\u0435\u0431\u0440\u043e, \u0438\u043d\u0446\u0438\u0434\u0435\u043d\u0442\u043d\u043e\u0435 \u0434\u0430\u043d\u043d\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u0435 \u0438 \u043e\u0431\u043b\u0430\u0434\u0430\u044e\u0449\u0435\u0435 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0439 \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c\u044e. \u041d\u0430\u0439\u0434\u0435\u043d\u043d\u043e\u0435 \u0440\u0435\u0431\u0440\u043e \u0438 \u0441\u043e\u0435\u0434\u0438\u043d\u044f\u0435\u043c\u044b\u0435 \u0438\u043c \u0434\u0432\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u043e\u0431\u0440\u0430\u0437\u0443\u044e\u0442 \u0434\u0435\u0440\u0435\u0432\u043e. \u0417\u0430\u0442\u0435\u043c, \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u0440\u0435\u0431\u0440\u0430 \u0433\u0440\u0430\u0444\u0430, \u043e\u0434\u0438\u043d \u043a\u043e\u043d\u0435\u0446 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u2014 \u0443\u0436\u0435 \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0430\u0449\u0430\u044f \u0434\u0435\u0440\u0435\u0432\u0443 \u0432\u0435\u0440\u0448\u0438\u043d\u0430, \u0430 \u0434\u0440\u0443\u0433\u043e\u0439 \u2014 \u043d\u0435\u0442; \u0438\u0437 \u044d\u0442\u0438\u0445 \u0440\u0435\u0431\u0435\u0440 \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u0440\u0435\u0431\u0440\u043e \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0439 \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u0438. \u0412\u044b\u0431\u0438\u0440\u0430\u0435\u043c\u043e\u0435 \u043d\u0430 \u043a\u0430\u0436\u0434\u043e\u043c \u0448\u0430\u0433\u0435 \u0440\u0435\u0431\u0440\u043e \u043f\u0440\u0438\u0441\u043e\u0435\u0434\u0438\u043d\u044f\u0435\u0442\u0441\u044f \u043a \u0434\u0435\u0440\u0435\u0432\u0443. \u0420\u043e\u0441\u0442 \u0434\u0435\u0440\u0435\u0432\u0430 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0434\u043e \u0442\u0435\u0445 \u043f\u043e\u0440, \u043f\u043e\u043a\u0430 \u043d\u0435 \u0431\u0443\u0434\u0443\u0442 \u0438\u0441\u0447\u0435\u0440\u043f\u0430\u043d\u044b \u0432\u0441\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0433\u0440\u0430\u0444\u0430.<\/p>\n<p> <\/p>\n<p>\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u043e\u043c \u0440\u0430\u0431\u043e\u0442\u044b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u041c\u041e\u0414.<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/58\/vh\/-p\/58vh-pe2w5w_zxf50_1umbcq6f8.png\" data-src=\"https:\/\/habrastorage.org\/webt\/58\/vh\/-p\/58vh-pe2w5w_zxf50_1umbcq6f8.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<p>\u0414\u0435\u043c\u043e\u043d\u0441\u0442\u0440\u0430\u0446\u0438\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u041f\u0440\u0438\u043c\u0430 \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%95%D0%B2%D0%BA%D0%BB%D0%B8%D0%B4%D0%BE%D0%B2%D0%B0_%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D0%BA%D0%B0#:~:text=%D0%95%D0%B2%D0%BA%D0%BB%D0%B8%D0%B4%D0%BE%D0%B2%D0%B0%20%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D0%BA%D0%B0%20(%D0%B5%D0%B2%D0%BA%D0%BB%D0%B8%D0%B4%D0%BE%D0%B2%D0%BE%20%D1%80%D0%B0%D1%81%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B5)%20%E2%80%94,%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%80%D0%B0%D0%BD%D1%81%D1%82%D0%B2%D0%B0%2C%20%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D1%8F%D0%B5%D0%BC%D0%BE%D0%B5%20%D0%BF%D0%BE%20%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B5%20%D0%9F%D0%B8%D1%84%D0%B0%D0%B3%D0%BE%D1%80%D0%B0.\">\u0435\u0432\u043a\u043b\u0438\u0434\u043e\u0432\u0430 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f<\/a>:<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/8n\/lc\/cw\/8nlccwfpieqf-f5deba2tbbph_k.gif\" data-src=\"https:\/\/habrastorage.org\/webt\/8n\/lc\/cw\/8nlccwfpieqf-f5deba2tbbph_k.gif\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<p><em>\u041f\u0441\u0435\u0432\u0434\u043e\u043a\u043e\u0434<\/em><\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/ju\/il\/bb\/juilbbh4o8tmhujsinz2zjimoos.png\" data-src=\"https:\/\/habrastorage.org\/webt\/ju\/il\/bb\/juilbbh4o8tmhujsinz2zjimoos.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<p><em>\u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c<\/em><\/p>\n<p> <\/p>\n<p>\u0410\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u043a\u0430 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 \u0441\u043f\u043e\u0441\u043e\u0431\u0430 \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0433\u0440\u0430\u0444\u0430 \u0438 \u0441\u043f\u043e\u0441\u043e\u0431\u0430 \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0432\u0435\u0440\u0448\u0438\u043d, \u043d\u0435 \u0432\u0445\u043e\u0434\u044f\u0449\u0438\u0445 \u0432 \u0434\u0435\u0440\u0435\u0432\u043e. \u0415\u0441\u043b\u0438 \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u043d\u0430\u044f \u043e\u0447\u0435\u0440\u0435\u0434\u044c <code>Q<\/code> \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u0430 \u043a\u0430\u043a \u043e\u0431\u044b\u0447\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 <code>d<\/code>, \u0442\u043e <code>Extract.Min(Q)<\/code> \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u0437\u0430 <code>O(n)<\/code>, \u0430 \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 <code>d|u| &lt;- w(v, u)<\/code> \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 <code>O(1)<\/code>. \u0415\u0441\u043b\u0438 <code>Q<\/code> \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0441\u043e\u0431\u043e\u0439 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%B0%D1%8F_%D0%BA%D1%83%D1%87%D0%B0\">\u0431\u0438\u043d\u0430\u0440\u043d\u0443\u044e \u043f\u0438\u0440\u0430\u043c\u0438\u0434\u0443<\/a>, \u0442\u043e \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c <code>Extract.Min(Q)<\/code> \u0441\u043d\u0438\u0436\u0430\u0435\u0442\u0441\u044f \u0434\u043e <code>O(log n)<\/code>, \u0430 \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c <code>d|u| &lt;- w(v, u)<\/code> \u0432\u043e\u0437\u0440\u0430\u0441\u0442\u0430\u0435\u0442 \u0434\u043e <code>O(log n)<\/code>. \u041f\u0440\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0438 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8%D0%B5%D0%B2%D0%B0_%D0%BA%D1%83%D1%87%D0%B0\">\u0444\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438\u0435\u0432\u044b\u0445 \u043f\u0438\u0440\u0430\u043c\u0438\u0434<\/a> \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f <code>Extract.Min(Q)<\/code> \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u0437\u0430 <code>O(log n)<\/code>, \u0430 <code>d|u| &lt;- w(v, u)<\/code> \u2014 \u0437\u0430 <code>O(1)<\/code>.<\/p>\n<p> <\/p>\n<p><strong>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/strong><\/p>\n<p> <\/p>\n<p>\u0414\u043b\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f <a href=\"https:\/\/habr.com\/ru\/companies\/timeweb\/articles\/828068\/\">\u043e\u0447\u0435\u0440\u0435\u0434\u044c \u0441 \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u043e\u043c<\/a>:<\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ algorithms\/graphs\/prim.js import Graph from '..\/..\/data-structures\/graph\/index' import PriorityQueue from '..\/..\/data-structures\/priority-queue'  \/\/ \u0424\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u0433\u0440\u0430\u0444 export default function prim(graph) {   \/\/ \u041f\u0440\u0438 \u043f\u0435\u0440\u0435\u0434\u0430\u0447\u0435 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u0433\u0440\u0430\u0444\u0430 \u0434\u043e\u043b\u0436\u043d\u043e \u0432\u044b\u0431\u0440\u0430\u0441\u044b\u0432\u0430\u0442\u044c\u0441\u044f \u0438\u0441\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435   if (graph.isDirected) {     throw new Error('\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u041f\u0440\u0438\u043c\u0430 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u0441 \u043d\u0435\u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u043c\u0438 \u0433\u0440\u0430\u0444\u0430\u043c\u0438')   }    \/\/ \u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u0443\u0435\u043c \u043d\u043e\u0432\u044b\u0439 \u0433\u0440\u0430\u0444, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u0443\u0434\u0435\u0442 \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442\u044c   \/\/ \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043e\u0441\u0442\u043e\u0432\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e (\u041c\u041e\u0414) \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0433\u0440\u0430\u0444\u0430   const minimumSpanningTree = new Graph()    \/\/ \u042d\u0442\u0430 \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u0441 \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u043e\u043c \u0431\u0443\u0434\u0435\u0442 \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442\u044c \u0432\u0441\u0435 \u0440\u0435\u0431\u0440\u0430,   \/\/ \u043d\u0430\u0447\u0438\u043d\u0430\u044e\u0449\u0438\u0435\u0441\u044f \u043e\u0442 \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432 \u0438 \u0440\u0430\u043d\u0436\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u043f\u043e \u0432\u0435\u0441\u0443 -   \/\/ \u043d\u0430 \u043a\u0430\u0436\u0434\u043e\u043c \u0448\u0430\u0433\u0435 \u043c\u044b \u0432\u0441\u0435\u0433\u0434\u0430 \u0431\u0443\u0434\u0435\u043c \u043f\u043e\u043b\u0443\u0447\u0430\u0442\u044c \u0440\u0435\u0431\u0440\u043e \u0441 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u0432\u0435\u0441\u043e\u043c   const edgesQueue = new PriorityQueue()    \/\/ \u041d\u0430\u0431\u043e\u0440 \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432   const visited = {}    \/\/ \u041d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u0439 \u0443\u0437\u0435\u043b \u0434\u043b\u044f \u043e\u0431\u0445\u043e\u0434\u0430 \u0433\u0440\u0430\u0444\u0430   const startNode = graph.getAllNodes()[0]    \/\/ \u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u0439 \u0443\u0437\u0435\u043b \u0432 \u043d\u0430\u0431\u043e\u0440 \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432   visited[startNode.getKey()] = startNode    \/\/ \u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0432\u0441\u0435 \u0440\u0435\u0431\u0440\u0430 \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0443\u0437\u043b\u0430 \u0432 \u043e\u0447\u0435\u0440\u0435\u0434\u044c   startNode.getEdges().forEach((graphEdge) =&gt; {     edgesQueue.add(graphEdge, graphEdge.weight)   })    \/\/ \u041f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0435\u043c \u0440\u0435\u0431\u0440\u0430, \u043d\u0430\u0445\u043e\u0434\u044f\u0449\u0438\u0435\u0441\u044f \u0432 \u043e\u0447\u0435\u0440\u0435\u0434\u0438   while (!edgesQueue.isEmpty()) {     \/\/ \u0418\u0437\u0432\u043b\u0435\u043a\u0430\u0435\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0435 \u0440\u0435\u0431\u0440\u043e \u0441 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u0432\u0435\u0441\u043e\u043c     const currentMinEdge = edgesQueue.poll()      \/\/ \u041d\u0430\u0445\u043e\u0434\u0438\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u043d\u0435\u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0439 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0443\u0437\u0435\u043b \u0434\u043b\u044f \u043e\u0431\u0445\u043e\u0434\u0430     let nextMinNode = null     if (!visited[currentMinEdge.from.getKey()]) {       nextMinNode = currentMinEdge.from     } else if (!visited[currentMinEdge.to.getKey()]) {       nextMinNode = currentMinEdge.to     }      \/\/ \u041f\u0440\u043e\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u044e, \u0435\u0441\u043b\u0438 \u0432\u0441\u0435 \u0443\u0437\u043b\u044b \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u0440\u0435\u0431\u0440\u0430 \u0443\u0436\u0435 \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u044b     if (nextMinNode) {       \/\/ \u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0442\u0435\u043a\u0443\u0449\u0435\u0435 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0435\u0431\u0440\u043e \u0432 \u041c\u041e\u0414       minimumSpanningTree.addEdge(currentMinEdge)        \/\/ \u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0443\u0437\u0435\u043b \u0432 \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0435       visited[nextMinNode.getKey()] = nextMinNode        \/\/ \u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0440\u0435\u0431\u0440\u0430 \u0443\u0437\u043b\u0430 \u0432 \u043e\u0447\u0435\u0440\u0435\u0434\u044c       nextMinNode.getEdges().forEach((graphEdge) =&gt; {         \/\/ \u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0442\u043e\u043b\u044c\u043a\u043e \u0442\u0435 \u0440\u0435\u0431\u0440\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0432\u0435\u0434\u0443\u0442 \u043a \u043d\u0435\u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u043c \u0443\u0437\u043b\u0430\u043c         if (           !visited[graphEdge.from.getKey()] ||           !visited[graphEdge.to.getKey()]         ) {           edgesQueue.add(graphEdge, graphEdge.weight)         }       })     }   }    return minimumSpanningTree }<\/code><\/pre>\n<p> <\/p>\n<div class=\"spoiler\" role=\"button\" tabindex=\"0\">                         <b class=\"spoiler_title\">\u0422\u0435\u0441\u0442\u044b:<\/b>                         <\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"javascript\">\/\/ algorithms\/graphs\/__tests__\/prim.test.js import GraphNode from '..\/..\/..\/data-structures\/graph\/node' import GraphEdge from '..\/..\/..\/data-structures\/graph\/edge' import Graph from '..\/..\/..\/data-structures\/graph\/index' import prim from '..\/prim'  describe('prim', () =&gt; {   it('\u043f\u0440\u0438 \u043f\u0435\u0440\u0435\u0434\u0430\u0447\u0435 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u0433\u0440\u0430\u0444\u0430 \u0434\u043e\u043b\u0436\u043d\u043e \u0432\u044b\u0431\u0440\u0430\u0441\u044b\u0432\u0430\u0442\u044c\u0441\u044f \u0438\u0441\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435', () =&gt; {     function applyPrimToDirectedGraph() {       const graph = new Graph(true)        prim(graph)     }      expect(applyPrimToDirectedGraph).toThrowError()   })    it('\u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0439\u0442\u0438 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043e\u0441\u0442\u043e\u0432\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e', () =&gt; {     const nodeA = new GraphNode('A')     const nodeB = new GraphNode('B')     const nodeC = new GraphNode('C')     const nodeD = new GraphNode('D')     const nodeE = new GraphNode('E')     const nodeF = new GraphNode('F')     const nodeG = new GraphNode('G')      const edgeAB = new GraphEdge(nodeA, nodeB, 2)     const edgeAD = new GraphEdge(nodeA, nodeD, 3)     const edgeAC = new GraphEdge(nodeA, nodeC, 3)     const edgeBC = new GraphEdge(nodeB, nodeC, 4)     const edgeBE = new GraphEdge(nodeB, nodeE, 3)     const edgeDF = new GraphEdge(nodeD, nodeF, 7)     const edgeEC = new GraphEdge(nodeE, nodeC, 1)     const edgeEF = new GraphEdge(nodeE, nodeF, 8)     const edgeFG = new GraphEdge(nodeF, nodeG, 9)     const edgeFC = new GraphEdge(nodeF, nodeC, 6)      const graph = new Graph()      graph       .addEdge(edgeAB)       .addEdge(edgeAD)       .addEdge(edgeAC)       .addEdge(edgeBC)       .addEdge(edgeBE)       .addEdge(edgeDF)       .addEdge(edgeEC)       .addEdge(edgeEF)       .addEdge(edgeFC)       .addEdge(edgeFG)      expect(graph.getWeight()).toEqual(46)      const minimumSpanningTree = prim(graph)      expect(minimumSpanningTree.getWeight()).toBe(24)     expect(minimumSpanningTree.getAllNodes().length).toBe(       graph.getAllNodes().length,     )     expect(minimumSpanningTree.getAllEdges().length).toBe(       graph.getAllNodes().length - 1,     )     expect(minimumSpanningTree.toString()).toBe('A,B,C,E,D,F,G')   })    it('\u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0439\u0442\u0438 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043e\u0441\u0442\u043e\u0432\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u0434\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u043e\u0433\u043e \u0433\u0440\u0430\u0444\u0430', () =&gt; {     const nodeA = new GraphNode('A')     const nodeB = new GraphNode('B')     const nodeC = new GraphNode('C')     const nodeD = new GraphNode('D')      const edgeAB = new GraphEdge(nodeA, nodeB, 1)     const edgeAD = new GraphEdge(nodeA, nodeD, 3)     const edgeBC = new GraphEdge(nodeB, nodeC, 1)     const edgeBD = new GraphEdge(nodeB, nodeD, 3)     const edgeCD = new GraphEdge(nodeC, nodeD, 1)      const graph = new Graph()      graph       .addEdge(edgeAB)       .addEdge(edgeAD)       .addEdge(edgeBC)       .addEdge(edgeBD)       .addEdge(edgeCD)      expect(graph.getWeight()).toEqual(9)      const minimumSpanningTree = prim(graph)      expect(minimumSpanningTree.getWeight()).toBe(3)     expect(minimumSpanningTree.getAllNodes().length).toBe(       graph.getAllNodes().length,     )     expect(minimumSpanningTree.getAllEdges().length).toBe(       graph.getAllNodes().length - 1,     )     expect(minimumSpanningTree.toString()).toBe('A,B,C,D')   }) })<\/code><\/pre>\n<\/div><\/div>\n<p> <\/p>\n<p>\u0417\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u0442\u0435\u0441\u0442\u044b:<\/p>\n<p> <\/p>\n<pre><code class=\"bash\">npm run test .\/algorithms\/graphs\/__tests__\/prim<\/code><\/pre>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/1j\/dd\/hh\/1jddhhgmq4py7u-tknso4t4olm8.png\" data-src=\"https:\/\/habrastorage.org\/webt\/1j\/dd\/hh\/1jddhhgmq4py7u-tknso4t4olm8.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<h2 id=\"-topologicheskaya-sortirovka\">\u276f \u0422\u043e\u043f\u043e\u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430<\/h2>\n<p> <\/p>\n<p><strong>\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435<\/strong><\/p>\n<p> <\/p>\n<ul>\n<li><a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%A2%D0%BE%D0%BF%D0%BE%D0%BB%D0%BE%D0%B3%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0\">\u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u044f<\/a><\/li>\n<li><a href=\"https:\/\/www.youtube.com\/watch?v=o0P8oNXoA_w\">YouTube<\/a><\/li>\n<\/ul>\n<p> <\/p>\n<p>\u0422\u043e\u043f\u043e\u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0438\u043b\u0438 \u0442\u043e\u043f\u043e\u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u0438\u0435 (topological sort) \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u0433\u0440\u0430\u0444\u0430 \u2014 \u044d\u0442\u043e \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u0438\u0435 \u0435\u0433\u043e \u0432\u0435\u0440\u0448\u0438\u043d, \u043f\u0440\u0438 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u0440\u0435\u0431\u0440\u0430 <code>uv<\/code> \u043e\u0442 \u0432\u0435\u0440\u0448\u0438\u043d\u044b <code>u<\/code> \u0434\u043e \u0432\u0435\u0440\u0448\u0438\u043d\u044b <code>v<\/code>, <code>u<\/code> \u043f\u0440\u0435\u0434\u0448\u0435\u0441\u0442\u0432\u0443\u0435\u0442 <code>v<\/code> \u0432 \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u0438\u0438.<\/p>\n<p> <\/p>\n<p>\u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0433\u0440\u0430\u0444\u0430 \u043c\u043e\u0433\u0443\u0442 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u044c, \u0430 \u0440\u0435\u0431\u0440\u0430 \u043c\u043e\u0433\u0443\u0442 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0442\u044c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f, \u0441\u043e\u0433\u043b\u0430\u0441\u043d\u043e \u043a\u043e\u0442\u043e\u0440\u044b\u043c \u043e\u0434\u043d\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 \u0434\u043e\u043b\u0436\u043d\u0430 \u0431\u044b\u0442\u044c \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0430 \u043f\u0435\u0440\u0435\u0434 \u0434\u0440\u0443\u0433\u043e\u0439; \u0432 \u044d\u0442\u043e\u043c \u043f\u0440\u0438\u043b\u043e\u0436\u0435\u043d\u0438\u0438 \u0442\u043e\u043f\u043e\u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u0438\u0435 \u2014 \u044d\u0442\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u0430\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0437\u0430\u0434\u0430\u0447.<\/p>\n<p> <\/p>\n<p>\u0422\u043e\u043f\u043e\u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u0438\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u0442\u043e\u0433\u0434\u0430 \u0438 \u0442\u043e\u043b\u044c\u043a\u043e \u0442\u043e\u0433\u0434\u0430, \u043a\u043e\u0433\u0434\u0430 \u0433\u0440\u0430\u0444 \u043d\u0435 \u0438\u043c\u0435\u0435\u0442 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0445 \u0446\u0438\u043a\u043b\u043e\u0432, \u0442\u043e \u0435\u0441\u0442\u044c \u0435\u0441\u043b\u0438 \u043e\u043d \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f <a href=\"https:\/\/en.wikipedia.org\/wiki\/Directed_acyclic_graph\">\u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u043c \u0430\u0446\u0438\u043a\u043b\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u0433\u0440\u0430\u0444\u043e\u043c<\/a> (directed acyclic graph, DAG). \u041b\u044e\u0431\u043e\u0439 DAG \u0438\u043c\u0435\u0435\u0442 \u043f\u043e \u043a\u0440\u0430\u0439\u043d\u0435\u0439 \u043c\u0435\u0440\u0435 \u043e\u0434\u043d\u043e \u0442\u043e\u043f\u043e\u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u0438\u0435, \u0438 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0433\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0434\u043b\u044f \u0435\u0433\u043e \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f.<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/e6\/yd\/gb\/e6ydgbndzlnsg8xeznuym1weitc.png\" data-src=\"https:\/\/habrastorage.org\/webt\/e6\/yd\/gb\/e6ydgbndzlnsg8xeznuym1weitc.png\"\/> <\/p>\n<p><em>\u0422\u043e\u043f\u043e\u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u0430\u0446\u0438\u043a\u043b\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0433\u0440\u0430\u0444\u0430: \u043a\u0430\u0436\u0434\u043e\u0435 \u0440\u0435\u0431\u0440\u043e \u0438\u0434\u0435\u0442 \u043e\u0442 \u0431\u043e\u043b\u0435\u0435 \u0440\u0430\u043d\u043d\u0435\u0433\u043e (\u043f\u043e \u043f\u043e\u0440\u044f\u0434\u043a\u0443) (\u0441\u0432\u0435\u0440\u0445\u0443 \u0441\u043b\u0435\u0432\u0430) \u043a \u0431\u043e\u043b\u0435\u0435 \u043f\u043e\u0437\u0434\u043d\u0435\u043c\u0443 (\u0441\u043d\u0438\u0437\u0443 \u0441\u043f\u0440\u0430\u0432\u0430) \u0443\u0437\u043b\u0430\u043c. \u041d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0439 \u0433\u0440\u0430\u0444 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0430\u0446\u0438\u043a\u043b\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u0442\u043e\u0433\u0434\u0430 \u0438 \u0442\u043e\u043b\u044c\u043a\u043e \u0442\u043e\u0433\u0434\u0430, \u043a\u043e\u0433\u0434\u0430 \u043e\u043d \u0438\u043c\u0435\u0435\u0442 \u0442\u043e\u043f\u043e\u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u0438\u0435<\/em><\/p>\n<p> <\/p>\n<p><em>\u041f\u0440\u0438\u043c\u0435\u0440<\/em><\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/in\/bz\/fc\/inbzfcxiqyzu51xgllmrlpscrkw.png\" data-src=\"https:\/\/habrastorage.org\/webt\/in\/bz\/fc\/inbzfcxiqyzu51xgllmrlpscrkw.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<p>\u041f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u043d\u044b\u0439 \u0433\u0440\u0430\u0444 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u043c\u0438 \u0441\u043f\u043e\u0441\u043e\u0431\u0430\u043c\u0438, \u0432 \u0442\u043e\u043c \u0447\u0438\u0441\u043b\u0435:<\/p>\n<p> <\/p>\n<ul>\n<li><code>5, 7, 3, 11, 8, 2, 9, 10<\/code> \u2014 \u0432\u0438\u0437\u0443\u0430\u043b\u044c\u043d\u043e \u0441\u043b\u0435\u0432\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043e, \u0441\u0432\u0435\u0440\u0445\u0443 \u0432\u043d\u0438\u0437<\/li>\n<li><code>3, 5, 7, 8, 11, 2, 9, 10<\/code> \u2014 \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u0434\u043e\u0441\u0442\u0443\u043f\u043d\u0430\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u0441 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0438\u043c \u043d\u043e\u043c\u0435\u0440\u043e\u043c<\/li>\n<li><code>5, 7, 3, 8, 11, 10, 9, 2<\/code> \u2014 \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u0434\u043e\u0441\u0442\u0443\u043f\u043d\u0430\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u0441 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0438\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e\u043c \u0440\u0435\u0431\u0435\u0440<\/li>\n<li><code>7, 5, 11, 3, 10, 8, 9, 2<\/code> \u2014 \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u0434\u043e\u0441\u0442\u0443\u043f\u043d\u0430\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u0441 \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0438\u043c \u043d\u043e\u043c\u0435\u0440\u043e\u043c<\/li>\n<li><code>5, 7, 11, 2, 3, 8, 9, 10<\/code> \u2014 \u0441\u0432\u0435\u0440\u0445\u0443 \u0432\u043d\u0438\u0437, \u0441\u043b\u0435\u0432\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043e<\/li>\n<li><code>3, 7, 8, 5, 11, 10, 2, 9<\/code> \u2014 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u044b\u0439 \u043f\u043e\u0440\u044f\u0434\u043e\u043a<\/li>\n<\/ul>\n<p> <\/p>\n<p><em>\u041f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0435<\/em><\/p>\n<p> <\/p>\n<p>\u0422\u043e\u043f\u043e\u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0447\u0430\u0441\u0442\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0434\u043b\u044f \u043f\u043b\u0430\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0437\u0430\u0434\u0430\u0447 \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u0438\u0445 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0435\u0439. \u0417\u0430\u0434\u0430\u0447\u0438 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u044b \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u043c\u0438, \u0438 \u0435\u0441\u0442\u044c \u0440\u0435\u0431\u0440\u043e \u043c\u0435\u0436\u0434\u0443 <code>x<\/code> \u0438 <code>y<\/code>, \u0435\u0441\u043b\u0438 \u0437\u0430\u0434\u0430\u0447\u0430 <code>x<\/code> \u0434\u043e\u043b\u0436\u043d\u0430 \u0431\u044b\u0442\u044c \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0430 \u043f\u0435\u0440\u0435\u0434 <code>y<\/code> (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043f\u0440\u0438 \u0441\u0442\u0438\u0440\u043a\u0435 \u043e\u0434\u0435\u0436\u0434\u044b, \u0441\u0442\u0438\u0440\u0430\u043b\u044c\u043d\u0430\u044f \u043c\u0430\u0448\u0438\u043d\u0430 \u0434\u043e\u043b\u0436\u043d\u0430 \u0437\u0430\u043a\u043e\u043d\u0447\u0438\u0442\u044c \u0441\u0432\u043e\u044e \u0440\u0430\u0431\u043e\u0442\u0443 \u043f\u0435\u0440\u0435\u0434 \u043f\u043e\u043c\u0435\u0449\u0435\u043d\u0438\u0435\u043c \u043e\u0434\u0435\u0436\u0434\u044b \u0432 \u0441\u0443\u0448\u0438\u043b\u043a\u0443). \u0417\u0434\u0435\u0441\u044c \u0442\u043e\u043f\u043e\u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442 \u043f\u043e\u0440\u044f\u0434\u043e\u043a \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447.<\/p>\n<p> <\/p>\n<p>\u0414\u0440\u0443\u0433\u0438\u043c \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0435\u043c \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0440\u0430\u0437\u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0435\u0439. \u041a\u0430\u0436\u0434\u0430\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u2014 \u044d\u0442\u043e \u043f\u0430\u043a\u0435\u0442, \u0430 \u043a\u0430\u0436\u0434\u043e\u0435 \u0440\u0435\u0431\u0440\u043e \u2014 \u044d\u0442\u043e \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u044c \u044d\u0442\u043e\u0433\u043e \u043c\u043e\u0434\u0443\u043b\u044f \u043e\u0442 \u0434\u0440\u0443\u0433\u0438\u0445 \u043c\u043e\u0434\u0443\u043b\u0435\u0439. \u0417\u0434\u0435\u0441\u044c \u0442\u043e\u043f\u043e\u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442 \u0442\u0430\u043a\u043e\u0439 \u043f\u043e\u0440\u044f\u0434\u043e\u043a \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0438 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0435\u0439, \u0447\u0442\u043e\u0431\u044b \u043f\u0435\u0440\u0435\u0434 \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u043e\u0439 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u0440\u0430\u0437\u0440\u0435\u0448\u0430\u043b\u0438\u0441\u044c \u0432\u0441\u0435 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0439 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438.<\/p>\n<p> <\/p>\n<p><strong>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/strong><\/p>\n<p> <\/p>\n<p>\u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0434\u043b\u044f \u0442\u043e\u043f\u043e\u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u0438\u044f. \u0412 \u043d\u0430\u0448\u0435\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0431\u0443\u0434\u0435\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0442\u0430\u043a\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043a\u0430\u043a <a href=\"https:\/\/habr.com\/ru\/companies\/timeweb\/articles\/896800\/\">\u043f\u043e\u0438\u0441\u043a \u0432 \u0433\u043b\u0443\u0431\u0438\u043d\u0443<\/a>, \u0438 \u0442\u0430\u043a\u0430\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u0430\u043a <a href=\"https:\/\/habr.com\/ru\/companies\/timeweb\/articles\/826424\/\">\u0441\u0442\u0435\u043a<\/a>:<\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ algorithms\/graphs\/topological-sort.js import Stack from '..\/..\/data-structures\/stack' import depthFirstSearch from '.\/depth-first-search'  \/\/ \u0424\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u0433\u0440\u0430\u0444 export default function topologicalSort(graph) {   \/\/ \u0423\u0437\u043b\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u044b \u0445\u043e\u0442\u0438\u043c \u043f\u043e\u0441\u0435\u0442\u0438\u0442\u044c   const unvisited = graph.getAllNodes().reduce((a, c) =&gt; {     a[c.getKey()] = c     return a   }, {})    \/\/ \u041f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0435 \u0443\u0437\u043b\u044b   const visited = {}    \/\/ \u0421\u0442\u0435\u043a \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432   const stack = new Stack()    \/\/ \u041e\u0431\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a\u0438 \u0434\u043b\u044f DFS   const callbacks = {     \/\/ \u041e\u0431\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a \u0432\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u0432 \u0443\u0437\u0435\u043b     enterNode: ({ currentNode }) =&gt; {       \/\/ \u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0443\u0437\u0435\u043b \u0432 \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0435, \u0435\u0441\u043b\u0438 \u0432\u0441\u0435 \u0435\u0433\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u0438 \u0431\u044b\u043b\u0438 \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u044b       visited[currentNode.getKey()] = currentNode        \/\/ \u0423\u0434\u0430\u043b\u044f\u0435\u043c \u0443\u0437\u0435\u043b \u0438\u0437 \u043d\u0435\u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0445       delete unvisited[currentNode.getKey()]     },     \/\/ \u041e\u0431\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a \u0432\u044b\u0445\u043e\u0434\u0430 \u0438\u0437 \u0443\u0437\u043b\u0430     leaveNode: ({ currentNode }) =&gt; {       \/\/ \u041f\u043e\u043c\u0435\u0449\u0430\u0435\u043c \u043f\u043e\u043b\u043d\u043e\u0441\u0442\u044c\u044e \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u0443\u0437\u0435\u043b \u0432 \u0441\u0442\u0435\u043a       stack.push(currentNode)     },     \/\/ \u041e\u0431\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0431\u0445\u043e\u0434\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e \u0443\u0437\u043b\u0430     allowTraverse: ({ nextNode }) =&gt; {       \/\/ \u0417\u0430\u043f\u0440\u0435\u0449\u0430\u0435\u043c \u043e\u0431\u0445\u043e\u0434 \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432       return !visited[nextNode.getKey()]     },   }    \/\/ \u041f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0435\u043c \u043d\u0435\u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0435 \u0443\u0437\u043b\u044b   while (Object.keys(unvisited).length) {     const currentKey = Object.keys(unvisited)[0]     const currentNode = unvisited[currentKey]      depthFirstSearch(graph, currentNode, callbacks)   }    \/\/ \u041f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u0443\u0435\u043c \u0441\u0442\u0435\u043a \u0432 \u043c\u0430\u0441\u0441\u0438\u0432 \u0438 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c \u0435\u0433\u043e   return stack.toArray() }<\/code><\/pre>\n<p> <\/p>\n<p><strong>\u0422\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435<\/strong><\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ algorithms\/graphs\/__tests__\/topological-sort.test.js import GraphEdge from '..\/..\/..\/data-structures\/graph\/edge' import Graph from '..\/..\/..\/data-structures\/graph\/index' import GraphNode from '..\/..\/..\/data-structures\/graph\/node' import topologicalSort from '..\/topological-sort'  describe('topologicalSort', () =&gt; {   it('\u0434\u043e\u043b\u0436\u0435\u043d \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u0442\u043e\u043f\u043e\u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0443 \u0443\u0437\u043b\u043e\u0432 \u0433\u0440\u0430\u0444\u0430', () =&gt; {     const nodeA = new GraphNode('A')     const nodeB = new GraphNode('B')     const nodeC = new GraphNode('C')     const nodeD = new GraphNode('D')     const nodeE = new GraphNode('E')     const nodeF = new GraphNode('F')     const nodeG = new GraphNode('G')     const nodeH = new GraphNode('H')      const edgeAC = new GraphEdge(nodeA, nodeC)     const edgeBC = new GraphEdge(nodeB, nodeC)     const edgeBD = new GraphEdge(nodeB, nodeD)     const edgeCE = new GraphEdge(nodeC, nodeE)     const edgeDF = new GraphEdge(nodeD, nodeF)     const edgeEF = new GraphEdge(nodeE, nodeF)     const edgeEH = new GraphEdge(nodeE, nodeH)     const edgeFG = new GraphEdge(nodeF, nodeG)      const graph = new Graph(true)      graph       .addEdge(edgeAC)       .addEdge(edgeBC)       .addEdge(edgeBD)       .addEdge(edgeCE)       .addEdge(edgeDF)       .addEdge(edgeEF)       .addEdge(edgeEH)       .addEdge(edgeFG)      const sortedVertices = topologicalSort(graph)      expect(sortedVertices).toBeDefined()     expect(sortedVertices.length).toBe(graph.getAllNodes().length)     expect(sortedVertices).toEqual([       nodeB,       nodeD,       nodeA,       nodeC,       nodeE,       nodeH,       nodeF,       nodeG,     ])   }) })<\/code><\/pre>\n<p> <\/p>\n<p>\u0417\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u0442\u0435\u0441\u0442\u044b:<\/p>\n<p> <\/p>\n<pre><code class=\"bash\">npm run test .\/algorithms\/graphs\/__tests__\/topological-sort<\/code><\/pre>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/dm\/si\/h9\/dmsih9frsgqbno8e9r5wryz3gei.png\" data-src=\"https:\/\/habrastorage.org\/webt\/dm\/si\/h9\/dmsih9frsgqbno8e9r5wryz3gei.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<h2 id=\"-tochka-sochleneniya\">\u276f \u0422\u043e\u0447\u043a\u0430 \u0441\u043e\u0447\u043b\u0435\u043d\u0435\u043d\u0438\u044f<\/h2>\n<p> <\/p>\n<p><strong>\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435<\/strong><\/p>\n<p> <\/p>\n<ul>\n<li><a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%A2%D0%BE%D1%87%D0%BA%D0%B0_%D1%81%D0%BE%D1%87%D0%BB%D0%B5%D0%BD%D0%B5%D0%BD%D0%B8%D1%8F\">\u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u044f<\/a><\/li>\n<li><a href=\"https:\/\/www.geeksforgeeks.org\/articulation-points-or-cut-vertices-in-a-graph\/\">GeekForGeeks<\/a><\/li>\n<li><a href=\"https:\/\/www.youtube.com\/watch?v=2kREIkF9UAs\">YouTube<\/a><\/li>\n<\/ul>\n<p> <\/p>\n<p>\u0422\u043e\u0447\u043a\u043e\u0439 \u0441\u043e\u0447\u043b\u0435\u043d\u0435\u043d\u0438\u044f (articulation point) \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u0433\u0440\u0430\u0444\u0430, \u043f\u0440\u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0438 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442 \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u0438 \u0432\u043e\u0437\u0440\u0430\u0441\u0442\u0430\u0435\u0442. \u0414\u043b\u044f \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u044d\u0442\u043e\u0433\u043e \u043f\u043e\u043d\u044f\u0442\u0438\u044f \u0442\u0430\u043a\u0436\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f \u0442\u0435\u0440\u043c\u0438\u043d\u044b &#171;\u0440\u0430\u0437\u0434\u0435\u043b\u044f\u044e\u0449\u0430\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430&#187; \u0438 &#171;\u0448\u0430\u0440\u043d\u0438\u0440&#187;.<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/xe\/7b\/cg\/xe7bcgrnxiehafg7x5mllx5vswm.png\" data-src=\"https:\/\/habrastorage.org\/webt\/xe\/7b\/cg\/xe7bcgrnxiehafg7x5mllx5vswm.png\"\/> <\/p>\n<p><em>\u041a\u0430\u0436\u0434\u044b\u0439 \u0446\u0432\u0435\u0442 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442 \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u0438. \u041c\u043d\u043e\u0433\u043e\u0446\u0432\u0435\u0442\u043d\u044b\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u2014 \u0442\u043e\u0447\u043a\u0438 \u0441\u043e\u0447\u043b\u0435\u043d\u0435\u043d\u0438\u044f, \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0430\u0449\u0438\u0435 \u0440\u0430\u0437\u043d\u044b\u043c \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u0430\u043c \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u0438<\/em><\/p>\n<p> <\/p>\n<p>\u0412\u0435\u0440\u0448\u0438\u043d\u0430 \u0433\u0440\u0430\u0444\u0430 <code>G<\/code> \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0448\u0430\u0440\u043d\u0438\u0440\u043e\u043c, \u0435\u0441\u043b\u0438 \u043f\u043e\u0434\u0433\u0440\u0430\u0444 <code>G1<\/code>, \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u043d\u044b\u0439 \u0438\u0437 \u0433\u0440\u0430\u0444\u0430 <code>G<\/code> \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435\u043c \u0432\u0435\u0440\u0448\u0438\u043d\u044b <code>v<\/code> \u0438 \u0432\u0441\u0435\u0445 \u0438\u043d\u0446\u0438\u0434\u0435\u043d\u0442\u043d\u044b\u0445 \u0435\u0439 \u0440\u0435\u0431\u0435\u0440, \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 \u0431\u043e\u043b\u044c\u0448\u0435\u0433\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442 \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u0438, \u0447\u0435\u043c \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u0433\u0440\u0430\u0444 <code>G<\/code>.<\/p>\n<p> <\/p>\n<p>\u0421 \u043f\u043e\u043d\u044f\u0442\u0438\u0435\u043c \u0448\u0430\u0440\u043d\u0438\u0440\u0430 \u0442\u0430\u043a\u0436\u0435 \u0441\u0432\u044f\u0437\u0430\u043d\u043e \u043f\u043e\u043d\u044f\u0442\u0438\u0435 \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u0438. <em>\u0414\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u044b\u0439 \u0433\u0440\u0430\u0444<\/em> \u2014 \u0441\u0432\u044f\u0437\u043d\u044b\u0439 \u0433\u0440\u0430\u0444, \u043d\u0435 \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0439 \u0448\u0430\u0440\u043d\u0438\u0440\u043e\u0432. <em>\u041a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u0430 \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u0438<\/em> \u2014 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 (\u043f\u043e \u0432\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u044e) \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u044b\u0439 \u043f\u043e\u0434\u0433\u0440\u0430\u0444 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0433\u0440\u0430\u0444\u0430. \u041a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u044b \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u0438 \u0438\u043d\u043e\u0433\u0434\u0430 \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442 \u0431\u043b\u043e\u043a\u0430\u043c\u0438.<\/p>\n<p> <\/p>\n<p>\u0420\u0435\u0431\u0435\u0440\u043d\u044b\u043c \u0430\u043d\u0430\u043b\u043e\u0433\u043e\u043c \u0448\u0430\u0440\u043d\u0438\u0440\u0430 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f <em>\u043c\u043e\u0441\u0442<\/em>. \u041c\u043e\u0441\u0442\u043e\u043c \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0442\u0430\u043a\u043e\u0435 \u0440\u0435\u0431\u0440\u043e \u0433\u0440\u0430\u0444\u0430, \u0432 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442 \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u0438 \u0432 \u0433\u0440\u0430\u0444\u0435 \u0432\u043e\u0437\u0440\u0430\u0441\u0442\u0430\u0435\u0442 (\u0441\u043c. \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0440\u0430\u0437\u0434\u0435\u043b).<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/mk\/o-\/sa\/mko-sanqelzqedhzrxh-g6taqfa.png\" data-src=\"https:\/\/habrastorage.org\/webt\/mk\/o-\/sa\/mko-sanqelzqedhzrxh-g6taqfa.png\"\/> <\/p>\n<p><em>\u0413\u0440\u0430\u0444, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0439 \u0434\u0432\u0430 \u0448\u0430\u0440\u043d\u0438\u0440\u0430 (\u0432\u0435\u0440\u0448\u0438\u043d\u044b 2 \u0438 5) \u0438 \u0442\u0440\u0438 \u0431\u043b\u043e\u043a\u0430 (<code>1,2<\/code>, <code>2,3,4,5<\/code>, <code>5,6<\/code>)<\/em><\/p>\n<p> <\/p>\n<p><strong>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/strong><\/p>\n<p> <\/p>\n<p>\u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0434\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u0442\u043e\u0447\u0435\u043a \u0441\u043e\u0447\u043b\u0435\u043d\u0435\u043d\u0438\u044f \u0432 \u0433\u0440\u0430\u0444\u0435. \u0412 \u043d\u0430\u0448\u0435\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043c\u044b \u0432 \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0439 \u0440\u0430\u0437 \u043f\u0440\u0438\u0431\u0435\u0433\u043d\u0435\u043c \u0441 \u0441\u0442\u0430\u0440\u043e\u043c\u0443-\u0434\u043e\u0431\u0440\u043e\u043c\u0443 <a href=\"https:\/\/habr.com\/ru\/companies\/timeweb\/articles\/896800\/\">\u043f\u043e\u0438\u0441\u043a\u0443 \u0432 \u0433\u043b\u0443\u0431\u0438\u043d\u0443<\/a>:<\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ algorithms\/graphs\/articulation-points.js import depthFirstSearch from '.\/depth-first-search'  \/\/ \u041c\u0435\u0442\u0430\u0434\u0430\u043d\u043d\u044b\u0435 \u0443\u0437\u043b\u0430 class VisitMetadata {   constructor({ discoveryTime, lowDiscoveryTime }) {     \/\/ \u0412\u0440\u0435\u043c\u044f \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f     this.discoveryTime = discoveryTime     \/\/ \u041d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u0432\u0440\u0435\u043c\u044f \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f     this.lowDiscoveryTime = lowDiscoveryTime     \/\/ \u0421\u0447\u0435\u0442\u0447\u0438\u043a \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u044b\u0445 \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u0432     this.independentChildrenCount = 0   } }  \/\/ \u0424\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u0433\u0440\u0430\u0444 export default function articulationPoints(graph) {   \/\/ \u041f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b   const visited = {}    \/\/ \u0422\u043e\u0447\u043a\u0438 \u0441\u043e\u0447\u043b\u0435\u043d\u0435\u043d\u0438\u044f   const articulationPoints = {}    \/\/ \u0412\u0440\u0435\u043c\u044f, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0435 \u0434\u043b\u044f \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u0443\u0437\u043b\u0430   \/\/ (\u0438\u0437\u043c\u0435\u0440\u044f\u0435\u0442\u0441\u044f \u0432 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0435 \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u0438\u0439 \u0443\u0437\u043b\u043e\u0432)   let discoveryTime = 0    const startNode = graph.getAllNodes()[0]    \/\/ \u041e\u0431\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a\u0438 \u0434\u043b\u044f DFS   const callbacks = {     \/\/ \u041e\u0431\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a \u0432\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u0432 \u0443\u0437\u0435\u043b     enterNode: ({ currentNode, previousNode }) =&gt; {       \/\/ \u0423\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u043c \u0432\u0440\u0435\u043c\u044f \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f       discoveryTime += 1        \/\/ \u041f\u043e\u043c\u0435\u0449\u0430\u0435\u043c \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u0443\u0437\u0435\u043b \u0432 \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0435       visited[currentNode.getKey()] = new VisitMetadata({         discoveryTime,         lowDiscoveryTime: discoveryTime,       })        if (previousNode) {         \/\/ \u041e\u0431\u043d\u043e\u0432\u043b\u044f\u0435\u043c \u0441\u0447\u0435\u0442\u0447\u0438\u043a \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u0432 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0433\u043e \u0443\u0437\u043b\u0430         visited[previousNode.getKey()].independentChildrenCount += 1       }     },     \/\/ \u041e\u0431\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a \u0432\u044b\u0445\u043e\u0434\u0430 \u0438\u0437 \u0443\u0437\u043b\u0430     leaveNode: ({ currentNode, previousNode }) =&gt; {       if (!previousNode) return        \/\/ \u041e\u0431\u043d\u043e\u0432\u043b\u044f\u0435\u043c `lowDiscoveryTime` \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0438\u043c \u0432\u0440\u0435\u043c\u0435\u043d\u0435\u043c \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445 \u0443\u0437\u043b\u043e\u0432       visited[currentNode.getKey()].lowDiscoveryTime = currentNode         .getNeighbors()         .filter((n) =&gt; n.getKey() !== previousNode.getKey())         .reduce((minTime, n) =&gt; {           const lowTime = visited[n.getKey()].lowDiscoveryTime           return lowTime &lt; minTime ? lowTime : minTime         }, visited[currentNode.getKey()].lowDiscoveryTime)        \/\/ \u041e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u043c, \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0438 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0439 \u0443\u0437\u0435\u043b \u0442\u043e\u0447\u043a\u043e\u0439 \u0441\u043e\u0447\u043b\u0435\u043d\u0435\u043d\u0438\u044f.       \/\/ \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043d\u0443\u0436\u043d\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c \u0434\u0432\u0430 \u0443\u0441\u043b\u043e\u0432\u0438\u044f \u0418\u041b\u0418:       \/\/ 1. \u042d\u0442\u043e \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u0443\u0437\u0435\u043b \u0441 (\u043c\u0438\u043d\u0438\u043c\u0443\u043c) \u0434\u0432\u0443\u043c\u044f \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u044b\u043c\u0438 \u043f\u043e\u0442\u043e\u043c\u043a\u0430\u043c\u0438.       \/\/ 2. \u0415\u0433\u043e \u0432\u0440\u0435\u043c\u044f \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f &lt;= \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u0432\u0440\u0435\u043c\u044f \u0441\u043e\u0441\u0435\u0434\u0430       if (previousNode === startNode) {         \/\/ \u041f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c, \u0447\u0442\u043e \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0439 \u0443\u0437\u0435\u043b \u0438\u043c\u0435\u0435\u0442 \u043a\u0430\u043a \u043c\u0438\u043d\u0438\u043c\u0443\u043c \u0434\u0432\u0443\u0445 \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u044b\u0445 \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u0432         if (visited[previousNode.getKey()].independentChildrenCount &gt; 1) {           articulationPoints[previousNode.getKey()] = previousNode         }       } else {         const currentLDT = visited[currentNode.getKey()].lowDiscoveryTime         const parentDT = visited[previousNode.getKey()].discoveryTime         \/\/ \u041f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c, \u0447\u0442\u043e \u0432\u0440\u0435\u043c\u044f \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f \u0443\u0437\u043b\u0430 &lt;= \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u0432\u0440\u0435\u043c\u044f \u0441\u043e\u0441\u0435\u0434\u0430         if (parentDT &lt;= currentLDT) {           articulationPoints[previousNode.getKey()] = previousNode         }       }     },     \/\/ \u041e\u0431\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u043e\u0441\u0442\u0438 \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f \u0443\u0437\u043b\u0430     allowTraverse: ({ nextNode }) =&gt; {       \/\/ \u0417\u0430\u043f\u0440\u0435\u0449\u0430\u0435\u043c \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u0435 \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432       return !visited[nextNode.getKey()]     },   }    \/\/ \u0417\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u043f\u043e\u0438\u0441\u043a \u0432 \u0433\u043b\u0443\u0431\u0438\u043d\u0443   depthFirstSearch(graph, startNode, callbacks)    return articulationPoints }<\/code><\/pre>\n<p> <\/p>\n<div class=\"spoiler\" role=\"button\" tabindex=\"0\">                         <b class=\"spoiler_title\">\u0422\u0435\u0441\u0442\u044b:<\/b>                         <\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"javascript\">\/\/ algorithms\/graphs\/__tests__\/articulation-points.test.js import GraphEdge from '..\/..\/..\/data-structures\/graph\/edge' import Graph from '..\/..\/..\/data-structures\/graph\/index' import GraphNode from '..\/..\/..\/data-structures\/graph\/node' import articulationPoints from '..\/articulation-points'  describe('articulationPoints', () =&gt; {   it('\u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0439\u0442\u0438 \u0442\u043e\u0447\u043a\u0438 \u0441\u043e\u0447\u043b\u0435\u043d\u0435\u043d\u0438\u044f \u0432 \u043f\u0440\u043e\u0441\u0442\u043e\u043c \u0433\u0440\u0430\u0444\u0435', () =&gt; {     const nodeA = new GraphNode('A')     const nodeB = new GraphNode('B')     const nodeC = new GraphNode('C')     const nodeD = new GraphNode('D')      const edgeAB = new GraphEdge(nodeA, nodeB)     const edgeBC = new GraphEdge(nodeB, nodeC)     const edgeCD = new GraphEdge(nodeC, nodeD)      const graph = new Graph()      graph.addEdge(edgeAB).addEdge(edgeBC).addEdge(edgeCD)      const articulationPointsSet = Object.values(articulationPoints(graph))      expect(articulationPointsSet.length).toBe(2)     expect(articulationPointsSet[0].getKey()).toBe(nodeC.getKey())     expect(articulationPointsSet[1].getKey()).toBe(nodeB.getKey())   })    it('\u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0439\u0442\u0438 \u0442\u043e\u0447\u043a\u0438 \u0441\u043e\u0447\u043b\u0435\u043d\u0435\u043d\u0438\u044f \u0432 \u043f\u0440\u043e\u0441\u0442\u043e\u043c \u0433\u0440\u0430\u0444\u0435 \u0441 \u043e\u0431\u0440\u0430\u0442\u043d\u044b\u043c \u0440\u0435\u0431\u0440\u043e\u043c #1', () =&gt; {     const nodeA = new GraphNode('A')     const nodeB = new GraphNode('B')     const nodeC = new GraphNode('C')     const nodeD = new GraphNode('D')      const edgeAB = new GraphEdge(nodeA, nodeB)     const edgeBC = new GraphEdge(nodeB, nodeC)     const edgeCD = new GraphEdge(nodeC, nodeD)     const edgeAC = new GraphEdge(nodeA, nodeC)      const graph = new Graph()      graph.addEdge(edgeAB).addEdge(edgeAC).addEdge(edgeBC).addEdge(edgeCD)      const articulationPointsSet = Object.values(articulationPoints(graph))      expect(articulationPointsSet.length).toBe(1)     expect(articulationPointsSet[0].getKey()).toBe(nodeC.getKey())   })    it('\u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0439\u0442\u0438 \u0442\u043e\u0447\u043a\u0438 \u0441\u043e\u0447\u043b\u0435\u043d\u0435\u043d\u0438\u044f \u0432 \u043f\u0440\u043e\u0441\u0442\u043e\u043c \u0433\u0440\u0430\u0444\u0435 \u0441 \u043e\u0431\u0440\u0430\u0442\u043d\u044b\u043c \u0440\u0435\u0431\u0440\u043e\u043c #2', () =&gt; {     const nodeA = new GraphNode('A')     const nodeB = new GraphNode('B')     const nodeC = new GraphNode('C')     const nodeD = new GraphNode('D')     const nodeE = new GraphNode('E')      const edgeAB = new GraphEdge(nodeA, nodeB)     const edgeBC = new GraphEdge(nodeB, nodeC)     const edgeCD = new GraphEdge(nodeC, nodeD)     const edgeAE = new GraphEdge(nodeA, nodeE)     const edgeCE = new GraphEdge(nodeC, nodeE)      const graph = new Graph()      graph       .addEdge(edgeAB)       .addEdge(edgeAE)       .addEdge(edgeCE)       .addEdge(edgeBC)       .addEdge(edgeCD)      const articulationPointsSet = Object.values(articulationPoints(graph))      expect(articulationPointsSet.length).toBe(1)     expect(articulationPointsSet[0].getKey()).toBe(nodeC.getKey())   })    it('\u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0439\u0442\u0438 \u0442\u043e\u0447\u043a\u0438 \u0441\u043e\u0447\u043b\u0435\u043d\u0435\u043d\u0438\u044f \u0432 \u0433\u0440\u0430\u0444\u0435', () =&gt; {     const nodeA = new GraphNode('A')     const nodeB = new GraphNode('B')     const nodeC = new GraphNode('C')     const nodeD = new GraphNode('D')     const nodeE = new GraphNode('E')     const nodeF = new GraphNode('F')     const nodeG = new GraphNode('G')     const nodeH = new GraphNode('H')      const edgeAB = new GraphEdge(nodeA, nodeB)     const edgeBC = new GraphEdge(nodeB, nodeC)     const edgeAC = new GraphEdge(nodeA, nodeC)     const edgeCD = new GraphEdge(nodeC, nodeD)     const edgeDE = new GraphEdge(nodeD, nodeE)     const edgeEG = new GraphEdge(nodeE, nodeG)     const edgeEF = new GraphEdge(nodeE, nodeF)     const edgeGF = new GraphEdge(nodeG, nodeF)     const edgeFH = new GraphEdge(nodeF, nodeH)      const graph = new Graph()      graph       .addEdge(edgeAB)       .addEdge(edgeBC)       .addEdge(edgeAC)       .addEdge(edgeCD)       .addEdge(edgeDE)       .addEdge(edgeEG)       .addEdge(edgeEF)       .addEdge(edgeGF)       .addEdge(edgeFH)      const articulationPointsSet = Object.values(articulationPoints(graph))      expect(articulationPointsSet.length).toBe(4)     expect(articulationPointsSet[0].getKey()).toBe(nodeF.getKey())     expect(articulationPointsSet[1].getKey()).toBe(nodeE.getKey())     expect(articulationPointsSet[2].getKey()).toBe(nodeD.getKey())     expect(articulationPointsSet[3].getKey()).toBe(nodeC.getKey())   })    it('\u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0439\u0442\u0438 \u0442\u043e\u0447\u043a\u0438 \u0441\u043e\u0447\u043b\u0435\u043d\u0435\u043d\u0438\u044f \u0432 \u0433\u0440\u0430\u0444\u0435, \u043d\u0430\u0447\u0438\u043d\u0430\u044e\u0449\u0435\u043c\u0441\u044f \u0441 \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430-\u0448\u0430\u0440\u043d\u0438\u0440\u0430', () =&gt; {     const nodeA = new GraphNode('A')     const nodeB = new GraphNode('B')     const nodeC = new GraphNode('C')     const nodeD = new GraphNode('D')     const nodeE = new GraphNode('E')     const nodeF = new GraphNode('F')     const nodeG = new GraphNode('G')     const nodeH = new GraphNode('H')      const edgeAB = new GraphEdge(nodeA, nodeB)     const edgeBC = new GraphEdge(nodeB, nodeC)     const edgeAC = new GraphEdge(nodeA, nodeC)     const edgeCD = new GraphEdge(nodeC, nodeD)     const edgeDE = new GraphEdge(nodeD, nodeE)     const edgeEG = new GraphEdge(nodeE, nodeG)     const edgeEF = new GraphEdge(nodeE, nodeF)     const edgeGF = new GraphEdge(nodeG, nodeF)     const edgeFH = new GraphEdge(nodeF, nodeH)      const graph = new Graph()      graph       .addEdge(edgeDE)       .addEdge(edgeAB)       .addEdge(edgeBC)       .addEdge(edgeAC)       .addEdge(edgeCD)       .addEdge(edgeEG)       .addEdge(edgeEF)       .addEdge(edgeGF)       .addEdge(edgeFH)      const articulationPointsSet = Object.values(articulationPoints(graph))      expect(articulationPointsSet.length).toBe(4)     expect(articulationPointsSet[0].getKey()).toBe(nodeF.getKey())     expect(articulationPointsSet[1].getKey()).toBe(nodeE.getKey())     expect(articulationPointsSet[2].getKey()).toBe(nodeC.getKey())     expect(articulationPointsSet[3].getKey()).toBe(nodeD.getKey())   })    it('\u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0439\u0442\u0438 \u0442\u043e\u0447\u043a\u0438 \u0441\u043e\u0447\u043b\u0435\u043d\u0435\u043d\u0438\u044f \u0435\u0449\u0435 \u0432 \u043e\u0434\u043d\u043e\u043c \u0433\u0440\u0430\u0444\u0435 #1', () =&gt; {     const nodeA = new GraphNode('A')     const nodeB = new GraphNode('B')     const nodeC = new GraphNode('C')     const nodeD = new GraphNode('D')     const nodeE = new GraphNode('E')      const edgeAB = new GraphEdge(nodeA, nodeB)     const edgeAC = new GraphEdge(nodeA, nodeC)     const edgeBC = new GraphEdge(nodeB, nodeC)     const edgeCD = new GraphEdge(nodeC, nodeD)     const edgeDE = new GraphEdge(nodeD, nodeE)      const graph = new Graph()      graph       .addEdge(edgeAB)       .addEdge(edgeAC)       .addEdge(edgeBC)       .addEdge(edgeCD)       .addEdge(edgeDE)      const articulationPointsSet = Object.values(articulationPoints(graph))      expect(articulationPointsSet.length).toBe(2)     expect(articulationPointsSet[0].getKey()).toBe(nodeD.getKey())     expect(articulationPointsSet[1].getKey()).toBe(nodeC.getKey())   })    it('\u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0439\u0442\u0438 \u0442\u043e\u0447\u043a\u0438 \u0441\u043e\u0447\u043b\u0435\u043d\u0435\u043d\u0438\u044f \u0435\u0449\u0435 \u0432 \u043e\u0434\u043d\u043e\u043c \u0433\u0440\u0430\u0444\u0435 #2', () =&gt; {     const nodeA = new GraphNode('A')     const nodeB = new GraphNode('B')     const nodeC = new GraphNode('C')     const nodeD = new GraphNode('D')     const nodeE = new GraphNode('E')     const nodeF = new GraphNode('F')     const nodeG = new GraphNode('G')      const edgeAB = new GraphEdge(nodeA, nodeB)     const edgeAC = new GraphEdge(nodeA, nodeC)     const edgeBC = new GraphEdge(nodeB, nodeC)     const edgeCD = new GraphEdge(nodeC, nodeD)     const edgeCE = new GraphEdge(nodeC, nodeE)     const edgeCF = new GraphEdge(nodeC, nodeF)     const edgeEG = new GraphEdge(nodeE, nodeG)     const edgeFG = new GraphEdge(nodeF, nodeG)      const graph = new Graph()      graph       .addEdge(edgeAB)       .addEdge(edgeAC)       .addEdge(edgeBC)       .addEdge(edgeCD)       .addEdge(edgeCE)       .addEdge(edgeCF)       .addEdge(edgeEG)       .addEdge(edgeFG)      const articulationPointsSet = Object.values(articulationPoints(graph))      expect(articulationPointsSet.length).toBe(1)     expect(articulationPointsSet[0].getKey()).toBe(nodeC.getKey())   }) })<\/code><\/pre>\n<\/div><\/div>\n<p> <\/p>\n<p>\u0417\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u0442\u0435\u0441\u0442\u044b:<\/p>\n<p> <\/p>\n<pre><code class=\"bash\">npm run test .\/algorithms\/graphs\/__tests__\/articulation-points<\/code><\/pre>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/rz\/uq\/yz\/rzuqyznhkbxu8rsqvk_fabvze0s.png\" data-src=\"https:\/\/habrastorage.org\/webt\/rz\/uq\/yz\/rzuqyznhkbxu8rsqvk_fabvze0s.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<h2 id=\"-most\">\u276f \u041c\u043e\u0441\u0442<\/h2>\n<p> <\/p>\n<p><strong>\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435<\/strong><\/p>\n<p> <\/p>\n<ul>\n<li><a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%9C%D0%BE%D1%81%D1%82_(%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2)\">\u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u044f<\/a><\/li>\n<li><a href=\"https:\/\/www.geeksforgeeks.org\/bridge-in-a-graph\/\">GeekForGeeks<\/a><\/li>\n<li><a href=\"https:\/\/www.youtube.com\/watch?v=thLQYBlz2DM\">YouTube<\/a><\/li>\n<\/ul>\n<p> <\/p>\n<p>\u041c\u043e\u0441\u0442 (bridge) \u2014 \u044d\u0442\u043e \u0440\u0435\u0431\u0440\u043e, \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442 \u0447\u0438\u0441\u043b\u043e \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442 \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u0438. \u0422\u0430\u043a\u0438\u0435 \u0440\u0435\u0431\u0440\u0430 \u0442\u0430\u043a\u0436\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b \u043a\u0430\u043a \u0440\u0430\u0437\u0440\u0435\u0437\u0430\u044e\u0449\u0438\u0435 \u0440\u0435\u0431\u0440\u0430 (cut-edge), \u0440\u0430\u0437\u0440\u0435\u0437\u0430\u044e\u0449\u0438\u0435 \u0434\u0443\u0433\u0438 (cut arc) \u0438\u043b\u0438 \u043f\u0435\u0440\u0435\u0448\u0435\u0439\u043a\u0438 (isthmus). \u042d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u043d\u043e\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u2014 \u0440\u0435\u0431\u0440\u043e \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043c\u043e\u0441\u0442\u043e\u043c \u0432 \u0442\u043e\u043c \u0438 \u0442\u043e\u043b\u044c\u043a\u043e \u0432 \u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u0435\u0441\u043b\u0438 \u043e\u043d\u043e \u043d\u0435 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442\u0441\u044f \u043d\u0438 \u0432 \u043e\u0434\u043d\u043e\u043c \u0446\u0438\u043a\u043b\u0435.<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/t0\/m2\/br\/t0m2brq9hrvpjhotmk3ylvnlljm.png\" data-src=\"https:\/\/habrastorage.org\/webt\/t0\/m2\/br\/t0m2brq9hrvpjhotmk3ylvnlljm.png\"\/> <\/p>\n<p><em>\u0413\u0440\u0430\u0444 \u0441 6 \u043c\u043e\u0441\u0442\u0430\u043c\u0438 (\u0432\u044b\u0434\u0435\u043b\u0435\u043d\u044b \u043a\u0440\u0430\u0441\u043d\u044b\u043c)<\/em><\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/lz\/kw\/zt\/lzkwztw_un8n6v0wcgptwyydvui.png\" data-src=\"https:\/\/habrastorage.org\/webt\/lz\/kw\/zt\/lzkwztw_un8n6v0wcgptwyydvui.png\"\/> <\/p>\n<p><em>\u041d\u0435\u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u0441\u0432\u044f\u0437\u043d\u044b\u0439 \u0433\u0440\u0430\u0444, \u043d\u0435 \u0438\u043c\u0435\u044e\u0449\u0438\u0439 \u043c\u043e\u0441\u0442\u043e\u0432<\/em><\/p>\n<p> <\/p>\n<p><em>\u0414\u0435\u0440\u0435\u0432\u044c\u044f \u0438 \u043b\u0435\u0441\u0430<\/em><\/p>\n<p> <\/p>\n<p>\u0413\u0440\u0430\u0444 \u0441 <code>n<\/code> \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u043c\u0438 \u043c\u043e\u0436\u0435\u0442 \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442\u044c \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 <code>n-1<\/code> \u043c\u043e\u0441\u0442\u043e\u0432, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0435\u0449\u0435 \u043e\u0434\u043d\u043e\u0433\u043e \u0440\u0435\u0431\u0440\u0430 \u043d\u0435\u043c\u0438\u043d\u0443\u0435\u043c\u043e \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u0442 \u043a \u043f\u043e\u044f\u0432\u043b\u0435\u043d\u0438\u044e \u0446\u0438\u043a\u043b\u0430. \u0413\u0440\u0430\u0444\u044b, \u0438\u043c\u0435\u044e\u0449\u0438\u0435 \u0432 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u0438 <code>n-1<\/code> \u043c\u043e\u0441\u0442\u043e\u0432, \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b \u043a\u0430\u043a <em>\u0434\u0435\u0440\u0435\u0432\u044c\u044f<\/em>, \u0430 \u0433\u0440\u0430\u0444\u044b, \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043b\u044e\u0431\u043e\u0435 \u0440\u0435\u0431\u0440\u043e \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043c\u043e\u0441\u0442\u043e\u043c \u2014 \u044d\u0442\u043e <em>\u043b\u0435\u0441\u0430<\/em>.<\/p>\n<p> <\/p>\n<p><em>\u0421\u0432\u044f\u0437\u044c \u0441 \u0432\u0435\u0440\u0448\u0438\u043d\u043d\u043e\u0439 \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u044c\u044e<\/em><\/p>\n<p> <\/p>\n<p>\u041c\u043e\u0441\u0442\u044b \u0442\u0435\u0441\u043d\u043e \u0441\u0432\u044f\u0437\u0430\u043d\u044b \u0441 \u043a\u043e\u043d\u0446\u0435\u043f\u0446\u0438\u0435\u0439 \u0448\u0430\u0440\u043d\u0438\u0440\u043e\u0432 (\u0441\u043c. \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0439 \u0440\u0430\u0437\u0434\u0435\u043b) \u2014 \u0432\u0435\u0440\u0448\u0438\u043d, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0432\u0445\u043e\u0434\u044f\u0442 \u0432 \u043b\u044e\u0431\u043e\u0439 \u043f\u0443\u0442\u044c, \u0441\u043e\u0435\u0434\u0438\u043d\u044f\u044e\u0449\u0438\u0439 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0434\u0432\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b. \u0414\u0432\u0435 \u043a\u043e\u043d\u0435\u0447\u043d\u044b\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u043c\u043e\u0441\u0442\u0430 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0448\u0430\u0440\u043d\u0438\u0440\u0430\u043c\u0438, \u0435\u0441\u043b\u0438 \u043e\u043d\u0438 \u043d\u0435 \u0438\u043c\u0435\u044e\u0442 \u0441\u0442\u0435\u043f\u0435\u043d\u044c 1, \u0445\u043e\u0442\u044f \u0440\u0435\u0431\u0440\u0430, \u043d\u0435 \u044f\u0432\u043b\u044f\u044e\u0449\u0438\u0435\u0441\u044f \u043c\u043e\u0441\u0442\u0430\u043c\u0438, \u0442\u043e\u0436\u0435 \u043c\u043e\u0433\u0443\u0442 \u0441 \u043e\u0431\u043e\u0438\u0445 \u043a\u043e\u043d\u0446\u043e\u0432 \u0438\u043c\u0435\u0442\u044c \u0448\u0430\u0440\u043d\u0438\u0440\u044b. \u0410\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e \u0433\u0440\u0430\u0444\u0430\u043c \u0431\u0435\u0437 \u043c\u043e\u0441\u0442\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0440\u0435\u0431\u0435\u0440\u043d\u043e \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u044b, \u0433\u0440\u0430\u0444\u044b \u0431\u0435\u0437 \u0448\u0430\u0440\u043d\u0438\u0440\u043e\u0432 \u0432\u0435\u0440\u0448\u0438\u043d\u043d\u043e \u0434\u0432\u0443\u0441\u0432\u044f\u0437\u043d\u044b.<\/p>\n<p> <\/p>\n<p><strong>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/strong><\/p>\n<p> <\/p>\n<p>\u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0434\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u043c\u043e\u0441\u0442\u043e\u0432 \u0432 \u0433\u0440\u0430\u0444\u0435. \u0412 \u043d\u0430\u0448\u0435\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043c\u044b \u0432 \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0439 \u0440\u0430\u0437 \u043f\u0440\u0438\u0431\u0435\u0433\u043d\u0435\u043c \u0441 \u0441\u0442\u0430\u0440\u043e\u043c\u0443-\u0434\u043e\u0431\u0440\u043e\u043c\u0443 <a href=\"https:\/\/habr.com\/ru\/companies\/timeweb\/articles\/896800\/\">\u043f\u043e\u0438\u0441\u043a\u0443 \u0432 \u0433\u043b\u0443\u0431\u0438\u043d\u0443<\/a>:<\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ algorithms\/graphs\/bridges.js import depthFirstSearch from '.\/depth-first-search'  \/\/ \u041c\u0435\u0442\u0430\u0434\u0430\u043d\u043d\u044b\u0435 \u0443\u0437\u043b\u0430 class VisitMetadata {   constructor({ discoveryTime, lowDiscoveryTime }) {     \/\/ \u0412\u0440\u0435\u043c\u044f \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f     this.discoveryTime = discoveryTime     \/\/ \u041d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u0432\u0440\u0435\u043c\u044f \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f     this.lowDiscoveryTime = lowDiscoveryTime   } }  \/\/ \u0424\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u0433\u0440\u0430\u0444 export default function graphBridges(graph) {   \/\/ \u041f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0435 \u0443\u0437\u043b\u044b   const visited = {}   \/\/ \u041c\u043e\u0441\u0442\u044b   const bridges = {}    \/\/ \u0412\u0440\u0435\u043c\u044f, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0435 \u0434\u043b\u044f \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u0443\u0437\u043b\u0430   \/\/ (\u0438\u0437\u043c\u0435\u0440\u044f\u0435\u0442\u0441\u044f \u0432 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0435 \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u0438\u0439 \u0443\u0437\u043b\u043e\u0432)   let discoveryTime = 0    const startNode = graph.getAllNodes()[0]    \/\/ \u041e\u0431\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a\u0438 \u0434\u043b\u044f DFS   const callbacks = {     \/\/ \u041e\u0431\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a \u0432\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u0432 \u0443\u0437\u0435\u043b     enterNode: ({ currentNode }) =&gt; {       \/\/ \u0423\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u043c \u0432\u0440\u0435\u043c\u044f \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f       discoveryTime += 1        \/\/ \u041f\u043e\u043c\u0435\u0449\u0430\u0435\u043c \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u0443\u0437\u0435\u043b \u0432 \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0435       visited[currentNode.getKey()] = new VisitMetadata({         discoveryTime,         lowDiscoveryTime: discoveryTime,       })     },     \/\/ \u041e\u0431\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a \u0432\u044b\u0445\u043e\u0434\u0430 \u0438\u0437 \u0443\u0437\u043b\u0430     leaveNode: ({ currentNode, previousNode }) =&gt; {       if (!previousNode) return        \/\/ \u041e\u0431\u043d\u043e\u0432\u043b\u044f\u0435\u043c `lowDiscoveryTime` \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0438\u043c \u0432\u0440\u0435\u043c\u0435\u043d\u0435\u043c \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445 \u0443\u0437\u043b\u043e\u0432       visited[currentNode.getKey()].lowDiscoveryTime = currentNode         .getNeighbors()         .filter((n) =&gt; n.getKey() !== previousNode.getKey())         .reduce((minTime, n) =&gt; {           const lowTime = visited[n.getKey()].lowDiscoveryTime           return lowTime &lt; minTime ? lowTime : minTime         }, visited[currentNode.getKey()].lowDiscoveryTime)        \/\/ \u0421\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0435\u043c \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f.       \/\/ \u0415\u0441\u043b\u0438 \u0442\u0435\u043a\u0443\u0449\u0435\u0435 \u0432\u0440\u0435\u043c\u044f \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c \u0432\u0440\u0435\u043c\u044f \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0433\u043e \u0443\u0437\u043b\u0430,       \/\/ \u043e\u0431\u043d\u043e\u0432\u043b\u044f\u0435\u043c `lowDiscoveryTime` \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0433\u043e \u0443\u0437\u043b\u0430       const currentLDT = visited[currentNode.getKey()].lowDiscoveryTime       const previousLDT = visited[previousNode.getKey()].lowDiscoveryTime       if (currentLDT &lt; previousLDT) {         visited[previousNode.getKey()].lowDiscoveryTime = currentLDT       }        \/\/ \u0421\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0435\u043c \u0442\u0435\u043a\u0443\u0449\u0435\u0435 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f \u0441\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0435\u043c \u043f\u0440\u0435\u0434\u043a\u0430.       \/\/ \u041f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u043d\u0430\u043b\u0438\u0447\u0438\u0435 \u043a\u043e\u0440\u043e\u0442\u043a\u043e\u0433\u043e \u043f\u0443\u0442\u0438.       \/\/ \u0415\u0441\u043b\u0438 \u043c\u044b \u043d\u0435 \u043c\u043e\u0436\u0435\u043c \u0434\u043e\u0431\u0440\u0430\u0442\u044c\u0441\u044f \u0434\u043e \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u0443\u0437\u043b\u0430 \u0438\u043d\u0430\u0447\u0435, \u0447\u0435\u043c \u0447\u0435\u0440\u0435\u0437 \u043f\u0440\u0435\u0434\u043a\u0430,       \/\/ \u0437\u043d\u0430\u0447\u0438\u0442, \u0440\u0435\u0431\u0440\u043e \u043c\u0435\u0436\u0434\u0443 \u0442\u0435\u043a\u0443\u0449\u0438\u043c \u0443\u0437\u043b\u043e\u043c \u0438 \u0435\u0433\u043e \u043f\u0440\u0435\u0434\u043a\u043e\u043c \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043c\u043e\u0441\u0442\u043e\u043c       const parentLDT = visited[previousNode.getKey()].discoveryTime       if (parentLDT &lt; currentLDT) {         const bridge = graph.findEdge(previousNode, currentNode)         bridges[bridge.getKey()] = bridge       }     },     \/\/ \u041e\u0431\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0431\u0445\u043e\u0434\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e \u0443\u0437\u043b\u0430     allowTraverse: ({ nextNode }) =&gt; {       \/\/ \u0417\u0430\u043f\u0440\u0435\u0449\u0430\u0435\u043c \u043e\u0431\u0445\u043e\u0434 \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432       return !visited[nextNode.getKey()]     },   }    \/\/ \u0417\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u043f\u043e\u0438\u0441\u043a \u0432 \u0433\u043b\u0443\u0431\u0438\u043d\u0443   depthFirstSearch(graph, startNode, callbacks)    return bridges }<\/code><\/pre>\n<p> <\/p>\n<div class=\"spoiler\" role=\"button\" tabindex=\"0\">                         <b class=\"spoiler_title\">\u0422\u0435\u0441\u0442\u044b:<\/b>                         <\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"javascript\">\/\/ algorithms\/graphs\/__tests__\/bridges.test.js import Graph from '..\/..\/..\/data-structures\/graph\/index' import GraphNode from '..\/..\/..\/data-structures\/graph\/node' import GraphEdge from '..\/..\/..\/data-structures\/graph\/edge' import graphBridges from '..\/bridges'  describe('graphBridges', () =&gt; {   it('\u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0439\u0442\u0438 \u043c\u043e\u0441\u0442\u044b \u0432 \u043f\u0440\u043e\u0441\u0442\u043e\u043c \u0433\u0440\u0430\u0444\u0435', () =&gt; {     const nodeA = new GraphNode('A')     const nodeB = new GraphNode('B')     const nodeC = new GraphNode('C')     const nodeD = new GraphNode('D')      const edgeAB = new GraphEdge(nodeA, nodeB)     const edgeBC = new GraphEdge(nodeB, nodeC)     const edgeCD = new GraphEdge(nodeC, nodeD)      const graph = new Graph()      graph.addEdge(edgeAB).addEdge(edgeBC).addEdge(edgeCD)      const bridges = Object.values(graphBridges(graph))      expect(bridges.length).toBe(3)     expect(bridges[0].getKey()).toBe(edgeCD.getKey())     expect(bridges[1].getKey()).toBe(edgeBC.getKey())     expect(bridges[2].getKey()).toBe(edgeAB.getKey())   })    it('\u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0439\u0442\u0438 \u043c\u043e\u0441\u0442\u044b \u0432 \u043f\u0440\u043e\u0441\u0442\u043e\u043c \u0433\u0440\u0430\u0444\u0435 \u0441 \u043e\u0431\u0440\u0430\u0442\u043d\u044b\u043c \u0440\u0435\u0431\u0440\u043e\u043c', () =&gt; {     const nodeA = new GraphNode('A')     const nodeB = new GraphNode('B')     const nodeC = new GraphNode('C')     const nodeD = new GraphNode('D')      const edgeAB = new GraphEdge(nodeA, nodeB)     const edgeBC = new GraphEdge(nodeB, nodeC)     const edgeCD = new GraphEdge(nodeC, nodeD)     const edgeAC = new GraphEdge(nodeA, nodeC)      const graph = new Graph()      graph.addEdge(edgeAB).addEdge(edgeAC).addEdge(edgeBC).addEdge(edgeCD)      const bridges = Object.values(graphBridges(graph))      expect(bridges.length).toBe(1)     expect(bridges[0].getKey()).toBe(edgeCD.getKey())   })    it('\u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0439\u0442\u0438 \u043c\u043e\u0441\u0442\u044b \u0432 \u0433\u0440\u0430\u0444\u0435', () =&gt; {     const nodeA = new GraphNode('A')     const nodeB = new GraphNode('B')     const nodeC = new GraphNode('C')     const nodeD = new GraphNode('D')     const nodeE = new GraphNode('E')     const nodeF = new GraphNode('F')     const nodeG = new GraphNode('G')     const nodeH = new GraphNode('H')      const edgeAB = new GraphEdge(nodeA, nodeB)     const edgeBC = new GraphEdge(nodeB, nodeC)     const edgeAC = new GraphEdge(nodeA, nodeC)     const edgeCD = new GraphEdge(nodeC, nodeD)     const edgeDE = new GraphEdge(nodeD, nodeE)     const edgeEG = new GraphEdge(nodeE, nodeG)     const edgeEF = new GraphEdge(nodeE, nodeF)     const edgeGF = new GraphEdge(nodeG, nodeF)     const edgeFH = new GraphEdge(nodeF, nodeH)      const graph = new Graph()      graph       .addEdge(edgeAB)       .addEdge(edgeBC)       .addEdge(edgeAC)       .addEdge(edgeCD)       .addEdge(edgeDE)       .addEdge(edgeEG)       .addEdge(edgeEF)       .addEdge(edgeGF)       .addEdge(edgeFH)      const bridges = Object.values(graphBridges(graph))      expect(bridges.length).toBe(3)     expect(bridges[0].getKey()).toBe(edgeFH.getKey())     expect(bridges[1].getKey()).toBe(edgeDE.getKey())     expect(bridges[2].getKey()).toBe(edgeCD.getKey())   })    it('\u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0439\u0442\u0438 \u043c\u043e\u0441\u0442\u044b \u0432 \u0433\u0440\u0430\u0444\u0435 \u0441 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u043c\u0438 \u043a\u043e\u0440\u043d\u0435\u0432\u044b\u043c\u0438 \u0443\u0437\u043b\u0430\u043c\u0438', () =&gt; {     const nodeA = new GraphNode('A')     const nodeB = new GraphNode('B')     const nodeC = new GraphNode('C')     const nodeD = new GraphNode('D')     const nodeE = new GraphNode('E')     const nodeF = new GraphNode('F')     const nodeG = new GraphNode('G')     const nodeH = new GraphNode('H')      const edgeAB = new GraphEdge(nodeA, nodeB)     const edgeBC = new GraphEdge(nodeB, nodeC)     const edgeAC = new GraphEdge(nodeA, nodeC)     const edgeCD = new GraphEdge(nodeC, nodeD)     const edgeDE = new GraphEdge(nodeD, nodeE)     const edgeEG = new GraphEdge(nodeE, nodeG)     const edgeEF = new GraphEdge(nodeE, nodeF)     const edgeGF = new GraphEdge(nodeG, nodeF)     const edgeFH = new GraphEdge(nodeF, nodeH)      const graph = new Graph()      graph       .addEdge(edgeDE)       .addEdge(edgeAB)       .addEdge(edgeBC)       .addEdge(edgeAC)       .addEdge(edgeCD)       .addEdge(edgeEG)       .addEdge(edgeEF)       .addEdge(edgeGF)       .addEdge(edgeFH)      const bridges = Object.values(graphBridges(graph))      expect(bridges.length).toBe(3)     expect(bridges[0].getKey()).toBe(edgeFH.getKey())     expect(bridges[1].getKey()).toBe(edgeDE.getKey())     expect(bridges[2].getKey()).toBe(edgeCD.getKey())   })    it('\u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0439\u0442\u0438 \u043c\u043e\u0441\u0442\u044b \u0435\u0449\u0435 \u0432 \u043e\u0434\u043d\u043e\u043c \u0433\u0440\u0430\u0444\u0435 #1', () =&gt; {     const nodeA = new GraphNode('A')     const nodeB = new GraphNode('B')     const nodeC = new GraphNode('C')     const nodeD = new GraphNode('D')     const nodeE = new GraphNode('E')      const edgeAB = new GraphEdge(nodeA, nodeB)     const edgeAC = new GraphEdge(nodeA, nodeC)     const edgeBC = new GraphEdge(nodeB, nodeC)     const edgeCD = new GraphEdge(nodeC, nodeD)     const edgeDE = new GraphEdge(nodeD, nodeE)      const graph = new Graph()      graph       .addEdge(edgeAB)       .addEdge(edgeAC)       .addEdge(edgeBC)       .addEdge(edgeCD)       .addEdge(edgeDE)      const bridges = Object.values(graphBridges(graph))      expect(bridges.length).toBe(2)     expect(bridges[0].getKey()).toBe(edgeDE.getKey())     expect(bridges[1].getKey()).toBe(edgeCD.getKey())   })    it('\u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0439\u0442\u0438 \u043c\u043e\u0441\u0442\u044b \u0435\u0449\u0435 \u0432 \u043e\u0434\u043d\u043e\u043c \u0433\u0440\u0430\u0444\u0435 #2', () =&gt; {     const nodeA = new GraphNode('A')     const nodeB = new GraphNode('B')     const nodeC = new GraphNode('C')     const nodeD = new GraphNode('D')     const nodeE = new GraphNode('E')     const nodeF = new GraphNode('F')     const nodeG = new GraphNode('G')      const edgeAB = new GraphEdge(nodeA, nodeB)     const edgeAC = new GraphEdge(nodeA, nodeC)     const edgeBC = new GraphEdge(nodeB, nodeC)     const edgeCD = new GraphEdge(nodeC, nodeD)     const edgeCE = new GraphEdge(nodeC, nodeE)     const edgeCF = new GraphEdge(nodeC, nodeF)     const edgeEG = new GraphEdge(nodeE, nodeG)     const edgeFG = new GraphEdge(nodeF, nodeG)      const graph = new Graph()      graph       .addEdge(edgeAB)       .addEdge(edgeAC)       .addEdge(edgeBC)       .addEdge(edgeCD)       .addEdge(edgeCE)       .addEdge(edgeCF)       .addEdge(edgeEG)       .addEdge(edgeFG)      const bridges = Object.values(graphBridges(graph))      expect(bridges.length).toBe(1)     expect(bridges[0].getKey()).toBe(edgeCD.getKey())   }) })<\/code><\/pre>\n<\/div><\/div>\n<p> <\/p>\n<p>\u0417\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u0442\u0435\u0441\u0442\u044b:<\/p>\n<p> <\/p>\n<pre><code class=\"bash\">npm run test .\/algorithms\/graphs\/__tests__\/bridges<\/code><\/pre>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/q4\/ow\/at\/q4owat0jtlaztqphkl4vdzsweak.png\" data-src=\"https:\/\/habrastorage.org\/webt\/q4\/ow\/at\/q4owat0jtlaztqphkl4vdzsweak.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<h2 id=\"-komponenta-silnoy-svyaznosti\">\u276f \u041a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u0430 \u0441\u0438\u043b\u044c\u043d\u043e\u0439 \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u0438<\/h2>\n<p> <\/p>\n<p><strong>\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435<\/strong><\/p>\n<p> <\/p>\n<ul>\n<li><a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%9A%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82%D0%B0_%D1%81%D0%B8%D0%BB%D1%8C%D0%BD%D0%BE%D0%B9_%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%BE%D1%81%D1%82%D0%B8\">\u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u044f<\/a><\/li>\n<li><a href=\"https:\/\/www.youtube.com\/watch?v=RpgcYiky7uw&amp;list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8\">YouTube<\/a><\/li>\n<li><a href=\"https:\/\/www.youtube.com\/watch?v=rZkauRhHKGo\">YouTube<\/a><\/li>\n<\/ul>\n<p> <\/p>\n<p>\u041e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u0433\u0440\u0430\u0444 \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f <em>\u0441\u0438\u043b\u044c\u043d\u043e \u0441\u0432\u044f\u0437\u043d\u044b\u043c\/\u0441\u0432\u044f\u0437\u0430\u043d\u043d\u044b\u043c<\/em> (strongly connected), \u0435\u0441\u043b\u0438 \u043b\u044e\u0431\u044b\u0435 \u0434\u0432\u0435 \u0435\u0433\u043e \u0432\u0435\u0440\u0448\u0438\u043d\u044b <code>s<\/code> \u0438 <code>t<\/code> \u0441\u0438\u043b\u044c\u043d\u043e \u0441\u0432\u044f\u0437\u0430\u043d\u044b, \u0442\u043e \u0435\u0441\u0442\u044c \u0435\u0441\u043b\u0438 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043f\u0443\u0442\u044c \u0438\u0437 <code>s<\/code> \u0432 <code>t<\/code> \u0438 \u043e\u0434\u043d\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e \u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043f\u0443\u0442\u044c \u0438\u0437 <code>t<\/code> \u0432 <code>s<\/code>.<\/p>\n<p> <\/p>\n<p><em>\u041a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u0430\u043c\u0438 \u0441\u0438\u043b\u044c\u043d\u043e\u0439 \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u0438<\/em> \u0433\u0440\u0430\u0444\u0430 \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442\u0441\u044f \u0435\u0433\u043e \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0435 \u043f\u043e \u0432\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u044e \u0441\u0438\u043b\u044c\u043d\u043e \u0441\u0432\u044f\u0437\u043d\u044b\u0435 \u043f\u043e\u0434\u0433\u0440\u0430\u0444\u044b. <em>\u041e\u0431\u043b\u0430\u0441\u0442\u044c\u044e \u0441\u0438\u043b\u044c\u043d\u043e\u0439 \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u0438<\/em> \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0432\u0435\u0440\u0448\u0438\u043d \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u043e\u0432 \u0441\u0438\u043b\u044c\u043d\u043e\u0439 \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u0438.<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/6y\/yk\/je\/6yykjevnhy08shelpkczcgff2ye.png\" data-src=\"https:\/\/habrastorage.org\/webt\/6y\/yk\/je\/6yykjevnhy08shelpkczcgff2ye.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<p>\u041d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0439 \u0433\u0440\u0430\u0444, \u043d\u0435 \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0430\u0449\u0438\u0439 \u043a \u043a\u043b\u0430\u0441\u0441\u0443 \u0441\u0438\u043b\u044c\u043d\u043e \u0441\u0432\u044f\u0437\u043d\u044b\u0445 \u0433\u0440\u0430\u0444\u043e\u0432, \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0430\u0431\u043e\u0440 \u0441\u0438\u043b\u044c\u043d\u043e \u0441\u0432\u044f\u0437\u043d\u044b\u0445 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442, \u0438 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0430\u0431\u043e\u0440 \u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0440\u0435\u0431\u0435\u0440, \u0438\u0434\u0443\u0449\u0438\u0445 \u043e\u0442 \u043e\u0434\u043d\u043e\u0439 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u044b \u043a \u0434\u0440\u0443\u0433\u043e\u0439.<\/p>\n<p> <\/p>\n<p>\u041b\u044e\u0431\u0430\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u0433\u0440\u0430\u0444\u0430 \u0441\u0438\u043b\u044c\u043d\u043e \u0441\u0432\u044f\u0437\u0430\u043d\u0430 \u0441\u0430\u043c\u0430 \u0441 \u0441\u043e\u0431\u043e\u0439.<\/p>\n<p> <\/p>\n<p><em>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b<\/em><\/p>\n<p> <\/p>\n<p>\u041f\u0440\u043e\u0441\u0442\u0435\u0439\u0448\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u043e \u043f\u043e\u0438\u0441\u043a\u0435 \u0441\u0438\u043b\u044c\u043d\u043e \u0441\u0432\u044f\u0437\u043d\u044b\u0445 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442 \u0432 \u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u043c \u0433\u0440\u0430\u0444\u0435 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c:<\/p>\n<p> <\/p>\n<ol>\n<li>\u041f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%A2%D1%80%D0%B0%D0%BD%D0%B7%D0%B8%D1%82%D0%B8%D0%B2%D0%BD%D0%BE%D0%B5_%D0%B7%D0%B0%D0%BC%D1%8B%D0%BA%D0%B0%D0%BD%D0%B8%D0%B5\">\u0442\u0440\u0430\u043d\u0437\u0438\u0442\u0438\u0432\u043d\u043e\u0433\u043e \u0437\u0430\u043c\u044b\u043a\u0430\u043d\u0438\u044f<\/a> \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c, \u0434\u043e\u0441\u0442\u0438\u0436\u0438\u043c\u0430 \u043b\u0438 <code>t<\/code> \u0438\u0437 <code>s<\/code>, \u0438 <code>s<\/code> \u0438\u0437 <code>t<\/code>, \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u043f\u0430\u0440 <code>s<\/code> \u0438 <code>t<\/code>.<\/li>\n<li>\u0417\u0430\u0442\u0435\u043c \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u043c \u0442\u0430\u043a\u043e\u0439 \u043d\u0435\u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u0433\u0440\u0430\u0444, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 \u0442\u0430\u043a\u043e\u0439 \u043f\u0430\u0440\u044b \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442\u0441\u044f \u0440\u0435\u0431\u0440\u043e.<\/li>\n<li>\u041f\u043e\u0438\u0441\u043a \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442 \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u0438 \u0442\u0430\u043a\u043e\u0433\u043e \u043d\u0435\u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0433\u043e \u0433\u0440\u0430\u0444\u0430 \u0434\u0430\u0435\u0442 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u044b \u0441\u0438\u043b\u044c\u043d\u043e\u0439 \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u0438.<\/li>\n<\/ol>\n<p> <\/p>\n<p>\u041e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0434\u0430\u043d\u043d\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 \u0442\u0440\u0430\u043d\u0437\u0438\u0442\u0438\u0432\u043d\u043e\u0435 \u0437\u0430\u043c\u044b\u043a\u0430\u043d\u0438\u0435.<\/p>\n<p> <\/p>\n<p>\u0422\u0430\u043a\u0436\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0442\u0440\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u0440\u0435\u0448\u0430\u044e\u0449\u0438\u0445 \u0434\u0430\u043d\u043d\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443 \u0437\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f. \u042d\u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%BE%D1%81%D0%B0%D1%80%D0%B0%D0%B9%D1%8E\">\u041a\u043e\u0441\u0430\u0440\u0430\u0439\u044e<\/a>, <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82_%D1%81%D0%B8%D0%BB%D1%8C%D0%BD%D0%BE%D0%B9_%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%81_%D0%B4%D0%B2%D1%83%D0%BC%D1%8F_%D1%81%D1%82%D0%B5%D0%BA%D0%B0%D0%BC%D0%B8\">\u043f\u043e\u0438\u0441\u043a\u0430 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442 \u0441\u0438\u043b\u044c\u043d\u043e\u0439 \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u0438 \u0441 \u0434\u0432\u0443\u043c\u044f \u0441\u0442\u0435\u043a\u0430\u043c\u0438<\/a> \u0438 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A2%D0%B0%D1%80%D1%8C%D1%8F%D0%BD%D0%B0\">\u0422\u0430\u0440\u044c\u044f\u043d\u0430<\/a>.<\/p>\n<p> <\/p>\n<p><strong>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/strong><\/p>\n<p> <\/p>\n<p>\u0412 \u043d\u0430\u0448\u0435\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0431\u0443\u0434\u0435\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0442\u0430\u043a\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043a\u0430\u043a <a href=\"https:\/\/habr.com\/ru\/companies\/timeweb\/articles\/896800\/\">\u043f\u043e\u0438\u0441\u043a \u0432 \u0433\u043b\u0443\u0431\u0438\u043d\u0443<\/a>, \u0438 \u0442\u0430\u043a\u0430\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u0430\u043a <a href=\"https:\/\/habr.com\/ru\/companies\/timeweb\/articles\/826424\/\">\u0441\u0442\u0435\u043a<\/a>:<\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ algorithms\/graphs\/strongly-connected-components.js import Stack from '..\/..\/data-structures\/stack' import depthFirstSearch from '.\/depth-first-search'  \/\/ \u0424\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u0433\u0440\u0430\u0444. \/\/ \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0441\u0442\u0435\u043a \u0443\u0437\u043b\u043e\u0432, \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u044b\u0445 \u043f\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f function getNodesSortedByDfsFinishTime(graph) {   \/\/ \u0421\u043f\u0438\u0441\u043e\u043a \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432   const visited = {}    \/\/ \u0421\u0442\u0435\u043a \u0443\u0437\u043b\u043e\u0432 \u043f\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f (\u0438\u0437\u043c\u0435\u0440\u044f\u0435\u0442\u0441\u044f \u0432 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0435 \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u0438\u0439 \u0443\u0437\u043b\u043e\u0432).   \/\/ \u0412\u0441\u0435 \u0443\u0437\u043b\u044b \u0432 \u044d\u0442\u043e\u043c \u0441\u0442\u0435\u043a\u0435 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u043f\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f \u0432 \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u0443\u0431\u044b\u0432\u0430\u043d\u0438\u044f.   \/\/ \u0423\u0437\u0435\u043b, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u044b\u043b \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d \u043f\u0435\u0440\u0432\u044b\u043c, \u0431\u0443\u0434\u0435\u0442 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c\u0441\u044f \u0432\u043d\u0438\u0437\u0443 \u0441\u0442\u0435\u043a\u0430, \u0430   \/\/ \u0443\u0437\u0435\u043b, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u044b\u043b \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u043c, \u0431\u0443\u0434\u0435\u0442 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c\u0441\u044f \u043d\u0430\u0432\u0435\u0440\u0445\u0443 \u0441\u0442\u0435\u043a\u0430   const stack = new Stack()    \/\/ \u0421\u043f\u0438\u0441\u043e\u043a \u043d\u0435\u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432   const unvisited = graph.getAllNodes().reduce((a, c) =&gt; {     a[c.getKey()] = c     return a   }, {})    \/\/ \u041e\u0431\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a\u0438 \u0434\u043b\u044f DFS   const callbacks = {     \/\/ \u041e\u0431\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a \u0432\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u0432 \u0443\u0437\u0435\u043b     enterNode: ({ currentNode }) =&gt; {       \/\/ \u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0443\u0437\u0435\u043b \u0432 \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0435       visited[currentNode.getKey()] = currentNode       \/\/ \u0423\u0434\u0430\u043b\u044f\u0435\u043c \u0443\u0437\u0435\u043b \u0438\u0437 \u043d\u0435\u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0445       delete unvisited[currentNode.getKey()]     },     \/\/ \u041e\u0431\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a \u0432\u044b\u0445\u043e\u0434\u0430 \u0438\u0437 \u0443\u0437\u043b\u0430     leaveNode: ({ currentNode }) =&gt; {       \/\/ \u041f\u043e\u043c\u0435\u0449\u0430\u0435\u043c \u043f\u043e\u043b\u043d\u043e\u0441\u0442\u044c\u044e \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u0443\u0437\u0435\u043b \u0432 \u0441\u0442\u0435\u043a       stack.push(currentNode)     },     \/\/ \u041e\u0431\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0431\u0445\u043e\u0434\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e \u0443\u0437\u043b\u0430     allowTraverse: ({ nextNode }) =&gt; {       \/\/ \u0417\u0430\u043f\u0440\u0435\u0449\u0430\u0435\u043c \u043e\u0431\u0445\u043e\u0434 \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432       return !visited[nextNode.getKey()]     },   }    \/\/ \u041f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0435\u043c \u043d\u0435\u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0435 \u0443\u0437\u043b\u044b \u0438 \u043e\u0431\u0445\u043e\u0434\u0438\u043c \u0438\u0445 \u0432 \u0433\u043b\u0443\u0431\u0438\u043d\u0443   while (Object.keys(unvisited).length) {     const startKey = Object.keys(unvisited)[0]     const startNode = unvisited[startKey]     delete unvisited[startKey]      depthFirstSearch(graph, startNode, callbacks)   }    return stack }  \/\/ \u0424\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u0433\u0440\u0430\u0444 \u0438 \u0441\u0442\u0435\u043a \u0443\u0437\u043b\u043e\u0432, \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u044b\u0445 \u043f\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f. \/\/ \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u043d\u0430\u0431\u043e\u0440\u044b \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442 \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u0438 function getSCCSets(graph, stack) {   \/\/ \u041d\u0430\u0431\u043e\u0440\u044b \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442 \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u0438   const sets = []   \/\/ \u0422\u0435\u043a\u0443\u0449\u0438\u0439 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442 \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u0438   let set = []   \/\/ \u0421\u043f\u0438\u0441\u043e\u043a \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432   const visited = {}    \/\/ \u041e\u0431\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a\u0438 \u0434\u043b\u044f DFS   const callbacks = {     \/\/ \u041e\u0431\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a \u0432\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u0432 \u0443\u0437\u0435\u043b     enterNode: ({ currentNode }) =&gt; {       \/\/ \u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0443\u0437\u0435\u043b \u0432 \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442 \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u0438       set.push(currentNode)       \/\/ \u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0443\u0437\u0435\u043b \u0432 \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0435       visited[currentNode.getKey()] = currentNode     },     \/\/ \u041e\u0431\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a \u0432\u044b\u0445\u043e\u0434\u0430 \u0438\u0437 \u0443\u0437\u043b\u0430     leaveNode: ({ previousNode }) =&gt; {       \/\/ \u0415\u0441\u043b\u0438 \u0443\u0437\u0435\u043b \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u043e\u0440\u043d\u0435\u0432\u044b\u043c, \u0437\u043d\u0430\u0447\u0438\u0442, \u043c\u044b \u043d\u0430\u0448\u043b\u0438 \u043d\u043e\u0432\u044b\u0439 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442 \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u0438       if (!previousNode) {         \/\/ \u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442 \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u0438 \u0432 \u043d\u0430\u0431\u043e\u0440\u044b         sets.push(set.slice())       }     },     \/\/ \u041e\u0431\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0431\u0445\u043e\u0434\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e \u0443\u0437\u043b\u0430     allowTraverse: ({ nextNode }) =&gt; {       \/\/ \u0417\u0430\u043f\u0440\u0435\u0449\u0430\u0435\u043c \u043e\u0431\u0445\u043e\u0434 \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432       return !visited[nextNode.getKey()]     },   }    \/\/ \u041f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0435\u043c \u0441\u0442\u0435\u043a \u0443\u0437\u043b\u043e\u0432 \u0438 \u043e\u0431\u0445\u043e\u0434\u0438\u043c \u0438\u0445 \u0432 \u0433\u043b\u0443\u0431\u0438\u043d\u0443   while (!stack.isEmpty()) {     const node = stack.pop()      set = []      if (!visited[node.getKey()]) {       depthFirstSearch(graph, node, callbacks)     }   }    return sets }  \/\/ \u0424\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u0433\u0440\u0430\u0444 export default function stronglyConnectedComponents(graph) {   \/\/ \u041f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0441\u0442\u0435\u043a \u0443\u0437\u043b\u043e\u0432, \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u044b\u0445 \u043f\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f   const stack = getNodesSortedByDfsFinishTime(graph)   \/\/ \u0418\u043d\u0432\u0435\u0440\u0442\u0438\u0440\u0443\u0435\u043c \u0433\u0440\u0430\u0444   graph.reverse()   \/\/ \u041f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0438 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c \u043d\u0430\u0431\u043e\u0440\u044b \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442 \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u0438   return getSCCSets(graph, stack) }<\/code><\/pre>\n<p> <\/p>\n<div class=\"spoiler\" role=\"button\" tabindex=\"0\">                         <b class=\"spoiler_title\">\u0422\u0435\u0441\u0442\u044b:<\/b>                         <\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"javascript\">\/\/ algorithms\/graphs\/__tests__\/strongly-connected-components.test.js import GraphEdge from '..\/..\/..\/data-structures\/graph\/edge' import Graph from '..\/..\/..\/data-structures\/graph\/index' import GraphNode from '..\/..\/..\/data-structures\/graph\/node' import stronglyConnectedComponents from '..\/strongly-connected-components'  describe('stronglyConnectedComponents', () =&gt; {   it('\u0434\u043e\u043b\u0436\u0435\u043d \u043e\u0431\u043d\u0430\u0440\u0443\u0436\u0438\u0442\u044c \u0441\u0438\u043b\u044c\u043d\u043e \u0441\u0432\u044f\u0437\u0430\u043d\u043d\u044b\u0435 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u044b \u0432 \u043f\u0440\u043e\u0441\u0442\u043e\u043c \u0433\u0440\u0430\u0444\u0435', () =&gt; {     const nodeA = new GraphNode('A')     const nodeB = new GraphNode('B')     const nodeC = new GraphNode('C')     const nodeD = new GraphNode('D')      const edgeAB = new GraphEdge(nodeA, nodeB)     const edgeBC = new GraphEdge(nodeB, nodeC)     const edgeCA = new GraphEdge(nodeC, nodeA)     const edgeCD = new GraphEdge(nodeC, nodeD)      const graph = new Graph(true)      graph.addEdge(edgeAB).addEdge(edgeBC).addEdge(edgeCA).addEdge(edgeCD)      const components = stronglyConnectedComponents(graph)      expect(components).toBeDefined()     expect(components.length).toBe(2)      expect(components[0][0].getKey()).toBe(nodeA.getKey())     expect(components[0][1].getKey()).toBe(nodeC.getKey())     expect(components[0][2].getKey()).toBe(nodeB.getKey())      expect(components[1][0].getKey()).toBe(nodeD.getKey())   })    it('\u0434\u043e\u043b\u0436\u0435\u043d \u043e\u0431\u043d\u0430\u0440\u0443\u0436\u0438\u0442\u044c \u0441\u0438\u043b\u044c\u043d\u043e \u0441\u0432\u044f\u0437\u0430\u043d\u043d\u044b\u0435 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u044b \u0432 \u0433\u0440\u0430\u0444\u0435', () =&gt; {     const nodeA = new GraphNode('A')     const nodeB = new GraphNode('B')     const nodeC = new GraphNode('C')     const nodeD = new GraphNode('D')     const nodeE = new GraphNode('E')     const nodeF = new GraphNode('F')     const nodeG = new GraphNode('G')     const nodeH = new GraphNode('H')     const nodeI = new GraphNode('I')     const nodeJ = new GraphNode('J')     const nodeK = new GraphNode('K')      const edgeAB = new GraphEdge(nodeA, nodeB)     const edgeBC = new GraphEdge(nodeB, nodeC)     const edgeCA = new GraphEdge(nodeC, nodeA)     const edgeBD = new GraphEdge(nodeB, nodeD)     const edgeDE = new GraphEdge(nodeD, nodeE)     const edgeEF = new GraphEdge(nodeE, nodeF)     const edgeFD = new GraphEdge(nodeF, nodeD)     const edgeGF = new GraphEdge(nodeG, nodeF)     const edgeGH = new GraphEdge(nodeG, nodeH)     const edgeHI = new GraphEdge(nodeH, nodeI)     const edgeIJ = new GraphEdge(nodeI, nodeJ)     const edgeJG = new GraphEdge(nodeJ, nodeG)     const edgeJK = new GraphEdge(nodeJ, nodeK)      const graph = new Graph(true)      graph       .addEdge(edgeAB)       .addEdge(edgeBC)       .addEdge(edgeCA)       .addEdge(edgeBD)       .addEdge(edgeDE)       .addEdge(edgeEF)       .addEdge(edgeFD)       .addEdge(edgeGF)       .addEdge(edgeGH)       .addEdge(edgeHI)       .addEdge(edgeIJ)       .addEdge(edgeJG)       .addEdge(edgeJK)      const components = stronglyConnectedComponents(graph)      expect(components).toBeDefined()     expect(components.length).toBe(4)      expect(components[0][0].getKey()).toBe(nodeG.getKey())     expect(components[0][1].getKey()).toBe(nodeJ.getKey())     expect(components[0][2].getKey()).toBe(nodeI.getKey())     expect(components[0][3].getKey()).toBe(nodeH.getKey())      expect(components[1][0].getKey()).toBe(nodeK.getKey())      expect(components[2][0].getKey()).toBe(nodeA.getKey())     expect(components[2][1].getKey()).toBe(nodeC.getKey())     expect(components[2][2].getKey()).toBe(nodeB.getKey())      expect(components[3][0].getKey()).toBe(nodeD.getKey())     expect(components[3][1].getKey()).toBe(nodeF.getKey())     expect(components[3][2].getKey()).toBe(nodeE.getKey())   }) })<\/code><\/pre>\n<\/div><\/div>\n<p> <\/p>\n<p>\u0417\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u0442\u0435\u0441\u0442\u044b:<\/p>\n<p> <\/p>\n<pre><code class=\"bash\">npm run test .\/algorithms\/graphs\/__tests__\/strongly-connected-components<\/code><\/pre>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/wa\/dp\/1w\/wadp1wkqiz7hkog1kr46djthxtw.png\" data-src=\"https:\/\/habrastorage.org\/webt\/wa\/dp\/1w\/wadp1wkqiz7hkog1kr46djthxtw.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<h2 id=\"zadacha-kommivoyazhera\">\u276f\u0417\u0430\u0434\u0430\u0447\u0430 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430<\/h2>\n<p> <\/p>\n<p><strong>\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435<\/strong><\/p>\n<p> <\/p>\n<ul>\n<li><a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D1%91%D1%80%D0%B0\">\u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u044f<\/a><\/li>\n<li><a href=\"https:\/\/www.youtube.com\/watch?v=r804FVgvaTo\">YouTube<\/a><\/li>\n<\/ul>\n<p> <\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430 (travelling salesman problem, TSP) \u2014 \u043e\u0434\u043d\u0430 \u0438\u0437 \u0441\u0430\u043c\u044b\u0445 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0445 \u0437\u0430\u0434\u0430\u0447 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%9A%D0%BE%D0%BC%D0%B1%D0%B8%D0%BD%D0%B0%D1%82%D0%BE%D1%80%D0%BD%D0%B0%D1%8F_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F\">\u043a\u043e\u043c\u0431\u0438\u043d\u0430\u0442\u043e\u0440\u043d\u043e\u0439 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438<\/a>, \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u044e\u0449\u0430\u044f\u0441\u044f \u0432 \u043f\u043e\u0438\u0441\u043a\u0435 \u0441\u0430\u043c\u043e\u0433\u043e \u0432\u044b\u0433\u043e\u0434\u043d\u043e\u0433\u043e \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430, \u043f\u0440\u043e\u0445\u043e\u0434\u044f\u0449\u0435\u0433\u043e \u0447\u0435\u0440\u0435\u0437 \u0443\u043a\u0430\u0437\u0430\u043d\u043d\u044b\u0435 \u0433\u043e\u0440\u043e\u0434\u0430 \u0440\u043e\u0432\u043d\u043e \u043f\u043e \u043e\u0434\u043d\u043e\u043c\u0443 \u0440\u0430\u0437\u0443 \u0441 \u043f\u043e\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u0432\u043e\u0437\u0432\u0440\u0430\u0442\u043e\u043c \u0432 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u0433\u043e\u0440\u043e\u0434. \u0412 \u0443\u0441\u043b\u043e\u0432\u0438\u044f\u0445 \u0437\u0430\u0434\u0430\u0447\u0438 \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0442\u0441\u044f \u043a\u0440\u0438\u0442\u0435\u0440\u0438\u0439 \u0432\u044b\u0433\u043e\u0434\u043d\u043e\u0441\u0442\u0438 \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430 (\u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439, \u0441\u0430\u043c\u044b\u0439 \u0434\u0435\u0448\u0435\u0432\u044b\u0439, \u0441\u043e\u0432\u043e\u043a\u0443\u043f\u043d\u044b\u0439 \u043a\u0440\u0438\u0442\u0435\u0440\u0438\u0439 \u0438 \u0442.\u043f.) \u0438 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0435 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439, \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u0438 \u0438 \u0442.\u0434. \u041a\u0430\u043a \u043f\u0440\u0430\u0432\u0438\u043b\u043e, \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u043c\u0430\u0440\u0448\u0440\u0443\u0442 \u0434\u043e\u043b\u0436\u0435\u043d \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u0442\u044c \u0447\u0435\u0440\u0435\u0437 \u043a\u0430\u0436\u0434\u044b\u0439 \u0433\u043e\u0440\u043e\u0434 \u0442\u043e\u043b\u044c\u043a\u043e \u043e\u0434\u0438\u043d \u0440\u0430\u0437 \u2014 \u0432 \u0442\u0430\u043a\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0432\u044b\u0431\u043e\u0440 \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u0440\u0435\u0434\u0438 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%93%D0%B0%D0%BC%D0%B8%D0%BB%D1%8C%D1%82%D0%BE%D0%BD%D0%BE%D0%B2_%D1%86%D0%B8%D0%BA%D0%BB\">\u0433\u0430\u043c\u0438\u043b\u044c\u0442\u043e\u043d\u043e\u0432\u044b\u0445 \u0446\u0438\u043a\u043b\u043e\u0432<\/a>. \u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0447\u0430\u0441\u0442\u043d\u044b\u0445 \u0441\u043b\u0443\u0447\u0430\u0435\u0432 \u043e\u0431\u0449\u0435\u0439 \u043f\u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0438 \u0437\u0430\u0434\u0430\u0447\u0438, \u0432 \u0447\u0430\u0441\u0442\u043d\u043e\u0441\u0442\u0438, \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430 (\u0442\u0430\u043a\u0436\u0435 \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u0430\u044f \u043f\u043b\u0430\u043d\u0430\u0440\u043d\u043e\u0439 \u0438\u043b\u0438 \u0435\u0432\u043a\u043b\u0438\u0434\u043e\u0432\u043e\u0439, \u043a\u043e\u0433\u0434\u0430 \u043c\u0430\u0442\u0440\u0438\u0446\u0430 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u043e\u0442\u0440\u0430\u0436\u0430\u0435\u0442 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u043c\u0435\u0436\u0434\u0443 \u0442\u043e\u0447\u043a\u0430\u043c\u0438 \u043d\u0430 \u043f\u043b\u043e\u0441\u043a\u043e\u0441\u0442\u0438), \u043c\u0435\u0442\u0440\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430 (\u043a\u043e\u0433\u0434\u0430 \u043d\u0430 \u043c\u0430\u0442\u0440\u0438\u0446\u0435 \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u0435\u0439 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u043d\u0435\u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u043e \u0442\u0440\u0435\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u0430), \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u0430\u044f \u0438 \u0430\u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430. \u0422\u0430\u043a\u0436\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043e\u0431\u043e\u0431\u0449\u0435\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438, \u0442\u0430\u043a \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u0430\u044f <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%9E%D0%B1%D0%BE%D0%B1%D1%89%D1%91%D0%BD%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D1%91%D1%80%D0%B0\">\u043e\u0431\u043e\u0431\u0449\u0435\u043d\u043d\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430<\/a>.<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/za\/hw\/m0\/zahwm0vfhmbadqqzkhjrlnefpyu.png\" data-src=\"https:\/\/habrastorage.org\/webt\/za\/hw\/m0\/zahwm0vfhmbadqqzkhjrlnefpyu.png\"\/> <\/p>\n<p><em>\u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430: \u0447\u0435\u0440\u043d\u0430\u044f \u043b\u0438\u043d\u0438\u044f \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u043d\u0430\u0438\u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0439 \u0446\u0438\u043a\u043b, \u0441\u043e\u0435\u0434\u0438\u043d\u044f\u044e\u0449\u0438\u0439 \u0432\u0441\u0435 \u043a\u0440\u0430\u0441\u043d\u044b\u0435 \u0442\u043e\u0447\u043a\u0438<\/em><\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/mi\/1f\/ia\/mi1fiajfszm-yczg3yg47xoanii.png\" data-src=\"https:\/\/habrastorage.org\/webt\/mi\/1f\/ia\/mi1fiajfszm-yczg3yg47xoanii.png\"\/> <\/p>\n<p><em>\u041e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043c\u0430\u0440\u0448\u0440\u0443\u0442 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430 \u0447\u0435\u0440\u0435\u0437 14 \u043a\u0440\u0443\u043f\u043d\u0435\u0439\u0448\u0438\u0445 \u0433\u043e\u0440\u043e\u0434\u043e\u0432 \u0413\u0435\u0440\u043c\u0430\u043d\u0438\u0438. \u0423\u043a\u0430\u0437\u0430\u043d\u043d\u044b\u0439 \u043c\u0430\u0440\u0448\u0440\u0443\u0442 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u0430\u043c\u044b\u043c \u043a\u043e\u0440\u043e\u0442\u043a\u0438\u043c \u0438\u0437 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 43 589 145 600 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432<\/em><\/p>\n<p> <\/p>\n<p>\u041e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u043e\u043d\u043d\u0430\u044f \u043f\u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0430 \u0437\u0430\u0434\u0430\u0447\u0438 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0441\u044f \u043a \u043a\u043b\u0430\u0441\u0441\u0443 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/NP-%D1%82%D1%80%D1%83%D0%B4%D0%BD%D0%BE%D1%81%D1%82%D1%8C\">NP-\u0442\u0440\u0443\u0434\u043d\u044b\u0445<\/a> \u0437\u0430\u0434\u0430\u0447, \u0432\u043f\u0440\u043e\u0447\u0435\u043c, \u043a\u0430\u043a \u0438 \u0431\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u043e \u0435\u0435 \u0447\u0430\u0441\u0442\u043d\u044b\u0445 \u0441\u043b\u0443\u0447\u0430\u0435\u0432. \u0412\u0435\u0440\u0441\u0438\u044f &#171;decision problem&#187; (\u0442\u043e \u0435\u0441\u0442\u044c \u0442\u0430\u043a\u0430\u044f, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0441\u0442\u0430\u0432\u0438\u0442\u0441\u044f \u0432\u043e\u043f\u0440\u043e\u0441, \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043b\u0438 \u043c\u0430\u0440\u0448\u0440\u0443\u0442 \u043d\u0435 \u0434\u043b\u0438\u043d\u043d\u0435\u0435, \u0447\u0435\u043c \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 <code>k<\/code>) \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0441\u044f \u043a \u043a\u043b\u0430\u0441\u0441\u0443 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0\">NP-\u043f\u043e\u043b\u043d\u044b\u0445 \u0437\u0430\u0434\u0430\u0447<\/a>. \u0417\u0430\u0434\u0430\u0447\u0430 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0441\u044f \u043a \u0447\u0438\u0441\u043b\u0443 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%A2%D1%80%D0%B0%D0%BD%D1%81%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0\">\u0442\u0440\u0430\u043d\u0441\u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445<\/a>: \u0443\u0436\u0435 \u043f\u0440\u0438 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u043e\u043c \u0447\u0438\u0441\u043b\u0435 \u0433\u043e\u0440\u043e\u0434\u043e\u0432 (&gt; 66) \u043e\u043d\u0430 \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0440\u0435\u0448\u0435\u043d\u0430 \u043c\u0435\u0442\u043e\u0434\u043e\u043c \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432 \u043d\u0438\u043a\u0430\u043a\u0438\u043c\u0438 \u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u043c\u044b\u0441\u043b\u0438\u043c\u044b\u043c\u0438 \u043a\u043e\u043c\u043f\u044c\u044e\u0442\u0435\u0440\u0430\u043c\u0438 \u0437\u0430 \u0432\u0440\u0435\u043c\u044f, \u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u0445 \u043c\u0438\u043b\u043b\u0438\u0430\u0440\u0434\u043e\u0432 \u043b\u0435\u0442.<\/p>\n<p> <\/p>\n<p><em>\u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0432 \u0432\u0438\u0434\u0435 \u0433\u0440\u0430\u0444\u0430<\/em><\/p>\n<p> <\/p>\n<p>\u0414\u043b\u044f \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044f \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0430\u043f\u043f\u0430\u0440\u0430\u0442\u0430 \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u0435\u0435 \u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0432 \u0432\u0438\u0434\u0435 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043c\u043e\u0434\u0435\u043b\u0438. \u0417\u0430\u0434\u0430\u0447\u0443 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0432 \u0432\u0438\u0434\u0435 \u043c\u043e\u0434\u0435\u043b\u0438 \u043d\u0430 \u0433\u0440\u0430\u0444\u0435, \u0442\u043e \u0435\u0441\u0442\u044c, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0438 \u0440\u0435\u0431\u0440\u0430 \u043c\u0435\u0436\u0434\u0443 \u043d\u0438\u043c\u0438. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0433\u0440\u0430\u0444\u0430 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0442 \u0433\u043e\u0440\u043e\u0434\u0430\u043c, \u0430 \u0440\u0435\u0431\u0440\u0430 <code>(i, j)<\/code> \u043c\u0435\u0436\u0434\u0443 \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u043c\u0438 <code>i<\/code> \u0438 <code>j<\/code> \u2014 \u043f\u0443\u0442\u0438 \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u044f \u043c\u0435\u0436\u0434\u0443 \u044d\u0442\u0438\u043c\u0438 \u0433\u043e\u0440\u043e\u0434\u0430\u043c\u0438. \u041a\u0430\u0436\u0434\u043e\u043c\u0443 \u0440\u0435\u0431\u0440\u0443 <code>(i, j)<\/code> \u043c\u043e\u0436\u043d\u043e \u0441\u043e\u043f\u043e\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043a\u0440\u0438\u0442\u0435\u0440\u0438\u0439 \u0432\u044b\u0433\u043e\u0434\u043d\u043e\u0441\u0442\u0438 \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430 c<sub>ij<\/sub> &gt;= 0, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043d\u0438\u043c\u0430\u0442\u044c \u043a\u0430\u043a, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043c\u0435\u0436\u0434\u0443 \u0433\u043e\u0440\u043e\u0434\u0430\u043c\u0438, \u0432\u0440\u0435\u043c\u044f \u0438\u043b\u0438 \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u043f\u043e\u0435\u0437\u0434\u043a\u0438.<\/p>\n<p> <\/p>\n<p>\u0413\u0430\u043c\u0438\u043b\u044c\u0442\u043e\u043d\u043e\u0432\u044b\u043c \u0446\u0438\u043a\u043b\u043e\u043c \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043c\u0430\u0440\u0448\u0440\u0443\u0442, \u0432\u043a\u043b\u044e\u0447\u0430\u044e\u0449\u0438\u0439 \u0440\u043e\u0432\u043d\u043e \u043f\u043e \u043e\u0434\u043d\u043e\u043c\u0443 \u0440\u0430\u0437\u0443 \u043a\u0430\u0436\u0434\u0443\u044e \u0432\u0435\u0440\u0448\u0438\u043d\u0443 \u0433\u0440\u0430\u0444\u0430.<\/p>\n<p> <\/p>\n<p>\u0412 \u0446\u0435\u043b\u044f\u0445 \u0443\u043f\u0440\u043e\u0449\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u0438 \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0438 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043e\u0432\u0430\u043d\u0438\u044f \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430 \u043e\u0431\u044b\u0447\u043d\u043e \u0441\u0447\u0438\u0442\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u043c\u043e\u0434\u0435\u043b\u044c\u043d\u044b\u0439 \u0433\u0440\u0430\u0444 \u0437\u0430\u0434\u0430\u0447\u0438 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e\u043b\u043d\u043e\u0441\u0442\u044c\u044e \u0441\u0432\u044f\u0437\u043d\u044b\u043c, \u0442\u043e \u0435\u0441\u0442\u044c, \u0447\u0442\u043e \u043c\u0435\u0436\u0434\u0443 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u043e\u0439 \u043f\u0430\u0440\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0440\u0435\u0431\u0440\u043e. \u0412 \u0442\u0435\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445, \u043a\u043e\u0433\u0434\u0430 \u043c\u0435\u0436\u0434\u0443 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u043c\u0438 \u0433\u043e\u0440\u043e\u0434\u0430\u043c\u0438 \u043d\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u044f, \u044d\u0442\u043e\u0433\u043e \u043c\u043e\u0436\u043d\u043e \u0434\u043e\u0441\u0442\u0438\u0447\u044c \u043f\u0443\u0442\u0435\u043c \u0432\u0432\u043e\u0434\u0430 \u0440\u0435\u0431\u0435\u0440 \u0441 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u043e\u0439. \u0418\u0437-\u0437\u0430 \u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u0434\u043b\u0438\u043d\u044b \u0442\u0430\u043a\u043e\u0435 \u0440\u0435\u0431\u0440\u043e \u043d\u0438\u043a\u043e\u0433\u0434\u0430 \u043d\u0435 \u043f\u043e\u043f\u0430\u0434\u0435\u0442 \u0432 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043c\u0430\u0440\u0448\u0440\u0443\u0442, \u0435\u0441\u043b\u0438 \u043e\u043d \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442.<\/p>\n<p> <\/p>\n<p>\u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430 \u2014 \u044d\u0442\u043e \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u0433\u0430\u043c\u0438\u043b\u044c\u0442\u043e\u043d\u043e\u0432\u0430 \u0446\u0438\u043a\u043b\u0430 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0432\u0435\u0441\u0430 \u0432 \u043f\u043e\u043b\u043d\u043e\u043c \u0432\u0437\u0432\u0435\u0448\u0435\u043d\u043d\u043e\u043c \u0433\u0440\u0430\u0444\u0435.<\/p>\n<p> <\/p>\n<p>\u0412 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u0442\u043e\u0433\u043e, \u043a\u0430\u043a\u043e\u0439 \u043a\u0440\u0438\u0442\u0435\u0440\u0438\u0439 \u0432\u044b\u0433\u043e\u0434\u043d\u043e\u0441\u0442\u0438 \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430 \u0441\u043e\u043f\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u0435 \u0440\u0435\u0431\u0435\u0440, \u0440\u0430\u0437\u043b\u0438\u0447\u0430\u044e\u0442 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0435 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b \u0437\u0430\u0434\u0430\u0447\u0438, \u0432\u0430\u0436\u043d\u0435\u0439\u0448\u0438\u043c\u0438 \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u0430\u044f \u0438 \u043c\u0435\u0442\u0440\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0438.<\/p>\n<p> <\/p>\n<p><em>\u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c<\/em><\/p>\n<p> <\/p>\n<p>\u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440 \u0432 \u043a\u0430\u0436\u0434\u043e\u043c \u0438\u0437 \u0433\u043e\u0440\u043e\u0434\u043e\u0432 \u0432\u0441\u0442\u0430\u0435\u0442 \u043f\u0435\u0440\u0435\u0434 \u0432\u044b\u0431\u043e\u0440\u043e\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e \u0433\u043e\u0440\u043e\u0434\u0430 \u0438\u0437 \u0442\u0435\u0445, \u0447\u0442\u043e \u043e\u043d \u0435\u0449\u0435 \u043d\u0435 \u043f\u043e\u0441\u0435\u0442\u0438\u043b, \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 <code>(n-1)!<\/code> \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u043e\u0432 \u0434\u043b\u044f \u0430\u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u043e\u0439 \u0438 <code>(n-1)!\/2<\/code> \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u043e\u0432 \u0434\u043b\u044f \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0440\u0430\u0437\u043c\u0435\u0440 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0430 \u043f\u043e\u0438\u0441\u043a\u0430 \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0430\u043b\u044c\u043d\u043e \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0433\u043e\u0440\u043e\u0434\u043e\u0432.<\/p>\n<p> <\/p>\n<p>\u0420\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0435 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b \u0437\u0430\u0434\u0430\u0447\u0438 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430 (\u043c\u0435\u0442\u0440\u0438\u0447\u0435\u0441\u043a\u0430\u044f, \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u0430\u044f \u0438 \u0430\u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u0430\u044f) NP-\u044d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u043d\u044b. \u0421\u043e\u0433\u043b\u0430\u0441\u043d\u043e \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u043d\u043e\u0439, \u043d\u043e \u043d\u0435\u0434\u043e\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u0439 \u0433\u0438\u043f\u043e\u0442\u0435\u0437\u0435 \u043e \u043d\u0435\u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u0435 \u043a\u043b\u0430\u0441\u0441\u043e\u0432 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 P \u0438 NP, \u043d\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0434\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u043c\u0430\u0448\u0438\u043d\u044b \u0422\u044c\u044e\u0440\u0438\u043d\u0433\u0430, \u0441\u043f\u043e\u0441\u043e\u0431\u043d\u043e\u0439 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u044d\u043a\u0437\u0435\u043c\u043f\u043b\u044f\u0440\u043e\u0432 \u0437\u0430\u0434\u0430\u0447\u0438 \u0437\u0430 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0433\u043e\u0440\u043e\u0434\u043e\u0432.<\/p>\n<p> <\/p>\n<p>\u0422\u0430\u043a\u0436\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e, \u0447\u0442\u043e \u043f\u0440\u0438 \u0443\u0441\u043b\u043e\u0432\u0438\u0438 <code>P !== NP<\/code> \u043d\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0434\u043b\u044f \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0430 <code>p<\/code> \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u043b \u0431\u044b \u0442\u0430\u043a\u0438\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043e\u0442\u043b\u0438\u0447\u0430\u043b\u0438\u0441\u044c \u0431\u044b \u043e\u0442 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c \u043d\u0430 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442 <code>2^p(n)<\/code>.<\/p>\n<p> <\/p>\n<p>\u041d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u043f\u043e\u0438\u0441\u043a \u0441\u0442\u0440\u043e\u0433\u043e \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043d\u0435 \u0432\u0441\u0435\u0433\u0434\u0430. \u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0435\u043d\u043d\u044b\u0445 \u0440\u0435\u0448\u0435\u043d\u0438\u0439 \u0434\u043b\u044f \u043c\u0435\u0442\u0440\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u0437\u0430 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u0438 \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0430 \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c \u0432\u0434\u0432\u043e\u0435 \u0434\u043b\u0438\u043d\u043d\u0435\u0435 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e. \u0414\u043e \u0441\u0438\u0445 \u043f\u043e\u0440 \u043d\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u0435\u043d \u043d\u0438 \u043e\u0434\u0438\u043d \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u044b\u043c \u0432\u0440\u0435\u043c\u0435\u043d\u0435\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u044b \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043b \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u043b\u0443\u0447\u0448\u0443\u044e, \u0447\u0435\u043c 1,5 \u043e\u0442 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439.<\/p>\n<p> <\/p>\n<p><em>\u041f\u0440\u043e\u0441\u0442\u044b\u0435 \u043c\u0435\u0442\u043e\u0434\u044b \u0440\u0435\u0448\u0435\u043d\u0438\u044f<\/em><\/p>\n<p> <\/p>\n<ul>\n<li>\u043f\u043e\u043b\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0431\u043e\u0440<\/li>\n<li>\u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0431\u043e\u0440<\/li>\n<li>\u0436\u0430\u0434\u043d\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b<\/li>\n<li>\u043c\u0435\u0442\u043e\u0434 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0435\u0433\u043e \u0441\u043e\u0441\u0435\u0434\u0430<\/li>\n<li>\u043c\u0435\u0442\u043e\u0434 \u0432\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u044f \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0435\u0433\u043e \u0433\u043e\u0440\u043e\u0434\u0430<\/li>\n<li>\u043c\u0435\u0442\u043e\u0434 \u0441\u0430\u043c\u043e\u0433\u043e \u0434\u0435\u0448\u0435\u0432\u043e\u0433\u043e \u0432\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u044f<\/li>\n<li>\u043c\u0435\u0442\u043e\u0434 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043e\u0441\u0442\u043e\u0432\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430<\/li>\n<li>\u043c\u0435\u0442\u043e\u0434 \u0438\u043c\u0438\u0442\u0430\u0446\u0438\u0438 \u043e\u0442\u0436\u0438\u0433\u0430<\/li>\n<\/ul>\n<p> <\/p>\n<p>\u0412\u0441\u0435 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0435 (\u0441\u043e\u043a\u0440\u0430\u0449\u0430\u044e\u0449\u0438\u0435 \u043f\u043e\u043b\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0431\u043e\u0440) \u043c\u0435\u0442\u043e\u0434\u044b \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430 \u2014 \u043c\u0435\u0442\u043e\u0434\u044b \u044d\u0432\u0440\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0435. \u0411\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u043e \u044d\u0432\u0440\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u0432 \u043d\u0430\u0445\u043e\u0434\u0438\u0442 \u043d\u0435 \u0441\u0430\u043c\u044b\u0439 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0439 \u043c\u0430\u0440\u0448\u0440\u0443\u0442, \u0430 \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0435\u043d\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435. \u0417\u0430\u0447\u0430\u0441\u0442\u0443\u044e \u0432\u043e\u0441\u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u044b \u0442\u0430\u043a \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u044b\u0435 &#171;any-time-\u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b&#187;, \u0442\u043e \u0435\u0441\u0442\u044c, \u043f\u043e\u0441\u0442\u0435\u043f\u0435\u043d\u043d\u043e \u0443\u043b\u0443\u0447\u0448\u0430\u044e\u0449\u0438\u0435 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0442\u0435\u043a\u0443\u0449\u0435\u0435 \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0435\u043d\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435.<\/p>\n<p> <\/p>\n<p><strong>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/strong><\/p>\n<p> <\/p>\n<p>\u041c\u044b \u0440\u0435\u0448\u0438\u043c \u0437\u0430\u0434\u0430\u0447\u0443 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0433\u0440\u0443\u0431\u043e\u0439 \u0441\u0438\u043b\u044b (brute force), \u0442.\u0435. \u043f\u043e\u043b\u043d\u044b\u043c \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u043e\u043c \u0432\u0441\u0435\u0445 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u043f\u0443\u0442\u0435\u0439. \u042d\u0442\u043e \u0441\u0430\u043c\u0430\u044f \u043f\u0440\u043e\u0441\u0442\u0430\u044f, \u043d\u043e \u0434\u0430\u043b\u0435\u043a\u043e \u043d\u0435 \u0441\u0430\u043c\u0430\u044f \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u0430\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430:<\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ algorithms\/graphs\/traveling-salesman.js \/\/ \u0424\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u0439 \u0443\u0437\u0435\u043b, \u0432\u0441\u0435 \u043f\u0443\u0442\u0438 \/\/ \u043d\u0430 \u0434\u0430\u043d\u043d\u043e\u0439 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u0438 \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u043f\u0443\u0442\u044c. \/\/ \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0432\u0441\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u043f\u0443\u0442\u0438 function findAllPaths(startNode, paths = [], path = []) {   \/\/ \u0422\u0435\u043a\u0443\u0449\u0438\u0439 \u043f\u0443\u0442\u044c   const currentPath = [...path, startNode]    \/\/ \u041f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0435 \u0443\u0437\u043b\u044b   const visitedNodes = currentPath.reduce((a, n) =&gt; {     const copy = { ...a }     copy[n.getKey()] = n     return copy   }, {})    \/\/ \u041d\u0435\u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0435 \u0441\u043e\u0441\u0435\u0434\u0438   const unvisitedNeighbors = startNode     .getNeighbors()     .filter((n) =&gt; !visitedNodes[n.getKey()])    \/\/ \u0415\u0441\u043b\u0438 \u043d\u0435\u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u043d\u0435 \u043e\u0441\u0442\u0430\u043b\u043e\u0441\u044c,   \/\/ \u0442\u043e \u043f\u0443\u0442\u044c \u0437\u0430\u0432\u0435\u0440\u0448\u0435\u043d, \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0435\u043c \u0435\u0433\u043e   if (!unvisitedNeighbors.length) {     paths.push(currentPath)     return paths   }    \/\/ \u041f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0435\u043c \u043d\u0435\u043f\u043e\u0441\u0435\u0449\u0435\u043d\u043d\u044b\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439   for (const neighbor of unvisitedNeighbors) {     \/\/ \u0420\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e \u0438\u0441\u0441\u043b\u0435\u0434\u0443\u0435\u043c \u0438\u0445 \u043f\u0443\u0442\u0438     findAllPaths(neighbor, paths, currentPath)   }    return paths }  \/\/ \u0424\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u043c\u0430\u0442\u0440\u0438\u0446\u0443 \u0441\u043c\u0435\u0436\u043d\u043e\u0441\u0442\u0438, \u0438\u043d\u0434\u0435\u043a\u0441\u044b \u0443\u0437\u043b\u043e\u0432 \u0438 \u0446\u0438\u043a\u043b. \/\/ \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0432\u0435\u0441\/\u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u0446\u0438\u043a\u043b\u0430 function getCycleWeight(adjacencyMatrix, nodesIndices, cycle) {   let weight = 0    for (let i = 1; i &lt; cycle.length; i++) {     const fromNode = cycle[i - 1]     const toNode = cycle[i]     const fromIndex = nodesIndices[fromNode.getKey()]     const toIndex = nodesIndices[toNode.getKey()]     weight += adjacencyMatrix[fromIndex][toIndex]   }    return weight }  \/\/ \u0424\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u0433\u0440\u0430\u0444 export default function bfTravellingSalesman(graph) {   const startNode = graph.getAllNodes()[0]    \/\/ \u041f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0432\u0441\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u043f\u0443\u0442\u0438   const paths = findAllPaths(startNode)    \/\/ \u041d\u0430\u0441 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u0443\u044e\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u0443\u0442\u0438, \u043e\u0431\u0440\u0430\u0437\u0443\u044e\u0449\u0438\u0435 \u0446\u0438\u043a\u043b\u044b   const cycles = paths.filter((p) =&gt; {     const lastNode = p.at(-1)     const lastNodeNeighbors = lastNode.getNeighbors()      return lastNodeNeighbors.includes(startNode)   })    \/\/ \u041c\u0430\u0442\u0440\u0438\u0446\u0430 \u0441\u043c\u0435\u0436\u043d\u043e\u0441\u0442\u0438   const adjacencyMatrix = graph.getAdjacencyMatrix()   \/\/ \u0418\u043d\u0434\u0435\u043a\u0441\u044b \u0443\u0437\u043b\u043e\u0432   const nodesIndices = graph.getNodesIndices()   \/\/ \u041f\u0443\u0442\u044c \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430   let salesmanPath = []   \/\/ \u041c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0432\u0435\u0441 \u043f\u0443\u0442\u0438 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430   let salesmanPathWeight = null    \/\/ \u041f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0435\u043c \u0446\u0438\u043a\u043b\u044b   for (const cycle of cycles) {     \/\/ \u0412\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u043c \u0432\u0435\u0441 \u0446\u0438\u043a\u043b\u0430     const cycleWeight = getCycleWeight(adjacencyMatrix, nodesIndices, cycle)      \/\/ \u041d\u0430\u0441 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u0443\u0435\u0442 \u043f\u0443\u0442\u044c \u0441 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u0432\u0435\u0441\u043e\u043c     if (salesmanPathWeight === null || cycleWeight &lt; salesmanPathWeight) {       salesmanPath = cycle       salesmanPathWeight = cycleWeight     }   }    return salesmanPath }<\/code><\/pre>\n<p> <\/p>\n<p><strong>\u0422\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435<\/strong><\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ algorithms\/graphs\/__tests__\/traveling-salesman.test.js import GraphEdge from '..\/..\/..\/data-structures\/graph\/edge' import Graph from '..\/..\/..\/data-structures\/graph\/index' import GraphNode from '..\/..\/..\/data-structures\/graph\/node' import bfTravellingSalesman from '..\/traveling-salesman'  describe('bfTravelingSalesman', () =&gt; {   it('\u0434\u043e\u043b\u0436\u0435\u043d \u0440\u0435\u0448\u0438\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0443 \u0434\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u043e\u0433\u043e \u0433\u0440\u0430\u0444\u0430', () =&gt; {     const nodeA = new GraphNode('A')     const nodeB = new GraphNode('B')     const nodeC = new GraphNode('C')     const nodeD = new GraphNode('D')      const edgeAB = new GraphEdge(nodeA, nodeB, 1)     const edgeBD = new GraphEdge(nodeB, nodeD, 1)     const edgeDC = new GraphEdge(nodeD, nodeC, 1)     const edgeCA = new GraphEdge(nodeC, nodeA, 1)      const edgeBA = new GraphEdge(nodeB, nodeA, 5)     const edgeDB = new GraphEdge(nodeD, nodeB, 8)     const edgeCD = new GraphEdge(nodeC, nodeD, 7)     const edgeAC = new GraphEdge(nodeA, nodeC, 4)     const edgeAD = new GraphEdge(nodeA, nodeD, 2)     const edgeDA = new GraphEdge(nodeD, nodeA, 3)     const edgeBC = new GraphEdge(nodeB, nodeC, 3)     const edgeCB = new GraphEdge(nodeC, nodeB, 9)      const graph = new Graph(true)     graph       .addEdge(edgeAB)       .addEdge(edgeBD)       .addEdge(edgeDC)       .addEdge(edgeCA)       .addEdge(edgeBA)       .addEdge(edgeDB)       .addEdge(edgeCD)       .addEdge(edgeAC)       .addEdge(edgeAD)       .addEdge(edgeDA)       .addEdge(edgeBC)       .addEdge(edgeCB)      const salesmanPath = bfTravellingSalesman(graph)      expect(salesmanPath.length).toBe(4)      expect(salesmanPath[0].getKey()).toEqual(nodeA.getKey())     expect(salesmanPath[1].getKey()).toEqual(nodeB.getKey())     expect(salesmanPath[2].getKey()).toEqual(nodeD.getKey())     expect(salesmanPath[3].getKey()).toEqual(nodeC.getKey())   }) })<\/code><\/pre>\n<p> <\/p>\n<p>\u0417\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u0442\u0435\u0441\u0442:<\/p>\n<p> <\/p>\n<pre><code class=\"bash\">npm run test .\/algorithms\/graphs\/__tests__\/traveling-salesman<\/code><\/pre>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/pn\/ye\/4l\/pnye4lcdpfdtjy1zjqyofkbfopw.png\" data-src=\"https:\/\/habrastorage.org\/webt\/pn\/ye\/4l\/pnye4lcdpfdtjy1zjqyofkbfopw.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<p>\u041d\u0430 \u0441\u0435\u0433\u043e\u0434\u043d\u044f \u044d\u0442\u043e \u0432\u0441\u0435, \u0434\u0440\u0443\u0437\u044c\u044f. \u0423\u0432\u0438\u0434\u0438\u043c\u0441\u044f \u0432 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u0447\u0430\u0441\u0442\u0438.<\/p>\n<p> <\/p>\n<hr\/>\n<p> <\/p>\n<hr\/>\n<p> <\/p>\n<blockquote><p><a href=\"https:\/\/t.me\/timewebru\"><b>\u041d\u043e\u0432\u043e\u0441\u0442\u0438, \u043e\u0431\u0437\u043e\u0440\u044b \u043f\u0440\u043e\u0434\u0443\u043a\u0442\u043e\u0432 \u0438 \u043a\u043e\u043d\u043a\u0443\u0440\u0441\u044b \u043e\u0442 \u043a\u043e\u043c\u0430\u043d\u0434\u044b Timeweb.Cloud \u2014 \u0432 \u043d\u0430\u0448\u0435\u043c Telegram-\u043a\u0430\u043d\u0430\u043b\u0435<\/b><\/a> <b>\u21a9<\/b><\/p><\/blockquote>\n<p><a href=\"https:\/\/timeweb.cloud\/?utm_source=habr&amp;utm_medium=banner&amp;utm_campaign=promo\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/6r\/9j\/sr\/6r9jsrljpzsgcfyj1jjupubij5e.png\" data-src=\"https:\/\/habrastorage.org\/webt\/6r\/9j\/sr\/6r9jsrljpzsgcfyj1jjupubij5e.png\"\/><\/a><\/p>\n<\/div>\n<\/div>\n<\/div>\n<p><!----><!----><\/div>\n<p><!----><!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/articles\/898686\/\"> https:\/\/habr.com\/ru\/articles\/898686\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-1\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/webt\/ma\/po\/lv\/mapolvqq4uunxfqoaviv3g9km9y.jpeg\" data-src=\"https:\/\/habrastorage.org\/webt\/ma\/po\/lv\/mapolvqq4uunxfqoaviv3g9km9y.jpeg\" data-blurred=\"true\"\/> <\/p>\n<p> \u041f\u0440\u0438\u0432\u0435\u0442, \u0434\u0440\u0443\u0437\u044c\u044f!<\/p>\n<p> <\/p>\n<p>\u0412 \u044d\u0442\u043e\u0439 \u0441\u0435\u0440\u0438\u0438 \u0441\u0442\u0430\u0442\u0435\u0439 \u043c\u044b \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u0435\u043c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b, \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0435 \u0432 <a href=\"https:\/\/github.com\/trekhleb\/javascript-algorithms\">\u044d\u0442\u043e\u043c \u0437\u0430\u043c\u0435\u0447\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u043c \u0440\u0435\u043f\u043e\u0437\u0438\u0442\u043e\u0440\u0438\u0438<\/a>. \u042d\u0442\u043e \u0434\u0435\u0441\u044f\u0442\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u0441\u0435\u0440\u0438\u0438.<\/p>\n<p> <\/p>\n<p>\u0421\u0435\u0433\u043e\u0434\u043d\u044f \u043c\u044b \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0438\u043c \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0434\u043b\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0441 \u0433\u0440\u0430\u0444\u0430\u043c\u0438.<\/p>\n<p> <\/p>\n<p>\u041a\u043e\u0434, \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0439 \u0432 \u044d\u0442\u043e\u0439 \u0438 \u0434\u0440\u0443\u0433\u0438\u0445 \u0441\u0442\u0430\u0442\u044c\u044f\u0445 \u0441\u0435\u0440\u0438\u0438, \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u0432 <a href=\"https:\/\/github.com\/harryheman\/algorithms-data-structures\">\u044d\u0442\u043e\u043c \u0440\u0435\u043f\u043e\u0437\u0438\u0442\u043e\u0440\u0438\u0438<\/a>.<\/p>\n<p> <\/p>\n<p>\u0418\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e? \u0422\u043e\u0433\u0434\u0430 \u043f\u0440\u043e\u0448\u0443 \u043f\u043e\u0434 \u043a\u0430\u0442.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-455154","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/455154","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=455154"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/455154\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=455154"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=455154"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=455154"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}