Zapisywanie rozwidleń w grafie.

Question

Dzień dobry, chciałbym się zapytać o zapisywanie w grafie rozwidleń. Jak na rozpisce na zdjęciu poniżej  chciałbym wyszukiwać jakie rozwidlenia były przed jakimś punktem w stosunku do punktu pierwszego czyli jak  w rozpisce dla "D" i "E" punktu jest tylko rozwidlenie "C" a dla punktów za punktem E są rozwidlenia C i E jak widać w tabeli i moje pytanie jest jak najszybciej taką tabelę zrobić aby za każdy razem jak się pytamy o dwa punkty np. D i  E  to może przejść się po rozwidleniach tego punktu i zobaczyć że jedynym i ostatnim zapisanym punktem wspólnym(rozwidleniem) jest C natomiast dla I oraz J było by to E ponieważ C jest dalsze. litery w rozwiązaniu byśmy zamienili na liczby, litery są tylko dla przykładu aby lepiej zrozumieć. Nie chodzi mi o kod tylko bardziej jakieś logiczne wytłumaczenie czyli przechodzimy po tabeli zapisujemy do każdego indeksu rozwidlenie w jakiś sposób. Wiem, że może nie jest to całkiem jasne wytłumaczenie problemu ale liczę na pomoc i z góry dziękuje.

*Graf może wyglądać inaczej może mieć więcej rozwidleń może ich nawet mieć zero.

Answer 1

Nie wiem, czy o to ci chodzi, ale zazwyczaj jest to organizowane tak, że masz elementarną strukturę danych:

{
  index: number;
  parentIndex: number;
}

I teraz masz głównego noda (rozwidlenie) on nie ma rodzica więc parentIndex = null, natomiast jego dzieci będą miały parentIndex = indeksowi głównego one też mogą mieć dzieci, które przechowują indeks swojego rodzica. Znalezienie wszystkich rozwidleń związanych z dzieckiem będzie polegało na przeskakiwaniu z indeksu na indeks aż znajdziesz głównego, który rodzica mieć nie będzie. Elementy będą przechowywane w tablicy, można to zorganizować w klasie, która udostępni metody dodawania/wyszukiwania. Można to też jeszcze inaczej zorganizować ale ta struktura jest też ciekawa bo można ją zastosować np w bazie danych.

Comments

W tytule pojawia się słowo graf, nie drzewo, więc chyba autor chciał wiedzieć na jakie sposoby można go reprezentować (macierz sąsiedztwa / lista sąsiedztwa)

Rozumiem, jednak, że na obrazku pojawia się drzewo, więc autor może sam nie wiedzieć czego chce

Answer 2

Chodzi o drzewo czy graf? Jesli o drzewo to pewnie można skorzystać ze zmodyfikowanego LCA