Обилазак графова - решени задаци¶
У наставку ћемо приказати решења неколико задатака у којима се примењује обилазак графа.
Пећине са тунелима¶
Спелеолози се налазе у улазној дворани пећине, на висини тла, чија је надморска висина позната. Пећина има укупно \(n\) дворана обележених бројевима од \(0\) до \(n-1\) (улазна дворана је обележена бројем \(0\)) и до сваке од њих се може стићи коришћењем неког од многих тунела који их повезују. Сви тунели су двосмерни. Ако се за сваки тунел зна које две дворане повезује и колика је висинска разлика између њих, написати програм који одређује најнижу надморску висину на коју се спелеолози у пећини могу спустити.
Са стандардног улаза се учитава висина тла (цео број), а затим, из следеће линије природни број \(n\) који представља број дворана и затим природни број \(m\) који представља број тунела. У наредних \(m\) линија налазе се по три цела броја раздвојена размацима, која описују тунел: редни број полазне дворане, редни број долазне дворане и висинску разлику имеђу полазне и долазне дворане (негативан број значи да је долазна дворана на мањој надморској висини).
На стандардни излаз исписати цео број који представља најнижу надморску висину на којој се налази нека дворана.
Претпоставимо, на пример, да је дат следећи улаз.
696
5
7
0 1 -7
0 4 4
0 3 -6
1 2 -10
1 3 1
1 4 11
3 2 -11
Распоред пећина и њихове надморске висине су приказане на следећој слици.
Са слике се јасно види да је најнижа дворана број 2 која се налази на надморској висини од 679 метара.
Обиласком графа тунела кренувши од улазне дворане можемо одредити и у низ уписати надморску висину сваке дворане. Након тога тражену најмању висину одређујемо као минимум тог низа. Обилазак можемо имплементирати рекурзивном претрагом у дубину, где у сваком позиву функције прослеђујемо тренутни број дворане и њену надморску висину. Да бисмо избегли циклусе, морамо памтити и низ логичких вредности којим се региструју посећене дворане. Приликом поновног уласка у већ посећену дворану одмах прекидамо даљу претрагу.
У наставку приказујемо рекурзивну имплементацију претраге у дубину, а вама за вежбу остављамо да направите решење које ће бити нерекурзивно (и користиће стек). У питању је неоријентисани тежински граф који представљамо листама суседа.
using System;using System.Collections.Generic;using System.Linq;class Program{ struct Tunel { public int dvoranaDo; public int razlikaVisina; public Tunel(int dvoranaDo, int razlikaVisina) { this.dvoranaDo = dvoranaDo; this.razlikaVisina = razlikaVisina; } } static void visineDFS(int dvorana, int visina, List<Tunel>[] tuneli, bool[] posecena, int[] visine) { posecena[dvorana] = true; visine[dvorana] = visina; foreach (Tunel h in tuneli[dvorana]) if (!posecena[dvoranaDo]) visineDFS(h.dvoranaDo, visina + h.razlikaVisina, tuneli, posecena, visine); } static int minVisinaDFS(int dvorana, int visina, List<Tunel>[] tuneli) { int n = tuneli.Length; bool[] posecena = new bool[n]; int[] visine = new int[n]; visineDFS(dvorana, visina, tuneli, posecena, visine); return visine.Min(); } static void Main(string[] args) { int visinaTla = int.Parse(Console.ReadLine()); int n = int.Parse(Console.ReadLine()); var tuneli = new List<Tunel>[n]; for (int i = 0; i < n; i++) tuneli[i] = new List<Tunel>(); int m = int.Parse(Console.ReadLine()); for (int i = 0; i < m; i++) { int dvoranaOd, dvoranaDo, razlikaVisina; string[] str = Console.ReadLine().Split(); dvoranaOd = int.Parse(str[0]); dvoranaDo = int.Parse(str[1]); razlikaVisina = int.Parse(str[2]); tuneli[dvoranaOd].Add(new Tunel(dvoranaDo, razlikaVisina)); tuneli[dvoranaDo].Add(new Tunel(dvoranaOd, -razlikaVisina)); } Console.WriteLine(minVisinaDFS(0, visinaTla, tuneli)); }}(pecine_sa_tunelima)
Обилазак је могуће реализовати и у ширину (уз коришћење реда), што вам такође остављамо за вежбу.
Пошто се овом функцијом сваки чвор обилази највише једном (само ако је раније непосећен) и анализирају се сви његови суседи, укупна сложеност је \(O(|V| + |E|)\).
Змије и лестве¶
У популарној игри “Змије и лестве” играч се креће од почетног поља бацајући коцкицу и померајући се онолико поља унапред колико покаже коцкица. Постоје две врсте посебних поља. Ако играч стане на неко поље на ком се налазе “лестве”, он се пење уз те лестве и прелази на оно поље са већим бројем до кога те лестве воде. Ако играч стане на неко поље на ком се налази змија, он се спушта и прелази на оно поље са мањим бројем до кога та змија води. Написати програм који одређује минималан број корака (бацања коцкице) којима играч може да стигне од почетног до завршног поља.
Напомена: Ако играч стигне на неко поље које је део циклуса састављеног од лестви и змија, он моментално губи игру и не може да стигне до циља (таква поља се морају избегавати).
Са стандардног улаза се учитава укупан број поља \(n\) (\(5 \leq n \leq 200\)). Поља су обележена бројевима од 0 до \(n-1\). У наредном реду се налази највећи број \(k\) који се може добити бацањем коцкице (коцкицом се добијају бројеви од \(1\) до \(k\)). Након тога се учитава укупан број \(m\) змија и лестви (\(0 \leq m \leq n\)), а затим и подаци о њима (број полазног и број долазног поља).
На стандардни излаз исписати тражени минимални број корака. Ако није могуће стићи до циља, исписати -1.
Размотримо неколико примера.
18
2
5
2 12
3 13
8 17
11 1
14 7
Добијањем броја 2, играч са поља 0 прелази на поље 2 и затим се лествама пење до поља 12. Добијањем броја 2, долази на поље 14, одакле се змијом спушта до поља 7. Добијањем броја 1, долази на поље 8, одакле се лествама пење до циљног поља 17. Дакле, до циљног поља може да се стигне у 3 бацања коцкице, што је, показује се и најмањи број бацања. На наредној слици приказана је ова игра.
Размотримо и наредни пример.
5
2
2
1 3
3 1
Играч не сме да стане на поље 1 или 3, јер ће тада изгубити због циклуса на ком се налази. Зато му је најбоље да прво дође до поља 2, па затим до поља 4 (на поље 4 не може одмах да дође, јер на коцкици може да добије само 1 или 2). Дакле, до циља може да стигне у најмање два бацања коцкице. На наредној слици приказана је ова игра.
Формирање новог графа и његова претрага у ширину
Проблем се може моделовати графом на неколико начина. Један начин је да чворови графа буду поља на табли, а да гране буду прелази између поља (за свако поље памтимо списак поља до којих можемо стићи након бацања коцкице и исцрпног праћења свих лестви и змија (нема потребе правити разлику између њих). Приликом одређивања грана таквог графа, за свако полазно поље \(p\) одређујемо све могуће исходе бацања коцкице и за сваки исход коцкице од поља \(p+i\) пратимо исцрпно лестве и змије док год је то могуће или док не установимо да смо упали у циклус (тако што смо се поново вратили на поље \(p+i\)). Ако нисмо упали у циклус и стигли смо до неког поља \(c\) од којег даље не воде лестве нити змије, у граф додајемо грану од \(p\) до \(c\).
Претходно описани граф је могуће експлицитно формирати у меморији (и представити га листама повезаности). Пошто се тражи најмањи број корака да се стигне од почетног до крајњег чвора природно је применити класичну претрагу у ширину над овако формираним графом. За свако поље памтимо и број корака који је био потребан да се до њега стигне. Претрага у ширину се завршава када први пут одредимо број корака потребних да стигнемо до поља \(n-1\).
На наредној слици је приказан тако формиран граф за игру приказану у првом примеру, као и најкраћи пут од чвора 0 до чвора 17.
Имплементација овог алгоритма дата је у наредном програму.
using System;using System.Collections.Generic;class Program{ static void Main(string[] args) { int n = int.Parse(Console.ReadLine()); int k = int.Parse(Console.ReadLine()); // ucitavamo zmilje i lestve int m = int.Parse(Console.ReadLine()); var prelaz = new Dictionary<int, int>(); for (int i = 0; i < m; i++) { string[] str = Console.ReadLine().Split(); int a = int.Parse(str[0]); int b = int.Parse(str[1]); prelaz[a] = b; } // kreiramo graf var graf = new List<int>[n]; for (int i = 0; i < n; i++) graf[i] = new List<int>(); for (int polje = 0; polje < n; polje++) { if (prelaz.ContainsKey(polje)) continue; for (int i = 1; i <= k && polje + i < n; i++) { // pomeramo se za i polja int cilj = polje + i; // sa tog polja pratimo lestve i zmije dok je god moguce, vodeci // racuna o tome da ne upadnemo u ciklus bool ciklus = false; while (true) { // pokusavamo da pronadjemo prelaz (preko zmija // ili lestvi) od tekuceg cilja int prelazDo; if (!prelaz.TryGetValue(cilj, out prelazDo)) // ako prelaz ne postoji, odredjen je cilj i petlja se prekida break; cilj = prelazDo; if (cilj == polje + i) { ciklus = true; break; } } // ako smo uspesno stigli na neko krajnje polje, dodajemo prelaz u graf if (!ciklus) graf[polje].Add(cilj); } } // broj koraka potreban da se stigne do svakog polja (-1 znaci da je taj // broj trenutno nepoznat) int[] rastojanje = new int[n]; Array.Fill(rastojanje, -1); // klasicna pretraga u sirinu var red = new Queue<int>(); red.Enqueue(0); rastojanje[0] = 0; while (red.Count > 0) { int polje = red.Dequeue(); foreach (int cilj in graf[polje]) if (rastojanje[cilj] == -1) { rastojanje[cilj] = rastojanje[polje] + 1; red.Enqueue(cilj); // prvi put kada stignemo do cilja prekidamo pretragu if (polje == n-1) break; } } Console.WriteLine(rastojanje[n-1]); }}(zmije_i_lestve_ex1_cs)
Број чворова формираног графа једнака је броју поља \(n\), а свако поље може да има \(k\) суседа, па је број грана једнак \(n\cdot k\). Обилазак овог графа зато захтева \(O(n\cdot k)\) корака. Неефикасност, међутим, може да наступи приликом формирања графа. Наиме, ако има пуно змија и лестви, унутрашња петља која исцрпно прати змије и лестве може често имати велики број корака. Једна могућа оптимизација (која није реализована у коду) је да се врши мемоизација - чим се за неко поље открије које је крајње поље ког се са њега стиже змијама и лествама, тај податак се памти, да би се касније употребио без поновног покретања исцрпног обиласка прелаза у склопу унутрашње петље. Остављамо вам да за вежбу имплементирате ову оптимизацију.
Модификована бинарна претрага имплицитно представљеног графа
Уместо да експлицитно креирамо граф прелаза измећу поља, можемо у меморији памтити само граф који је формиран од змија и лестви, а прелазе између поља доступних на основу бачене коцкице (без праћења змија и лестви) представити имплицитно. Пошто свако поље има највише један прелаз помоћу змије или лестава, тај граф се најбоље представља речником који свако поље пресликава у поље на које се може стићи помоћу змија или лестава (нема потребе правити разлику између њих).
Пошто се тражи најмањи број корака да се стигне од почетног до крајњег чвора природно је применити претрагу у ширину, међутим, пошто граф овај пут представља само лестве и змије, а не коначне прелазе, та претрага се мора мало прилагодити.
Од сваког поља \(p\) бацањем коцкице можемо стићи на поља \(p+1\), \(p+2\), \(\ldots\), \(p+k\) (ти прелази нису експлицитно представљени графом, али су имплицитно одређени). Када стигнемо на неко поље \(p+i\), пратимо исцрпно лестве и змије све док је могуће или док не установимо да смо направили циклус (тако што се поново вратимо на поље \(p+i\)). Ако нисмо направили циклус са поља \(p\) вршимо прелаз на поље \(c\) које је било последње доступно лествама и змијама и од којег даље не воде лестве нити змије (дакле, не прелазимо на поље \(p+i\), већ на поље \(c\)). За свако поље памтимо и број корака који је био потребан да се до њега стигне. Претрага у ширину се завршава када први пут одредимо број корака потребних да стигнемо до поља \(n-1\).
На наредној слици је приказан тако формиран граф за игру приказану у првом примеру. Сиве гране су имплицитне и нису представљене у меморији.
Имплементација овако модификованог алгоритма претраге у ширину дата је у следећем C# програму.
using System;using System.Collections.Generic;class Program{ static void Main(string[] args) { int n = int.Parse(Console.ReadLine()); int k = int.Parse(Console.ReadLine()); // ucitavamo zmije i lestve int m = int.Parse(Console.ReadLine()); var prelaz = new Dictionary<int, int>(); for (int i = 0; i < m; i++) { string[] str = Console.ReadLine().Split(); int a = int.Parse(str[0]); int b = int.Parse(str[1]); prelaz[a] = b; } // broj koraka potreban da se stigne do svakog polja (-1 znaci da je taj // broj trenutno nepoznat) int[] rastojanje = new int[n]; Array.Fill(rastojanje, -1); // pretraga u sirinu var red = new Queue<int>(); red.Enqueue(0); rastojanje[0] = 0; while (red.Count > 0) { int polje = red.Dequeue(); for (int i = 1; i <= k && polje + i < n; i++) { // pomeramo se za i polja int cilj = polje + i; // sa tog polja pratimo lestve i zmije dok je god moguce, vodeci // racuna o tome da ne upadnemo u ciklus bool ciklus = false; while (true) { int prelazDo; if (!prelaz.TryGetValue(cilj, out prelazDo)) break; cilj = prelazDo; if (cilj == polje + i) { ciklus = true; break; } } // ako smo uspesno stigli na neposeceno polje, dodajemo ga u red if (!ciklus && rastojanje[cilj] == -1) { rastojanje[cilj] = rastojanje[polje] + 1; red.Enqueue(cilj); // prvi put kada stignemo do cilja prekidamo pretragu if (polje == n-1) break; } } } Console.WriteLine(rastojanje[n-1]); }}(zmije_i_lestve_cs)
Временска сложеност овог приступа идентична је сложености претходног. Наиме, циљно поље се одређује само једном за свако поље графа чвор. И проблеми и могуће оптимизације су идентичне. Са друге стране, меморијска сложеност је боља, јер се граф не памти експлицитно.
Провера бипартитности графа¶
Пера je отишао на летњи спортски камп и када је тамо дошао видео је још неколико својих другара. И друга деца су знала понеког. Интересантно, Пера је свако дете знао посредно (знао је некога, ко зна некога, ко зна некога итд. ко зна то дете).
Потребно је да се деца поделе у две групе, али пошто свако жели да упозна што више нових другара, потребно је да сваку групу чине међусобно непознате особе (две особе које се већ познају не могу бити у истој групи). Написати програм који одређује да ли је то могуће и ако јесте, која ће све деца бити у групи са Пером.
Са стандардног улаза се учитава број деце n, а затим и број парова m деце која се већ познају, а затим и низ парова бројева од 0 до n-1 који представљају познанства.
На стандардни излаз исписати редне бројеве деце који су у групи са Пером (кренувши од Пере који има редни број 0, па у растућем поретку) или симбол - ако тражене две групе није могуће формирати.
Размотримо поново неколико примера.
6
6
0 1
1 2
2 3
3 4
4 5
5 0
Ако су у једној групи деца са бројевима 0, 2 и 4, у другој су деца са бројевима 1, 3 и 5 и тада се ни у једној групи не налазе деца која се међусобно познају.
5
5
0 1
1 2
2 3
3 4
4 0
Пера (особа 0) не сме да буде у групи са особом 1, која не сме да буде у групи са особом 2, што значи да 0 и 2 морају да буду у истој групи. Особе 2 и 3 не могу да буду у истој групи, па су 1 и 3 у истој групи. Особа 4 не сме да буде у групи са особом 3, па она мора бити у групи са особама 0 и 2, међутим, то није допуштено, јер се особе 4 и 0 познају. Одатле следи да није могуће поделити децу на две тражене групе.
Ако се чворови графа могу поделити у две групе, тако да не постоје гране које спајају чворове из исте групе, каже се да је граф бипартитан (двостран).
Ако неки чвор припада левој половини, тада сви његови суседи припадају десној половини, њихови суседи левој половини, њихови суседи десној и тако даље. Зато се задатак може решити обиласком графа (на пример у дубину) обележавајући чворове наизменично (за сваки непосећени чвор се обележава да ли припада левој или десној половини). Ово обележавање можемо схватити као бојење чворова помоћу две боје (на пример, чворове леве половине бојимо плаво, а десне половине црвено). Ако се приликом обиласка наиђе на чвор чији је сусед већ обележен тако да припада истој половини као текући, тада граф није бипартитан. Ако се на такав чвор не наиђе, тада граф јесте бипартитан.
Напомена: пошто граф не мора бити повезан, поступак претраге у дубину и означавања чворова треба поновити за сваку компоненту повезаности засебно (проналажење комонената повезаности је описано засебно).
Наредна анимација приказује успешно бојење једног бипартитног графа.
Наредна анимација приказује неуспешно бојење једног графа који није бипартитан. Током бојења догађа се да чвор има суседа који је обојен у исту боју.
Наредни програм садржи имплементацију провере бипартитности графа која је заснована на нерекурзивно имплементираном обиласку графа у дубину.
using System;using System.Collections.Generic;class Program{ static void Main(string[] args) { // ucitavamo neusmeren graf i predstavljamo ga u obliku lista suseda int n = int.Parse(Console.ReadLine()); int m = int.Parse(Console.ReadLine()); var susedi = new List<int>[n]; for (int i = 0; i < n; i++) susedi[i] = new List<int>(); for (int i = 0; i < m; i++) { string[] str = Console.ReadLine().Split(); int a = int.Parse(str[0]); int b = int.Parse(str[1]); susedi[a].Add(b); susedi[b].Add(a); } // na pocetku ni jedan cvor nije obojen int[] boje = new int[n]; for (int i = 0; i < n; i++) boje[i] = -1; // da li se graf moze obojiti sa dve boje (0 i 1) bool moze = true; // vrsimo bojenje svake komponente povezanosti for (int i = 0; i < n && moze; i++) { // ako cvor i nije obojen, kreceno bojenje njegove komponente od njega if (boje[i] == -1) { var stek = new Stack<int>(); stek.Push(i); // pocetni cvor u svakoj komponenti bojimo u boju 0 int boja = 0; boje[i] = boja; while (stek.Count > 0) { int x = stek.Pop(); // susede cvora x bojimo u suprotnu boju od x boja = 1 - boje[x]; foreach (int sused in susedi[x]) { // ako je neki sused vec obojen u boju cvora x, // bojenje sa dve boje nije moguce if (boje[sused] != -1 && boje[sused] != boja) { moze = false; break; } // ako sused nije obojen, bojimo ga u boju suprotnu od x if (boje[sused] == -1) { boje[sused] = boja; stek.Push(sused); } } } } } if (moze) { // ispisujemo cvorove obojene u boju 0 (u koju je obojen i cvor 0) for (int i = 0; i < n; i++) if (boje[i] == 0) Console.Write(i + " "); Console.WriteLine(); } else Console.WriteLine("-"); }}(da_li_je_bipartitan_cs)
Сложеност овог алгоритма потиче од сложености обиласка графа и једнака је \(O(|V| + |E|)\)
Провера бипартитности графа је еквивалентан проблем проблему 2-обојивости графа у ком се захтева да се чворови графа обоје са две боје тако да нема суседних чворова обојених у исту боју. Уопштење овог проблема је проблем k-обојивости. Покушај да имплементираш алгоритам који проверава да ли се граф може обојити помоћу 3 боје (то је знатно тежи проблем, јер захтева бектрекинг тј. испитивање различитих могућности за бојење текућег чвора).