Bahagi 2 Bahagi 3 Bahagi 4 Na-prompt akong isulat ang artikulong ito sa pamamagitan ng isang mapaminsalang gawain mula sa Java Multithreading quest, na, nang walang panunukso mula sa mga developer, ay tinawag nilang "StringBuilder task." Ang kakanyahan ng kanyang kondisyon ay ang isang hanay ng mga salita (sa kondisyon na ibinigay ang mga pangalan ng mga lungsod, na nakapagpapaalaala sa laro ng salita ng mga bata) ay kailangang ayusin ayon sa prinsipyo ng domino, ang huling titik ng n' salita ay dapat ay katumbas ng unang titik ng salita (n+1) go, at nalaman na ang lahat ng ibinigay (indibidwal) na mga salita ay idinagdag sa naturang chain. Kung posible na bumuo ng ilang mga pagpipilian para sa nais na hanay ng mga salita, sinuman ang tinanggap bilang isang solusyon. Sa kabila ng maliwanag na pagiging simple at kalinawan ng kundisyon, ang paglutas sa problema ay malayo sa madali, at ang mahusay na paggamit ng StringBuilder ay hindi nakaligtas sa sitwasyon. Ang mga nag-develop ng problema ay lumabas na inutusan ng mga isomorph mula sa planetang Linear Chaos, na higit sa isang beses ay natakot sa mga kadete ng JavaRush. Tulad ng inaasahan, ang mga mababaw na solusyon ay hindi nababagay sa validator, dahil palaging may mga chain na pumipilit sa walang muwang na algorithm na laktawan ang mga salita. Kinailangan na mag-pile up ng mga karagdagang "saklay", na, habang nagpapalubha sa problema, ay hindi nagdala ng solusyon na mas malapit sa pangkalahatang kaso at lalong pinalakas ang pakiramdam na ang isang simpleng kondisyon ay dapat magkaroon ng pantay na simpleng solusyon. Kinailangan kong baguhin ang mga taktika at sumisid ng kaunti sa mas pangunahing mga lugar. Hayaan akong gumawa kaagad ng reserbasyon na sa anumang kaso ay hindi ko itinuturing ang aking sarili na isang dalubhasa sa teorya ng graph; ang mga paksang tatalakayin ko ay halos hindi lalampas sa saklaw ng paglutas ng problema sa salitang domino, maliban, marahil, lamang isang pares ng mga digression ng isang teoretikal na kalikasan. Kaya, mga graph. Ano ang graph: ito ay isang koleksyon (set, set, list - whatever) ng mga vertex na konektado sa isa't isa . Ang mga koneksyon ay karaniwang tinatawag na mga gilid , ang mga vertice ay tinatawag ding mga node o node. Ito ay isang graph: Ito rin ay isang graph: Kung masasabi natin ang tungkol sa isang gilid na ito ay may direksyon, kung gayon ang graph ay tinatawag na oriented : Ang mga graph sa unang dalawang larawan ay hindi nakadirekta. Masasabi natin tungkol sa kanila na ang gilid (u, v) ay magkapareho sa gilid (v, u), iyon ay, halimbawa, ang mga gilid (0, 4) at (4, 0) ay magkaparehong gilid. Ang mga arrow sa mga gilid ng isang nakadirekta na graph ay nangangahulugan na ang gilid (u, v) ay isang landas mula sa vertex u hanggang sa vertex v at gilid (v, u) ay hindi umiiral. Sa ikatlong larawan mayroong isang gilid (E, A). Walang gilid (A, E). Tingnan natin ang huling pagguhit. Maaari mong mapansin na ang vertex F ay walang mga gilid, ito ay lubos na posible. Napansin din namin na ang isang gilid ay lumitaw malapit sa vertex A - isang loop, at sa pagitan ng mga vertex B at D mayroong dalawang magkaibang direksyon na mga gilid. Pinapayagan ng mga nakadirekta na graph ang mga naturang artifact. Sabihin nating inilalarawan ng graph ang isang grupo ng mga kakilala na nagbibigay ng regalo sa isa't isa. Nakita natin na ang sakim na si F ay hindi nagbigay ng anuman sa sinuman, si B at D ay nagpalitan ng mga regalo (maliban sa katotohanan na ang bawat isa sa kanila ay nagbigay ng regalo sa iba), at si A ay nagbigay ng regalo sa kanyang sarili, marahil sa okasyon ng matagumpay na paglutas ng isang problema mula sa planetang Linear Chaos. Sa pamamagitan ng paraan, tandaan na ang mga vertex ng graph ay hindi kailangang mga numero o naglalaman ng mga numero; sila ay mga lalagyan, i.e. maaari silang mag-imbak ng anumang bagay. Ang graph ay isang paglalarawan ng mga koneksyon. Ang isang mahalagang termino na magiging kapaki-pakinabang sa amin sa ibang pagkakataon - ang bilang ng mga gilid na nakakabit sa isang vertex (o, gaya ng sinasabi nila, insidente dito) ay tinatawag na antas ng isang naibigay na vertex. Halimbawa, sa unang larawan, ang vertex 0 ay may degree 2, ang 1 ay may degree 4, 3 ay may degree 3, ang vertex 0 ng pangalawang figure ay may degree 1. Sa artikulong ito ay hindi namin susuriin ang iba't ibang uri ng mga graph, babanggitin lang natin na meron ding weighted graphs, mga. yaong kung saan ang isang tiyak na numero ay nakakabit sa bawat gilid, na nagpapahiwatig ng "presyo" ng pagpasa nito. Ang mga konektadong graph ay may bilang ng mga subtype, na nakikilala sa pamamagitan ng kanilang mga katangian. Halimbawa, ang mga graph na ang mga gilid ay hindi bumubuo ng isang cycle kahit saan ay tinatawag na mga puno (mayroon silang mga kawili-wiling pamilya na may mga kahanga-hangang pangalan tulad ng "mga pulang-itim na puno," halimbawa) at malawakang ginagamit sa iba't ibang mahahalagang algorithm at istruktura ng data. Paggamit ng isang graph upang malutas ang isang problema Ang lahat ng ito ay napaka-interesante, sabi mo, ngunit ano ang kinalaman ng lahat ng ito sa pagbuo ng isang hanay ng mga salita? Ito ay lumiliko na ang pinaka-direktang bagay ay. Tingnan natin ang aming halimbawa ng pagsubok mula sa kundisyon: { Amsterdam Melbourne New York Kyiv Vienna }. Isulat natin sa anumang pagkakasunud-sunod ang mga "nodal" na titik kung saan nakakapit ang mga salita: {A, M, N, K, B} at ikonekta ang mga ito sa mga salita. Gaya ng nakikita natin, mayroon tayong direktang graph kung saan ang mga node ay mga titik at ang mga gilid ay mga salita, na nagdudugtong sa kanila. Kung makakahanap tayo ng paraan upang madaanan ang lahat ng mga gilid mula sa vertex hanggang sa vertex upang bisitahin natin ang bawat gilid nang isang beses lamang, malulutas ang ating problema. Subukan nating ipamahagi ang mga node sa diagram nang medyo naiiba: Ngayon ay mas makikita natin na ang ating graph ay isang closed loop. Maaari nating simulan ang pagkakasunud-sunod sa anumang salita, at ito ang magiging tamang desisyon. Gayunpaman, ang kondisyon ng problema ay nagsasabi sa amin na anumang isang solusyon ay magiging sapat. Palitan natin ang Vena ng Vladimir: Nakikita natin ang dalawang kahihinatnan: una, kailangan nating magdagdag ng bagong vertex, ang letrang P, at pangalawa, nakikita natin na hindi na posible na i-loop ang ating graph. Isa-isahin natin ang lahat ng nasa itaas at ipakilala ang dalawang bagong termino: 1. Ang isang konektadong graph na ang mga gilid ay maaaring daanan sa pamamagitan ng pagbisita sa bawat isa nang isang beses lamang ay tinatawag na graph na naglalaman ng isang "Eulerian path" . Ang isang tampok ng naturang graph (maliban sa kawalan ng mga vertice na walang mga gilid) ay ang pantay na antas ng lahat ng mga vertex maliban sa dalawa (at dalawa lamang). 2. Kung naging posible na bumalik sa orihinal na node, sinasabi namin na mayroong "Eulerian cycle" sa graph . Ang isang tampok ng naturang graph (maliban sa kawalan ng mga vertices na walang mga gilid) ay ang pantay na antas ng lahat ng vertices. Isipin natin ang aming listahan ng mga lungsod tulad nito: {Moscow Anapa Adler Rostov-on-Don Wuhan}. Bumuo tayo ng graph: Sa diagram makikita mo na ang graph na ito ay may Eulerian path. Mayroon lamang dalawang vertices na may kakaibang degree - ito ay M at L, ang iba ay pantay: A ay may degree 4, dahil ang loop ay binibilang ng dalawang beses, at ang P at Y ay may degree na 2. Kung makabuo tayo ng isang algorithm na maaaring bumuo ng isang Eulerian na ruta batay sa scheme na ito, sabihin nating, sa anyo ng isang listahan {M, A, A, P, Y , L}, pagkatapos ay malulutas namin ang problema , dahil Ang paglabas ng mga salita sa isang naibigay na pagkakasunud-sunod ay magiging isang bagay lamang ng pamamaraan. Kaya, ang solusyon sa aming problema sa domino word ay bumaba sa pagpapatupad ng isang algorithm para sa paghahanap ng isang Eulerian na landas (ang cycle ay "libre") sa isang direktang graph. Susunod ->
Ito rin ay isang graph: 
Kung masasabi natin ang tungkol sa isang gilid na ito ay may direksyon, kung gayon ang graph ay tinatawag na oriented : 
Ang mga graph sa unang dalawang larawan ay hindi nakadirekta. Masasabi natin tungkol sa kanila na ang gilid (u, v) ay magkapareho sa gilid (v, u), iyon ay, halimbawa, ang mga gilid (0, 4) at (4, 0) ay magkaparehong gilid. Ang mga arrow sa mga gilid ng isang nakadirekta na graph ay nangangahulugan na ang gilid (u, v) ay isang landas mula sa vertex u hanggang sa vertex v at gilid (v, u) ay hindi umiiral. Sa ikatlong larawan mayroong isang gilid (E, A). Walang gilid (A, E). Tingnan natin ang huling pagguhit. Maaari mong mapansin na ang vertex F ay walang mga gilid, ito ay lubos na posible. Napansin din namin na ang isang gilid ay lumitaw malapit sa vertex A - isang loop, at sa pagitan ng mga vertex B at D mayroong dalawang magkaibang direksyon na mga gilid. Pinapayagan ng mga nakadirekta na graph ang mga naturang artifact. Sabihin nating inilalarawan ng graph ang isang grupo ng mga kakilala na nagbibigay ng regalo sa isa't isa. Nakita natin na ang sakim na si F ay hindi nagbigay ng anuman sa sinuman, si B at D ay nagpalitan ng mga regalo (maliban sa katotohanan na ang bawat isa sa kanila ay nagbigay ng regalo sa iba), at si A ay nagbigay ng regalo sa kanyang sarili, marahil sa okasyon ng matagumpay na paglutas ng isang problema mula sa planetang Linear Chaos. Sa pamamagitan ng paraan, tandaan na ang mga vertex ng graph ay hindi kailangang mga numero o naglalaman ng mga numero; sila ay mga lalagyan, i.e. maaari silang mag-imbak ng anumang bagay. Ang graph ay isang paglalarawan ng mga koneksyon. Ang isang mahalagang termino na magiging kapaki-pakinabang sa amin sa ibang pagkakataon - ang bilang ng mga gilid na nakakabit sa isang vertex (o, gaya ng sinasabi nila, insidente dito) ay tinatawag na antas ng isang naibigay na vertex. Halimbawa, sa unang larawan, ang vertex 0 ay may degree 2, ang 1 ay may degree 4, 3 ay may degree 3, ang vertex 0 ng pangalawang figure ay may degree 1. Sa artikulong ito ay hindi namin susuriin ang iba't ibang uri ng mga graph, babanggitin lang natin na meron ding weighted graphs, mga. yaong kung saan ang isang tiyak na numero ay nakakabit sa bawat gilid, na nagpapahiwatig ng "presyo" ng pagpasa nito. Ang mga konektadong graph ay may bilang ng mga subtype, na nakikilala sa pamamagitan ng kanilang mga katangian. Halimbawa, ang mga graph na ang mga gilid ay hindi bumubuo ng isang cycle kahit saan ay tinatawag na mga puno (mayroon silang mga kawili-wiling pamilya na may mga kahanga-hangang pangalan tulad ng "mga pulang-itim na puno," halimbawa) at malawakang ginagamit sa iba't ibang mahahalagang algorithm at istruktura ng data. Paggamit ng isang graph upang malutas ang isang problema Ang lahat ng ito ay napaka-interesante, sabi mo, ngunit ano ang kinalaman ng lahat ng ito sa pagbuo ng isang hanay ng mga salita? Ito ay lumiliko na ang pinaka-direktang bagay ay. Tingnan natin ang aming halimbawa ng pagsubok mula sa kundisyon: { Amsterdam Melbourne New York Kyiv Vienna }. Isulat natin sa anumang pagkakasunud-sunod ang mga "nodal" na titik kung saan nakakapit ang mga salita: {A, M, N, K, B} 
at ikonekta ang mga ito sa mga salita. 
Gaya ng nakikita natin, mayroon tayong direktang graph kung saan ang mga node ay mga titik at ang mga gilid ay mga salita, na nagdudugtong sa kanila. Kung makakahanap tayo ng paraan upang madaanan ang lahat ng mga gilid mula sa vertex hanggang sa vertex upang bisitahin natin ang bawat gilid nang isang beses lamang, malulutas ang ating problema. Subukan nating ipamahagi ang mga node sa diagram nang medyo naiiba: 
Ngayon ay mas makikita natin na ang ating graph ay isang closed loop. Maaari nating simulan ang pagkakasunud-sunod sa anumang salita, at ito ang magiging tamang desisyon. Gayunpaman, ang kondisyon ng problema ay nagsasabi sa amin na anumang isang solusyon ay magiging sapat. Palitan natin ang Vena ng Vladimir: 
Nakikita natin ang dalawang kahihinatnan: una, kailangan nating magdagdag ng bagong vertex, ang letrang P, at pangalawa, nakikita natin na hindi na posible na i-loop ang ating graph. Isa-isahin natin ang lahat ng nasa itaas at ipakilala ang dalawang bagong termino: 1. Ang isang konektadong graph na ang mga gilid ay maaaring daanan sa pamamagitan ng pagbisita sa bawat isa nang isang beses lamang ay tinatawag na graph na naglalaman ng isang "Eulerian path" . Ang isang tampok ng naturang graph (maliban sa kawalan ng mga vertice na walang mga gilid) ay ang pantay na antas ng lahat ng mga vertex maliban sa dalawa (at dalawa lamang). 2. Kung naging posible na bumalik sa orihinal na node, sinasabi namin na mayroong "Eulerian cycle" sa graph . Ang isang tampok ng naturang graph (maliban sa kawalan ng mga vertices na walang mga gilid) ay ang pantay na antas ng lahat ng vertices. Isipin natin ang aming listahan ng mga lungsod tulad nito: {Moscow Anapa Adler Rostov-on-Don Wuhan}. Bumuo tayo ng graph: 
Sa diagram makikita mo na ang graph na ito ay may Eulerian path. Mayroon lamang dalawang vertices na may kakaibang degree - ito ay M at L, ang iba ay pantay: A ay may degree 4, dahil ang loop ay binibilang ng dalawang beses, at ang P at Y ay may degree na 2. Kung makabuo tayo ng isang algorithm na maaaring bumuo ng isang Eulerian na ruta batay sa scheme na ito, sabihin nating, sa anyo ng isang listahan {M, A, A, P, Y , L}, pagkatapos ay malulutas namin ang problema , dahil Ang paglabas ng mga salita sa isang naibigay na pagkakasunud-sunod ay magiging isang bagay lamang ng pamamaraan. Kaya, ang solusyon sa aming problema sa domino word ay bumaba sa pagpapatupad ng isang algorithm para sa paghahanap ng isang Eulerian na landas (ang cycle ay "libre") sa isang direktang graph. Susunod ->
GO TO FULL VERSION