PI (Fach) / Graphen: Repräsentation (Lektion)
In dieser Lektion befinden sich 4 Karteikarten
Graphen: Repräsentation
Diese Lektion wurde von blace erstellt.
Diese Lektion ist leider nicht zum lernen freigegeben.
- Was ist eine Adjazenz-Matrix? Erläutere an einem geeigneten Beispiel. Eine Adjazenz-Matrix ist eine Boolsche Matrix, welche die adjazenz der Knoten im Graphen beschreibt. Dabei wird die Matrix mit A0(aij) beschrieben, sie hat die Größe |V| X |V| also sind i,j ∈{1,.....,|V|} hierbei sind aij true falls (i,j) ∈ E und falls falls (i,j) ∉ E Mit dem Beispiel aus der Volresung also einem Graphen, der das Element 1 ohne asugehende Kante, das Elment 2 mit 2 ausgehenden nach 1 und 3, 3 mit einem nach 4 und 4 mit einem nach 1, sowie 5 welches eine zu sich selber hat wäre die matrix also: i/j 1 2 3 4 5 1 false false false false false 2 true false true false false 3 false false false true false 4 true false false false false 5 false false false false true
- Welche Vor- und Nachteile hat die Darstellung eines Graphen als Adjazenz-Matrix? Vorteile: übersichtliche Darstellung des Graphen
- Erläutere, wie ein Graph in Form einer Adjazenz-Liste dargestellt werden kann. Wenn man den Graphen mittels einer Adjazenz Liste darstellen möchte, tut man dies, indem die einzelnen Knoten in einem Array dargestellt werden und an die jeweilige Stelle dann eine Liste der Adjazenten Knoten eingetragen wird.
- Wie wird die Darstellung eines Graphen in Form einer Adjazenz-Liste in Java realisiert? public class AdjList { private static class Edge { public final int target; public Edge next; public Edge(final int pTarget, final Edge pNext) { target = pTarget; next = pNext; } } private final Edge[ ] a; public AdjList(final int nodes) { a = new Edge[nodes]; } public boolean adjacent(final int i, final int j) { Edge e = a[i]; while (e != null && e.goal != j) { e = e.next; } return e != null; } public void addEdge(final int i, final int j) { if (!adjacent(i, j)) { a[i] = new Edge(j, a[i]); } }}