Mniej-więcej rozumiem, jak działa przeszukiwanie w głąb (wszerz jeszcze przede mną, jak coś). Jednak jedyne implementacje tego algorytmu, jakie znalazłem (w pseudokodzie), uwzględniają skorzystanie z iteracji po wszystkich nieodwiedzonych wierzchołkach. Jak natomiast mógłby wyglądać pseudokod przeszukiwania grafu w głąb bez iteracji?
Napisałem coś takiego (pseudokod), ale po przepisaniu na JavaScript Node.js mówi mi, że następuje przepełnienie stosu: :/
Pseudokod
DFS (pred, getNeighbors, curVertex, unvisitedNeighbors, path)
if pred(curVertex)
then return curVertex
else
if not empty(unvisitedNeighbors)
then DFS(
pred,
unvisitedNeighbors[0],
concat(
relativeComplement(
getNeighbors(unvisitedNeighbors[0]),
slice(unvisitedNeighbors, 1, len(unvisitedNeighbors))
),
slice(unvisitedNeighbors, 1, len(unvisitedNeighbors))
),
concat(unvisitedNeighbors[0], path)
)
else
if not empty(path)
then DFS(
pred,
path[0],
slice(unvisitedNeighbors, 1, len(unvisitedNeighbors)),
slice(path, 1, len(path))
)
else return nil
Przykładowe wywołanie:
DFS(vt -> equal(vt, 4), /* tu jakaś funkcja pobierania sąsiednich wierzchołków */, 0, [1, 2, 3], [])
W pseudokodzie istotne jest dla mnie znalezienie kompromisu między jak najmniejszą liczbą operacji pomocnicznych (tj. np. slice, empty), zmiennych (tj. parametrów funkcji) i przejrzystością kodu.
UPDATE: Znalazłem i poprawiłem jeden błąd: lista path powinna być pusta przy wywołaniu. Jeśli nie będzie, to początkowy wierzchołek dodany będzie podwójnie. Nie wiem, czy ta poprawka ma jakiekolwiek przełożenie na działanie algorytmu – nadal pojawia się przepełnienie stosu.
PS. Jeszcze przed powyższą poprawką poprawiłem inny błąd, niezwiązany bezpośrednio z algorytmem. Funkcja pobierania sąsiednich wierzchołków dodawała dany wierzchołek do jego własnych sąsiadów.
UPDATE2: Poprawiłem drugi błąd w algorytmie. W rekurencyjnym wywoływaniu DFS podczas przechodzenia do nowego wierzchołka było zwykłe łączenie listy jego sąsiednich wierzchołków z listą nieodwiedzonych do tej pory wierzchołków. Skutkowało to tym, że jeśli była pętla np. (1, 2), (2, 1), to przechodząc z wierzchołka 1 do wierzchołka 2 wierzchołek 1 występował zaczynał występować na liście dwukrotnie.
...I właśnie pisząc powyższy akapit uświadomiłem sobie, że jest w moich danych testowych (tj. w grafie) cykl. Zobaczę, jak sobie radzi algorytm bez niego. Docelowo cykle chciałbym zachować – choćby dlatego, by algorytm mógł działać na grafach nieskierowanych.
PS2. Dla formalności: nadal, po drugiej poprawce, jest przepełnienie stosu.
UPDATE3: Ech, bez cykli testy przechodzą. Niezależnie od tego wrzucam implementację w JS – może rzeczywiście, jak wzmiankował niżej @tsz, jest gdzieś błąd w niej samej. Wrzucam też testy.
Implementacja:
// JavaScript
exports.dfs
= (pred, getNbVtsFn, curVt, unvNbVts, path) =>
pred(curVt)
? curVt
// Check whether you can move forwards
: unvNbVts.length !== 0
// Move forward
? exports.dfs(
pred,
getNbVtsFn,
unvNbVts[0],
getNbVtsFn(unvNbVts[0])
.filter(
vt => !unvNbVts.slice(1).find(v => vt.id === v.id)
).concat(unvNbVts.slice(1)),
[curVt].concat(path)
)
// Check whether you can move backwards
: path.length !== 0
// Move backwards
? exports.dfs(
pred,
getNbVtsFn,
path[0],
unvNbVts.slice(1),
path.slice(1)
)
// No move possible === all vertices visited
: undefined;
Testy (dla czytelności pominąłem komentarze JSDoc):
// JavaScript
const getNbVts
= (gr, vt) =>
gr.vts.filter(
v =>
vt.nbVtIDs.includes(v.id)
&& v.id !== vt.id
);
const mockGraph = {
vts: [
{ id: 0, nbVtIDs: [1, 2] },
{ id: 1, nbVtIDs: [3] },
{ id: 2, nbVtIDs: [3] },
{ id: 3, nbVtIDs: [] }
]
};
const root = mockGraph.vts.find(v => v.id === 0);
exports.testCases = [
new TestCase(
"dfs",
dfs,
[
v => v.id === 0,
v => getNbVts(mockGraph, v),
root,
getNbVts(mockGraph, root),
[]
],
res => res.id === 0
),
new TestCase(
"dfs",
dfs,
[
v => v.id === 1,
v => getNbVts(mockGraph, v),
root,
getNbVts(mockGraph, root),
[]
],
res => res.id === 1
),
new TestCase(
"dfs",
dfs,
[
v => v.id === 2,
v => getNbVts(mockGraph, v),
root,
getNbVts(mockGraph, root),
[]
],
res => res.id === 2
),
new TestCase(
"dfs",
dfs,
[
v => v.id === 3,
v => getNbVts(mockGraph, v),
root,
getNbVts(mockGraph, root),
[]
],
res => res.id === 3
)
];
UPDATE4: Przepisałem testy na prostsze. Teraz wierzchołki są tożsame z ich identyfikatorami (tj. są reprezentowane przez typ number).
UPDATE5: Co do tej nowej, wzmiankowanej powyżej wersji testów (i oczywiście samej implementacji) – nie wiem: czy zamieszczać? I tak już dużo kodu tu jest.
UPDATE6: W pierwszym PS napisałem, że poprawiłem funkcję pobierania sąsiednich wierzchołków. Wyglądało to tak, że dla danego wierzchołka uniemożliwiłem jej ustawianie jego samego jako jego sąsiedniego wierzchołka. Teraz sobie jednak uświadomiłem, że jeśli chcę obsługiwać cykle (a chcę, jak wyżej napisałem), funkcja ta musi móc dodawać dany wierzchołek do jego własnych sąsiadów.
UPDATE7: Doszedłem do wniosku, że nie będę poprawiać wersji kodu w pierwszym poście, tylko będę zamieszczać nowe wersje sukcesywnie w kolejnych postach. Dzięki temu będzie będzie bardziej przejrzyście, mam nadzieję.