Co je struktura dat grafu?

A Graf je nelineární datová struktura skládající se z vrcholů a hran. Vrcholy jsou někdy také označovány jako uzly a hrany jsou čáry nebo oblouky, které spojují libovolné dva uzly v grafu. Formálněji se graf skládá ze sady vrcholů ( V ) a sadu hran ( A ). Graf je označen G(V, E) .

jinak pokud java

Reprezentace grafu

Zde jsou dva nejběžnější způsoby znázornění grafu:

1. Matice sousedství
2. Seznam sousedství

Matice sousedství

Matice sousedství je způsob reprezentace grafu jako matice boolean (0 a 1).

Předpokládejme, že existují n vrcholy v grafu Vytvořte tedy 2D matici adjMat[n][n] mající rozměr n x n.

• Pokud existuje hrana z vrcholu i na j , značka adjMat[i][j] tak jako 1 .
• Pokud z vrcholu není žádná hrana i na j , značka adjMat[i][j] tak jako 0 .

Reprezentace neorientovaného grafu k matici sousedství:

Níže uvedený obrázek ukazuje neorientovaný graf. Zpočátku je celý Matrix inicializován 0 . Pokud existuje hrana od zdroje k cíli, vložíme 1 v obou případech ( adjMat[cíl] a adjMat [ destinace]) protože můžeme jít oběma směry.

Undirected Graph to Adjacency Matrix

Reprezentace řízeného grafu k matici sousedství:

Níže uvedený obrázek ukazuje orientovaný graf. Zpočátku je celý Matrix inicializován 0 . Pokud existuje hrana od zdroje k cíli, vložíme 1 pro toho konkrétního adjMat[cíl] .

Directed Graph to Adjacency Matrix

Seznam sousedství

Pole seznamů se používá k uložení hran mezi dvěma vrcholy. Velikost pole se rovná počtu vrcholy (tj. n) . Každý index v tomto poli představuje určitý vrchol v grafu. Záznam na indexu i pole obsahuje propojený seznam obsahující vrcholy, které sousedí s vrcholem i .

Předpokládejme, že existují n vrcholy v grafu Vytvořte tedy an pole seznamu velikosti n tak jako adjList[n].

• adjList[0] bude mít všechny uzly, které jsou připojeny (soused) k vrcholu 0 .
• adjList[1] bude mít všechny uzly, které jsou připojeny (soused) k vrcholu 1 a tak dále.

Reprezentace neorientovaného grafu k seznamu sousedství:

Níže uvedený neorientovaný graf má 3 vrcholy. Vytvoří se tedy pole seznamu o velikosti 3, kde každý index představuje vrcholy. Nyní má vrchol 0 dva sousedy (tj. 1 a 2). Takže vložte vrchol 1 a 2 na indexy 0 pole. Podobně pro vrchol 1 má dva sousedy (tj. 2 a 0), takže vložte vrcholy 2 a 0 na indexy 1 pole. Podobně pro vrchol 2 vložte jeho sousedy do pole seznamu.

Neorientovaný graf na seznam sousedství

Reprezentace řízeného grafu k seznamu sousedství:

Níže vedený graf má 3 vrcholy. Vytvoří se tedy pole seznamu o velikosti 3, kde každý index představuje vrcholy. Nyní vrchol 0 nemá žádné sousedy. Pro vrchol 1 má dva sousedy (tj. 0 a 2) Takže vložte vrcholy 0 a 2 na indexy 1 pole. Podobně pro vrchol 2 vložte jeho sousedy do pole seznamu.

Nasměrovaný graf na seznam sousedství