Graph

V této části se podíváme na Graph. Jedná se o velmi užitečnou datovou strukturu, která má mnoho použití.

Co je to Graph

Graph je datová struktura, skládající se z nodes, které jsou spolu různě propojeny. Mohou být propojeny jakkoliv, neexistuje žádné pravidlo jak by měli být propojeny. U linked listu byly nodes propojeny za sebou, u tree nodes tvořili stromovou strukturu, ale u graphu mohou být propojeny různě.

Graph má různá využití. Například Google Mapy používají graph pro nalezení nejkratší cesty z jednoho místa na druhé. Uživatelé sociálních sítí také představují graph. Mají různé přátele, kteří mají další přátele a dohromady tedy tvoří v podstatě graph.

Následující ukázka ukazuje, jak si můžete graph například představit.

Terminologie

Existuje pár pojmů, které se u graphů používají. Některé z nich možná v této části použiji. Zde jsou vysvětleny:

• vertex - představuje node graphu
• edge - propojení mezi dvěma vertexy
• weighted/unweighted - graphy, které mají u edgů přiřazené hodnoty jsou weighted, a ty které u edgů nemají přiřazené hodnoty jsou unweighted
• directed/undirected - u undirected graphu jsou vertexy propojeny oběma směry; u directed graphu jsou vertexy propojeny jen jedním směrem

Typy Graphů

Existují různé typy graphů. Zde se můžete podívat na jejich seznam. Tady si hlavně ukážeme, co je to directed/undirected graph a weighted/unweighted graph, a že třeba i Tree je graph.

Tree

Mezi graphy se dá zařadit datová struktura Tree, o které jste se mohli dočíst v části Binary Search Tree. Jedná se o graph, ve kterém jsou dva vertexy vždy propojeny jen jednou cestou. Neexistuje jiná cesta, jak se dostat z jednoho vertexu na nějaký jiný.

Weighted Graph

Pokud mají edge graphu přiřazenou hodnotu, tak se jedná o weighted graph.

Directed Graph

Pokud jsou vertexy v graphu propojeny jen jedním směrem, tak se jedná o directed graph.

Jakým způsobem je Graph reprezentován

Pro reprezentaci Graphu existují dva standardní způsoby: Adjacency List a Adjacency Matrix. Oba mají své výhody a nevýhody.

Adjacency Matrix

Jedním ze způsobů jak reprezentovat graph, je použít tabulku (matici) ve které si zaznamenáváme, které vertexy jsou spolu propojeny. Takovou tabulku si můžeme vytvořit jako pole polí.

Níže můžete vidět tabulku a pod ní graficky zobrazený graph. Na místech, kde je zapsaná 1 jsou vertexy propojeny. Tam kde je zapsaná 0 vertexy nejsou propojeny.

Adjacency List

Druhý způsob pro reprezentaci graphu je Adjacency List. Tento způsob používá pro ukládání propojení vertexů namísto matice linked list nebo pole. V tomto poli (nebo linked listu) je pro každý vertex vyhrazeno pole (nebo linked list), ve kterém se ukládá s jakými vertexy je vertex propojen.

[
    [1, 5], // vertex 0 je propojen s vertexy 1 a 5
    [0, 2], // vertex 1 je propojen s vertexy 0 a 2
    [1, 3], // vertex 2 je propojen s vertexy 1 a 3
    [2, 4], // vertex 3 je propojen s vertexy 2 a 4
    [3, 5], // vertex 4 je propojen s vertexy 3 a 5
    [4, 0] // vertex 5 je propojen s vertexy 4 a 0
]

Ukládání polí obsahující propojení vertexu s vertexy uvnitř pole se hodí, když máme jako vertexy hodnoty, které jsou čísla představující indexy tohoto pole. Pokud ale máme jako vertexy jiné hodnoty než jsou indexy pole, tak můžeme namísto pole použít Hash Table. Můžeme tedy pole (nebo linked listy) obsahující propojení vertexu s vertexy ukládat v objektu.

{
    A: ["B", "F"], // vertex A je propojen s vertexy B a F
    B: ["A", "C"], // vertex B je propojen s vertexy A a C
    C: ["B", "D"], // vertex C je propojen s vertexy B a D
    D: ["C", "E"], // vertex D je propojen s vertexy C a E
    E: ["D", "F"], // vertex E je propojen s vertexy D a F
    F: ["E", "A"] // vertex F je propojen s vertexy E a A
}

Adjacency Matrix vs. Adjacency List

Oba způsoby mají své výhody a nevýhody. Zde je jejich porovnání:

Vytvoření základu Graphu

Pro ukázku graphu si vytvoříme undirected graph, jeho vertexy tedy budou propojeny oběma směry. K jeho reprezentaci použijeme Adjacency List, který se u většinu graphů hodí více než Adjacency Matrix. Vytvoříme si třídu jménem Graph, která bude Adjacency List uchovávat. Nic víc v této třídě zatím nepotřebujeme, později si do ní přidáme metody pro interakci s graphem.

// třída pro Graph
class Graph {
    constructor() {
        this.adjacencyList = {};
    }
}

Metoda addVertex

Pro přidání vertexu do graphu si vytvoříme metodu addVertex. Bude obsahovat pouze jeden řádek, který pro vertex vytvoří v adjacency listu pole. Toto pole bude sloužit k uchování vertexů, ke kterým se vertex napojí.

Pravděpodobně by bylo lepší použít namísto pole linked list, ale pro jednoduchost jsem použil jen pole. Myslím že byste si kód zvládli předělat, pokud byste chtěli namísto pole použít linked list.

class Graph {
    /* ... */

    // metoda pro přidání vertexu do graphu
    addVertex(vertex) {
        // pokud vertex v graphu ještě není, tak se pro něj v adjacency listu vytvoří pole
        if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
    }
}

// vytvoření graphu
const graph = new Graph();

// přidání vertexů do graphu
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
graph.addVertex("F");

Metoda addEdge

Pro propojení dvou vertexů ve graphu si vytvoříme metodu addEdge. Tato metoda vezme jako parametr dva vertexy a vzájemně je propojí jejich přidáním do adjacency listu. Do pole prvního vertexu se přidá druhý vertex a do pole druhého vertexu se přidá první vertex.

class Graph {
    /* ... */

    // metoda pro propojení dvou vertexů
    addEdge(v1, v2) {
        // pokud se jeden z předaných vertexů v graphu nenachází, tak se metoda ukončí
        if (!this.adjacencyList[v1] || !this.adjacencyList[v2]) return;

        // pokud předané vertexy nejsou propojeny, tak se propojí
        if (!this.adjacencyList[v1].includes(v2)) this.adjacencyList[v1].push(v2);
        if (!this.adjacencyList[v2].includes(v1)) this.adjacencyList[v2].push(v1);
    }
}

// vytvoření graphu
const graph = new Graph();

// přidání vertexů do graphu
graph.addVertex("A"); graph.addVertex("B"); graph.addVertex("C");
graph.addVertex("D"); graph.addVertex("E"); graph.addVertex("F");

// propojení vertexů
graph.addEdge("A", "B");
graph.addEdge("B", "C");
graph.addEdge("C", "D");
graph.addEdge("D", "F");
graph.addEdge("D", "E");
graph.addEdge("F", "E");
graph.addEdge("E", "A");
graph.addEdge("B", "D");

Metoda removeEdge

Pro odstranění propojení mezi dvěma vertexy si vytvoříme metodu removeEdge. Tato metoda vezme jako parametr dva vertexy. V adjacency listu pro první vertex odstraní druhý vertex a v adjacency listu pro druhý vertex odstraní první vertex.

V kódu jsou použity metody findIndex a splice, které se týkají polí. Pokud nevíte jak fungují, můžete se podívat třeba zde: findIndex, splice.

class Graph {
    /* ... */

    // metoda pro odstranění propojení mezi dvěma vertexy
    removeEdge(v1, v2) {
        // pokud se jeden z předaných vertexů v graphu nenachází, tak se metoda ukončí
        if (!this.adjacencyList[v1] || !this.adjacencyList[v2]) return;

        // získání indexu vertexu v2 v adjacency listu pro vertex v1
        let index = this.adjacencyList[v1].findIndex((val) => val === v2);
        // odstranění propojení s vertexem na získaném indexu
        if (index !== -1) this.adjacencyList[v1].splice(index, 1);

        // získání indexu vertexu v1 v adjacency listu pro vertex v2
        index = this.adjacencyList[v2].findIndex((val) => val === v1);
        // odstranění propojení s vertexem na získaném indexu
        if (index !== -1) this.adjacencyList[v2].splice(index, 1);
    }
}

// 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.addEdge("A", "B"); graph.addEdge("B", "C"); graph.addEdge("C", "D"); graph.addEdge("D", "F");
graph.addEdge("D", "E"); graph.addEdge("F", "E"); graph.addEdge("E", "A"); graph.addEdge("B", "D");

// odstranění propojení mezi některými vertexy
graph.removeEdge("A", "B");
graph.removeEdge("B", "D");
graph.removeEdge("D", "F");

Metoda removeVertex

Pro odstranění vertexu graphu si vytvoříme metodu removeVertex. Tato metoda přijme vertex, který se má odstranit, odstraní jeho propojení s jinými vertexy v graphu pomocí metody removeEdge, a odstraní jeho pole z adjacency listu pomocí operátoru delete.

Operátor delete v JavaScriptu slouží k odstranění vlastnosti objektu.

class Graph {
    /* ... */

    // metoda pro odstranění vertexu
    removeVertex(vertex) {
        // tento cyklus odstraní propojení se všemi vertexy, se kterými je odstraňovaný vertex propojen
        while (this.adjacencyList[vertex].length) {
            // získání a odstranění vertexu z konce pole odstraňovaného vertexu v adjacency listu
            const adjacentVertex = this.adjacencyList[vertex].pop();
            // použití metody removeEdge pro odstranění propojení mezi vertexy
            this.removeEdge(vertex, adjacentVertex);
        }
        // odstranění vertexu z graphu (odstranění jeho pole v adjacency listu)
        delete this.adjacencyList[vertex];
    }
}

// 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.addEdge("A", "B"); graph.addEdge("B", "C"); graph.addEdge("C", "D"); graph.addEdge("D", "F");
graph.addEdge("D", "E"); graph.addEdge("F", "E"); graph.addEdge("E", "A"); graph.addEdge("B", "D");

// odstranění vertexů z graphu
graph.removeVertex("F");
graph.removeVertex("B");

Další metody si pro náš graph v této části již vytvářet nebudeme. Vytvořili jsme si metody pro přidávání a odstraňování vertexů a edgů. Následující část bude o procházení graphu, a tam si pro náš graph vytvoříme ještě další metody.