Zvratné smerované grafy a hrany - výkon, algoritmus, graf, orientovaný graf

Takže pracujem na tomto probléme:

Tu je to, čo mám zatiaľ

a) Create a new graph with the same size 2-dimensional array, B. Iterate
through the original graph"s 2-dimensional array, A, which is of size VxV,
where V is the number of vertices in the graph. If A[i][j] is true, then an
edge exists there. Set B[j][i] true in the new reversed graph"s matrix.
The algorithm will be of complexity V^2 since it needs to iterate through
all of the 2-dimensional array.

b) Create a new graph with an empty array, B, of size V, where V is the
number of vertices. Iterate through the array of lists in the original
graph, A. if there is a list  at A[i] then iterate through each one and i to
the corresponding B[x] where x is the integer in the list. The algorithm
will be complexity of V + E since it needs to iterate through an array of
size V, and then a total list elements of size E.

Najprv by som chcel urobiť nejaké dvojité kontrolyodpovedať. Nie som oboznámený s riadenými grafmi a nie som príliš kvalifikovaný pri hľadaní efektívnosti / komplexnosti algoritmov. Myslím, že som to urobil správne, ale chcel by som nejakú pomoc, ak to budem potrebovať. boli to prvé algoritmy, ktoré mi vyskočili do hlavy, takže mám pocit, že existuje pravdepodobne lepší spôsob, ako to urobiť.

Vďaka

odpovede:

Vaše a) je správne. V maticovom jazyku nájdete transponovať matice A. Jeden malý detail, na ktorý sa treba zamyslieť, je, či je potrebné nastaviť okrajové položky B na hodnotu false. Závisí to od jazyka, hoci väčšina jazykov (myslím) by pri inicializácii pamäte nastavila všetky položky B na false alebo 0. Zložitosť je skutočne O(V^2).

Vaše písmeno b) nie je správne formulované. Ale myslím si, že máš nápad. Musíte niečo zatlačiť do zoznamu na B [x]. Popíšte x lepšie. Zložitosť je skutočne O(V+E).

Nie je toho veľa, aby ste ich urobili viacefektívna. Musíte spracovať každú dvojicu vrcholov v prvom prípade a každú hranu v druhom. V prípade susediacej matice môžete zameniť poradie vrcholov skôr, ako sa pozriete hore, takže ak sa vás opýta, či je hrana od (x, y), namiesto toho vrátite odpoveď pre (y, x). , ale ak to urobíte viac ako V^2 časy, keď neprídete dopredu. Rovnaké ako pri zoznamoch susedov.