Graf (datová struktura)
Graf je datová struktura, představující abstraktní matematický objekt zvaný graf. Používá se všude tam, kde je potřeba pracovat s navzájem propojenými objekty – například entity a jejich vztahy v databázi, počítače spojené v síti, webové stránky spojené odkazy a podobně.
Implementace
Volba konkrétní implementace závisí na velikosti a struktuře grafu a na míře jeho změny během spuštění programu.
Matice sousednosti
Nejjednodušší reprezentací grafu je matice sousednosti. Oba její rozměry jsou rovny počtu uzlů. Každý prvek matice na pozici X,Y odpovídá počtu hran z uzlu číslo X do uzlu číslo Y. Je-li graf prostý (bez rovnoběžných hran a smyček), stačí k reprezentaci každé dvojice jen jeden bit (má hranu, nemá hranu) a na hlavní diagonále jsou nuly (neobsahuje smyčky). Je-li graf neorientovaný, je matice sousednosti symetrická podél hlavní diagonály.
Obsahuje-li graf mnoho vrcholů a málo hran (řídký graf), je použití matice sousednosti zbytečným plýtváním pamětí. Vlastní matice je reprezentována dvojrozměrným polem, které má pevně daný rozměr. Proto je matice sousednosti nevhodná pro reprezentaci grafů, u kterých se mění počet uzlů.
* Třída představující prostý graf reprezentovaný maticí sousednosti.
* @author Vojtěch Hordějčuk
*/
public class GraphMatrix
{
/**
* matice sousednosti
*/
final private boolean matrix[][];
/**
* příznak, zda je graf orientovaný
*/
final private boolean oriented;
/**
* Vytvoří novou matici sousednosti.
* @param nodeCount počet uzlů
* @param oriented příznak, zda je graf orientovaný
*/
public GraphMatrix (int nodeCount, boolean oriented)
{
// zkontrolovat parametry
if (nodeCount < 1)
{
throw new UnsupportedOperationException ("Count must be higher than zero.");
}
// uložit orientaci
this.oriented = oriented;
// vytvořit dvojrozměrné pole
this.matrix = new boolean[nodeCount][];
for (int i = 0; i < nodeCount; i ++)
{
this.matrix[i] = new boolean[nodeCount];
}
// vynulovat matici
this.reset ();
}
/**
* Odstraní všechny hrany.
*/
public void reset ()
{
for (int y = 0; y < this.matrix.length; y ++)
{
for (int x = 0; x < this.matrix.length; x ++)
{
this.matrix[y][x] = false;
}
}
}
/**
* Přidá hranu z uzlu A do uzlu B. Orientovanost závisí na nastavení grafu.
* @param indexFrom index uzlu A
* @param indexTo index uzlu B
*/
public void addEdge (int indexFrom, int indexTo)
{
// zkontrolovat parametry
if (indexFrom == indexTo)
{
throw new UnsupportedOperationException ("Loop edges are not supported.");
}
if (indexFrom >= this.matrix.length || indexTo >= this.matrix.length)
{
throw new UnsupportedOperationException ("Node index out of range.");
}
if (this.oriented && this.hasEdge (indexTo, indexFrom))
{
throw new UnsupportedOperationException ("Multigraphs are not supported.");
}
// přidat první (dopřednou) hranu
this.matrix[indexFrom][indexTo] = true;
if ( ! this.oriented)
{
// přidat druhou (zpětnou) hranu
this.matrix[indexTo][indexFrom] = true;
}
}
/**
* Zjistí, zda se v grafu nachází hrana z uzlu A do uzlu B.
* @param indexFrom index uzlu A
* @param indexTo index uzlu B
* @return TRUE právě když existuje hrana z uzlu A do uzlu B
*/
public boolean hasEdge (int indexFrom, int indexTo)
{
// zkontrolovat parametry
if (indexFrom == indexTo)
{
return false;
}
if (indexFrom >= this.matrix.length || indexTo >= this.matrix.length)
{
throw new UnsupportedOperationException ("Node index out of range.");
}
// ověřit existenci hrany
return this.matrix[indexFrom][indexTo];
}
/**
* Vrátí počet uzlů.
* @return počet uzlů
*/
public int getNodeCount ()
{
return this.matrix.length;
}
/**
* Vypíše matici sousednosti.
*/
public void print ()
{
// vypsat řádky
for (int y = 0; y < this.matrix.length; y ++)
{
// vypsat sloupce
for (int x = 0; x < this.matrix.length; x ++)
{
System.out.print (this.matrix[y][x] ? 1 : 0);
}
System.out.println ();
}
}
}
zdrojový kód (Java) - zobrazit (3125 znaků)
Ukázka použití:
{
// vytvořit neorientovaný graf se čtyřmi uzly
final GraphMatrix a = new GraphMatrix (4, false);
// přidat tři hrany
a.addEdge (0, 1);
a.addEdge (1, 2);
a.addEdge (1, 3);
// vypsat matici sousednosti
a.print ();
}
zdrojový kód (Java) - zobrazit (275 znaků)
Seznam sousedů
Reprezentace grafu pomocí seznamu sousedů je dynamická. Umožňuje měnit graf během spuštění programu, a to s minimem nadbytečné paměti. Tato reprezentace je vhodná pro velké grafy. Práce s grafem je však pomalejší kvůli režii dynamických datových struktur.
import java.util.Set;
/**
* Třída představující uzel grafu.
* @author Vojtěch Hordějčuk
*/
public class GraphNode
{
/**
* název uzlu
*/
final private String name;
/**
* množina sousedních uzlů
*/
final private Set<GraphNode> neighbours;
/**
* Vytvoří nový uzel.
* @param name jedinečný název uzlu
*/
public GraphNode (final String name)
{
this.name = name;
this.neighbours = new HashSet<GraphNode> ();
}
/**
* Přidá sousední uzel.
* @param node sousední uzel
* @param oriented orientovaná hrana
*/
public void connect (final GraphNode node, boolean oriented)
{
// zkontrolovat parametry
if (node.equals (this))
{
throw new UnsupportedOperationException ("Loop edges are not supported.");
}
// přidat dopřednou hranu
this.neighbours.add (node);
if ( ! oriented)
{
// přidat zpětnou hranu
node.neighbours.add (this);
}
}
/**
* Zjistí, zda vede hrana z tohoto uzlu do uzlu zadaného.
* @param node druhý uzel
* @return TRUE právě když vede hrana z tohoto uzlu do uzlu zadaného
*/
public boolean isConnectedTo (final GraphNode node)
{
return this.neighbours.contains (node);
}
/**
* Vrátí název uzlu.
* @return název uzlu
*/
public String getName ()
{
return this.name;
}
/**
* Vrátí množinu sousedních uzlů.
* @return množina sousedních uzlů
*/
public Set<GraphNode> getNeighbours ()
{
return this.neighbours;
}
@Override
public boolean equals (final Object obj)
{
// porovnat třídu
if ( ! obj.getClass ().equals (this.getClass ()))
{
return false;
}
// přetypovat objekt
final GraphNode other = (GraphNode) obj;
// porovnat název
if ( ! other.name.equals (this.name))
{
return false;
}
return true;
}
@Override
public int hashCode ()
{
return this.name.hashCode ();
}
@Override
public String toString ()
{
// začít názvem uzlu
final StringBuffer buffer = new StringBuffer (this.name + ": ");
// přidat názvy sousedů
for (final GraphNode temp: this.neighbours)
{
buffer.append (temp.getName () + " ");
}
// vrátit bez zbytečných mezer
return buffer.toString ().trim ();
}
}
zdrojový kód (Java) - zobrazit (2330 znaků)
Ukázka použití:
{
// vytvořit všechny uzly
final GraphNode a = new GraphNode ("A");
final GraphNode b = new GraphNode ("B");
final GraphNode c = new GraphNode ("C");
final GraphNode d = new GraphNode ("D");
// přidat hrany
a.connect (b, false);
a.connect (d, false);
b.connect (c, false);
c.connect (a, false);
// vypsat uzly a jejich sousedy
System.out.println (a);
System.out.println (b);
System.out.println (c);
System.out.println (d);
}
zdrojový kód (Java) - zobrazit (499 znaků)