Graph Traversing
Minulá část byla o datové struktuře jménem Graph. Dozvěděli jste se v ní co to graph je, jaké jsou typy graphů a také jsme si pro graph vytvořili vlastní třídu. V této části si ukážeme, jak můžeme graph procházet.
Co je to Graph Traversing
Tato část je pojmenovaná jako Graph Traversing. Jak jsem již psal v části Tree Traversing, v češtině traversing znamená procházení. Ukážeme si tedy, jakými způsoby můžeme graph procházet. Stejně jako u procházení tree, tak i u graphů existují dva hlavní způsoby pro jejich procházení: Breadth First a Depth First. Pro oba tyto způsoby si do naší graph třídy, kterou jsme si vytvořili v minulé části, přidáme metodu. Tyto metody projdou všechny vertexy graphu a na konci vrátí pole, které bude obsahovat vertexy graphu v pořadí, ve kterém byly navštíveny.
Co pro ukázku procházení Graphu potřebujeme
Jak jsem již psal, pro procházení graphu si v naší graph třídě z minulé části vytvoříme metody. Vytvoříme si celkem 3 metody. Dvě se budou týkat Depth First procházení a třetí Breadth First procházení. Depth First procházení můžeme provádět iterativně nebo rekurzivně. Obě verze si ukážeme, proto pro něj budeme mít dvě metody. Pro iterativní verzi Depth First procházení navíc potřebujeme Stack a pro Breadth First procházení potřebujeme Queue. Obě tyto datové struktury jsme si vytvářeli v části Stack a Queue, takže je jen použijeme.
Následující ukázka ukazuje startovní kód.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class Stack {
constructor() {
this.first = null;
this.size = 0;
}
push(value) {
const newNode = new Node(value);
if (!this.first) {
this.first = newNode;
} else {
newNode.next = this.first;
this.first = newNode;
}
return ++this.size;
}
pop() {
if (!this.first) return null;
const value = this.first.value;
this.first = this.first.next;
this.size--;
return value;
}
}
class Queue {
constructor() {
this.first = null;
this.last = null;
this.size = 0;
}
enqueue(value) {
const newNode = new Node(value);
if (!this.first) {
this.first = newNode;
this.last = newNode;
} else {
this.last.next = newNode;
this.last = newNode;
}
return ++this.size;
}
dequeue() {
if (!this.first) return null;
const value = this.first.value;
if (this.first === this.last) {
this.last = null;
}
this.first = this.first.next;
this.size--;
return value;
}
}
class Graph {
constructor() {
this.adjacencyList = {};
}
addVertex(vertex) {
if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
}
addEdge(v1, v2) {
if (!this.adjacencyList[v1] || !this.adjacencyList[v2]) return;
if (!this.adjacencyList[v1].includes(v2)) this.adjacencyList[v1].push(v2);
if (!this.adjacencyList[v2].includes(v1)) this.adjacencyList[v2].push(v1);
}
removeEdge(v1, v2) {
if (!this.adjacencyList[v1] || !this.adjacencyList[v2]) return;
let index = this.adjacencyList[v1].findIndex((val) => val === v2);
if (index !== -1) this.adjacencyList[v1].splice(index, 1);
index = this.adjacencyList[v2].findIndex((val) => val === v1);
if (index !== -1) this.adjacencyList[v2].splice(index, 1);
}
removeVertex(vertex) {
while (this.adjacencyList[vertex].length) {
const adjacentVertex = this.adjacencyList[vertex].pop();
this.removeEdge(vertex, adjacentVertex);
}
delete this.adjacencyList[vertex];
}
}Depth First Traversing - rekurzivně
Jako první si ukážeme Depth First procházení graphu. Depth First u graphu znamená, že se vždy vezme první vertex se kterým je zrovna procházený vertex propojen a pokračuje se dál. Až se najde vertex, který již nemá žádné propojené vertexy, které by se měli procházet, tak se pokračuje směrem zpět a stejným způsobem se procházejí ostatní vertexy, které ještě nebyly navštíveny.
Graph nemá žádný počáteční vertex jako tomu bylo u tree. Takže pokud chceme graph procházet, musíme určit odkud se má začít. Proto budou metody pro procházení graphu vždy přijímat vertex, od kterého se má začínat.
Depth First procházení můžeme provést rekurzivně nebo iterativně. Jako první si ukážeme rekurzivní verzi. Depth First procházení je u graphu možná složitější si představit než u tree, ale myslím že následující vizuální ukázka vám v tom může pomoct.
V ukázce se vertexy, které již byly navštíveny, ukládají do objektu visited. V graficky znázorněném graphu se vertexy uložené v tomto objektu označují červeně.
class Graph {
/* ... */
// metoda pro Depth First procházení (rekurzivní verze)
DFRecursive(startVertex) {
// do tohoto pole se budou postupně ukládat navštívené vertexy
const result = [];
// v tomto objektu se budou ukládat vertexy, které již byly navštíveny
const visited = {};
// pomocná funkce pro procházení graphu
const df = (vertex) => {
// pokud se vertex v graphu nenachází, tak se funkce ukončí
if (!this.adjacencyList[vertex]) return;
// vertex se uložením do objektu označí jako navštívený
visited[vertex] = true;
// uložení vertexu do pole result
result.push(vertex);
// tento cyklus projde všechny vertexy, se kterými je vertex propojen
for (let adjacentVertex of this.adjacencyList[vertex]) {
// pokud vertex ještě nebyl navštíven, tak se pro něj zavolá funkce df
if (!visited[adjacentVertex]) df(adjacentVertex);
}
}
// zavolání pomocné funkce df se startovním vertexem jako argumentem
df(startVertex);
// vrácení pole s vertexy
return result;
}
}
// vytvoření graphu
const graph = new Graph();
graph.addVertex("A"); graph.addVertex("B"); graph.addVertex("C"); graph.addVertex("D");
graph.addVertex("E"); graph.addVertex("F"); graph.addVertex("G"); graph.addVertex("H");
graph.addVertex("I");
graph.addEdge("A", "D"); graph.addEdge("D", "B"); graph.addEdge("D", "E"); graph.addEdge("B", "C");
graph.addEdge("D", "C"); graph.addEdge("E", "F"); graph.addEdge("F", "G"); graph.addEdge("G", "A");
graph.addEdge("G", "H"); graph.addEdge("E", "I"); graph.addEdge("I", "F");
// zavolání metody pro Depth First procházení (procházet se začne od vertexu D)
const vysledek = graph.DFRecursive("D");
console.log("Graph se procházel v tomto pořadí:");
console.log(vysledek);
Depth First Traversing - iterativně
Předchozí ukázka ukazovala Depth First procházení s použitím rekurze. Jde to ale provést i bez ní, budeme k tomu ale potřebovat Stack, který jsme si vytvářeli v části Stack a Queue.
Iterativní verze Depth First procházení funguje tak, že se na začátku do stacku přidá vertex, od kterého se má graph začít procházet a označí se jako navštívený. Poté se ze stacku postupně získávají vertexy a vertexy, které jsou s nimi propojeny a ještě nebyly navštíveny se přidávají do stacku. To probíhá tak dlouho, dokud se stack nevyprázdní.
U iterativní verze Depth First procházení se budou vertexy procházet v jiném pořadí než u rekurzivní verze, pořád se ale jedná o Depth First procházení.
class Graph {
/* ... */
// metoda pro Depth First procházení (iterativní verze)
DFIterative(startVertex) {
// vytvoření stacku
const stack = new Stack();
// do tohoto pole se budou postupně ukládat navštívené vertexy
const result = [];
// v tomto objektu se budou ukládat vertexy, které již byly navštíveny
const visited = {};
// tato proměnná bude uchovávat vertex, který se momentálně prochází
let currentVertex;
// startovní vertex se přidá do stacku a označí se jako navštívený
stack.push(startVertex);
visited[startVertex] = true;
// následující cyklus bude probíhat tak dlouho, dokud se stack nevyprázdní
while (stack.size !== 0) {
// získání vertexu ze stacku
currentVertex = stack.pop();
// uložení vertexu do pole result
result.push(currentVertex);
// tento cyklus projde všechny vertexy, se kterými je vertex propojen
for (let neighbor of this.adjacencyList[currentVertex]) {
// pokud vertex ještě nebyl navštíven, tak se přidá do stacku a označí se jako navštívený
if (!visited[neighbor]) {
stack.push(neighbor);
visited[neighbor] = true;
}
}
}
// vrácení pole s vertexy
return result;
}
}
// vytvoření graphu
const graph = new Graph();
graph.addVertex("A"); graph.addVertex("B"); graph.addVertex("C"); graph.addVertex("D");
graph.addVertex("E"); graph.addVertex("F"); graph.addVertex("G"); graph.addVertex("H");
graph.addVertex("I");
graph.addEdge("A", "D"); graph.addEdge("D", "B"); graph.addEdge("D", "E"); graph.addEdge("B", "C");
graph.addEdge("D", "C"); graph.addEdge("E", "F"); graph.addEdge("F", "G"); graph.addEdge("G", "A");
graph.addEdge("G", "H"); graph.addEdge("E", "I"); graph.addEdge("I", "F");
// zavolání metody pro Depth First procházení (procházet se začne od vertexu D)
const vysledek = graph.DFIterative("D");
console.log("Graph se procházel v tomto pořadí:");
console.log(vysledek);
Breadth First Traversing
Druhý způsob, který si pro procházení graphu ukážeme, je Breadth First. U graphu Breadth First znamená nejdříve procházet všechny propojené vertexy vertexu a až poté pokračovat dále.
Kód pro Breadth First procházení je hodně podobný iterativní verzi Depth First procházení. Jediný rozdíl je v tom, že se namísto stacku používá queue.
class Graph {
/* ... */
// metoda pro Breadth First procházení
BF(startVertex) {
// vytvoření queue
const queue = new Queue();
// do tohoto pole se budou postupně ukládat navštívené vertexy
const result = [];
// v tomto objektu se budou ukládat vertexy, které již byly navštíveny
const visited = {};
// tato proměnná bude uchovávat vertex, který se momentálně prochází
let currentVertex;
// startovní vertex se přidá do queue a označí se jako navštívený
queue.enqueue(startVertex);
visited[startVertex] = true;
// následující cyklus bude probíhat tak dlouho, dokud se queue nevyprázdní
while (queue.size !== 0) {
// získání vertexu z queue
currentVertex = queue.dequeue();
// uložení vertexu do pole result
result.push(currentVertex);
// tento cyklus projde všechny vertexy, se kterými je vertex propojen
for (let neighbor of this.adjacencyList[currentVertex]) {
// pokud vertex ještě nebyl navštíven, tak se přidá do queue a označí se jako navštívený
if (!visited[neighbor]) {
queue.enqueue(neighbor);
visited[neighbor] = true;
}
}
}
// vrácení pole s vertexy
return result;
}
}
// vytvoření graphu
const graph = new Graph();
graph.addVertex("A"); graph.addVertex("B"); graph.addVertex("C"); graph.addVertex("D");
graph.addVertex("E"); graph.addVertex("F"); graph.addVertex("G"); graph.addVertex("H");
graph.addVertex("I");
graph.addEdge("A", "D"); graph.addEdge("D", "B"); graph.addEdge("D", "E"); graph.addEdge("B", "C");
graph.addEdge("D", "C"); graph.addEdge("E", "F"); graph.addEdge("F", "G"); graph.addEdge("G", "A");
graph.addEdge("G", "H"); graph.addEdge("E", "I"); graph.addEdge("I", "F");
// zavolání metody pro Breadth First procházení (procházet se začne od vertexu D)
const vysledek = graph.BF("D");
console.log("Graph se procházel v tomto pořadí:");
console.log(vysledek);