Datenstrukturen - Graph
Ein Graph ist eine allgemeinere nichtlineare Datenstruktur, die verwendet wird, um komplexe „Viele-zu-viele“-Beziehungen zwischen Elementen darzustellen, und aus Knoten und Kanten besteht, die die Knoten verbinden.
Grundkonzepte von Graphen
GraphentypenGraphentypen — ungerichteter Graph, gerichteter Graph, gewichteter Graph
Ungerichteter Graph
0
—1
Kanten haben keine Richtung; Verbindungen sind wechselseitig.
Beispiel: Freundschaftsbeziehungen in sozialen Netzwerken
Beispiel: Freundschaftsbeziehungen in sozialen Netzwerken
Gerichteter Graph
0
→1
Kanten haben eine Richtung; Verbindungen sind einseitig.
Beispiel: Folgebeziehungen, Webseiten-Links
Beispiel: Folgebeziehungen, Webseiten-Links
Gewichteter Graph
0
51
Kanten tragen Gewichte (Distanz/Kosten)
Beispiel: Kartennavigation, Netzwerklatenz
Beispiel: Kartennavigation, Netzwerklatenz
Methoden zur Graphspeicherung
Vergleich der SpeichermethodenAdjazenzmatrix vs. Adjazenzliste
Adjazenzmatrix
SpeicherkomplexitätO(V²)
Prüfen, ob zwei Knoten verbunden sindO(1)
Benachbarte Knoten durchlaufenO(V)
Geeignet für: Dichte Graphen · int graph[V][V]
Adjazenzliste
SpeicherkomplexitätO(V+E)
Prüfen, ob zwei Knoten verbunden sindO(degree)
Benachbarte Knoten durchlaufenO(degree)
Geeignet für: Dünn besetzte Graphen · Array aus verketteten Listen
Graphdurchlauf
DFS vs BFS — Durchlauf beginnend bei Knoten 0
DFS Tiefensuche
0→
1→
3→
4→
2→
5
Einen Pfad bis zum Ende verfolgen und dann zurückverfolgen
Implementierung: Rekursion / Stack | Geeignet für Pfadsuche, topologische Sortierung
BFS Breitensuche
0→
1→
2→
3→
4→
5
Schichtweise erweitern; Knoten auf derselben Ebene werden zuerst besucht
Implementierung: Warteschlange | Natürlich geeignet für kürzeste Pfade in ungewichteten Graphen
Beispiele
#include <stdio.h>
#include <stdbool.h>
#define V 6 /* Anzahl der Knoten */
/* Graph dargestellt durch Adjazenzmatrix */
int graph[V][V] = {
{0,1,1,0,0,0}, /* Adjazenzbeziehungen von Knoten 0 */
{1,0,0,1,1,0}, /* Knoten 1 */
{1,0,0,0,1,0}, /* Knoten 2 */
{0,1,0,0,0,1}, /* Knoten 3 */
{0,1,1,0,0,1}, /* Knoten 4 */
{0,0,0,1,1,0} /* Knoten 5 */
};
bool visited[V];
/* DFS: Tiefensuche, rekursive Implementierung Eigenschaften: Folgt einem Pfad bis zum Ende und geht zurück, geeignet für Pfadsuche und Konnektivitätsprüfung */
/* Aktuellen Knoten besuchen */
void DFS(int v) {
visited[v] = true;
printf("%d ", v); /* Unbesuchte benachbarte Knoten rekursiv besuchen */
for (int i = 0; i < V; i++) {
if (graph[v][i] && !visited[i]) {
DFS(i); /* BFS: Breitensuche, implementiert mit einer Warteschlange Eigenschaften: Erweitert Ebene für Ebene, natürlich geeignet zum Finden kürzester Pfade */
}
}
}
/* Startknoten in die Warteschlange einfügen */
/* Aus der Warteschlange entnehmen */
void BFS(int start) {
bool visited[V] = {false};
int queue[V];
int front = 0, rear = 0;
visited[start] = true;
queue[rear++] = start; /* Benachbarte Knoten in die Warteschlange einfügen */
while (front < rear) {
int v = queue[front++]; /* Besucht-Markierungen initialisieren */
printf("%d ", v);
for (int i = 0; i < V; i++) {
if (graph[v][i] && !visited[i]) {
visited[i] = true;
queue[rear++] = i; "DFS (Start bei Knoten 0): "
}
}
}
}
int main() {
/* Ausgabe: 0 1 3 5 4 2 */
for (int i = 0; i < V; i++) visited[i] = false;
printf("BFS (beginnend bei Knoten 0): ");
DFS(0); /* Ausgabe: 0 1 2 3 4 5 */
printf("\n");
printf(Graph-Anwendungsszenarien);
BFS(0); Szenarien
printf("\n");
return 0;
}
#include <stdbool.h>
#define V 6 /* Anzahl der Knoten */
/* Graph dargestellt durch Adjazenzmatrix */
int graph[V][V] = {
{0,1,1,0,0,0}, /* Adjazenzbeziehungen von Knoten 0 */
{1,0,0,1,1,0}, /* Knoten 1 */
{1,0,0,0,1,0}, /* Knoten 2 */
{0,1,0,0,0,1}, /* Knoten 3 */
{0,1,1,0,0,1}, /* Knoten 4 */
{0,0,0,1,1,0} /* Knoten 5 */
};
bool visited[V];
/* DFS: Tiefensuche, rekursive Implementierung Eigenschaften: Folgt einem Pfad bis zum Ende und geht zurück, geeignet für Pfadsuche und Konnektivitätsprüfung */
/* Aktuellen Knoten besuchen */
void DFS(int v) {
visited[v] = true;
printf("%d ", v); /* Unbesuchte benachbarte Knoten rekursiv besuchen */
for (int i = 0; i < V; i++) {
if (graph[v][i] && !visited[i]) {
DFS(i); /* BFS: Breitensuche, implementiert mit einer Warteschlange Eigenschaften: Erweitert Ebene für Ebene, natürlich geeignet zum Finden kürzester Pfade */
}
}
}
/* Startknoten in die Warteschlange einfügen */
/* Aus der Warteschlange entnehmen */
void BFS(int start) {
bool visited[V] = {false};
int queue[V];
int front = 0, rear = 0;
visited[start] = true;
queue[rear++] = start; /* Benachbarte Knoten in die Warteschlange einfügen */
while (front < rear) {
int v = queue[front++]; /* Besucht-Markierungen initialisieren */
printf("%d ", v);
for (int i = 0; i < V; i++) {
if (graph[v][i] && !visited[i]) {
visited[i] = true;
queue[rear++] = i; "DFS (Start bei Knoten 0): "
}
}
}
}
int main() {
/* Ausgabe: 0 1 3 5 4 2 */
for (int i = 0; i < V; i++) visited[i] = false;
printf("BFS (beginnend bei Knoten 0): ");
DFS(0); /* Ausgabe: 0 1 2 3 4 5 */
printf("\n");
printf(Graph-Anwendungsszenarien);
BFS(0); Szenarien
printf("\n");
return 0;
}
Graph-Anwendungsszenarien
| Kürzester Pfad | Dijkstra, Bellman-Ford (Kartennavigation) |
|---|---|
| Minimaler Spannbaum | Prim, Kruskal (Optimierung der Netzwerkverkabelung) |
| Topologische Sortierung | Kahn-Algorithmus (Analyse von Aufgabenabhängigkeiten) |
| Analyse sozialer Netzwerke | PageRank, Community-Erkennung |
| Andere Erweiterungen | KI denkt nach... |