View
122
Download
0
Category
Preview:
Citation preview
ACM ICPC Praktikum
Kapitel 9: Graphdurchlauf
Übersicht
• Arten von Graphen
• Datenstrukturen für Graphen
• Breitensuche
• Tiefensuche
• Zusammenhangskomponenten
• Topologische Sortierung
Arten von Graphen
• Ein Graph G=(V,E) besteht aus einer Kontenmenge V und Kantenmenge E.
• G ungerichtet: E µ { {u,v} | u,v 2 V}
• Beispiel eines ungerichteten Graphen:
KnotenKante
Arten von Graphen
• G gerichtet: E µ V £ V
• Beispiel eines gerichteten Graphen:
• G gewichtet: Gewichtsfunktion für Knoten oder Kanten
Arten von Graphen
• G is azyklisch, wenn es keinen (gerichteten) Kreis hat, und sonst zyklisch
• Beispiel eines gerichteten azyklischen Graphen (in der Literatur oft als DAG bez.)
Arten von Graphen
• G heißt einfach, wenn keine Kante doppelt vorkommt
• Beispiel eines nicht-einfachen Graphen:
• G ist beschriftet, falls die Knoten/Kanten Namen haben, sonst unbeschriftet
Datenstrukturen für Graphen
• G=(V,E) enthalte n Knoten und m Kanten• Adjazenzmatrix: Verwende n £ n-Matrix
A[i,j] 2 {0,1} und setze A[i,j] auf 1 genau dann, wenn (i,j) bzw. {i,j} in E.Geeignet für dichte Graphen, d.h. m groß
• Array von Adjazenzlisten: Vewende Array V der Größe n. V[i] speichert die Liste der benachbarten Knoten für Knoten i.Geeignet für dünne Graphen, d.h. m klein
Datenstrukturen für Graphen
• Array von Kanten: Verwende Array der Größe m, um alle Kanten abzuspeichern.Geeignet für sehr dünne Graphen.
• Reine Pointerstruktur: Jeder Knoten ist ein Objekt mit Pointern, die Kanten repräsentieren, zu anderen Knoten.Geeignet für dynamische Graphen.
Beispiel für Datenstruktur1. #define MAXV 100 /* maximum number of vertices */2. #define MAXDEGREE 50 /* maximum outdegree of a vertex */
3. typedef struct {4. int edges[MAXV+1][MAXDEGREE]; /* adjacency info */5. int degree[MAXV+1]; /* outdegree of each vertex */6. int nvertices; /* number of vertices in the graph */7. int nedges; /* number of edges in the graph */8. } graph;
9. initialize_graph(graph *g)10. {11. int i; /* counter */
12. g -> nvertices = 0;13. g -> nedges = 0;
14. for (i=1; i<=MAXV; i++) g->degree[i] = 0;15. }
Beispiel für Datenstruktur1. read_graph(graph *g, bool directed)2. {3. int i; /* counter */4. int m; /* number of edges */5. int x, y; /* vertices in edge (x,y) */
6. initialize_graph(g);
7. scanf("%d %d",&(g->nvertices),&m);
8. for (i=1; i<=m; i++) {9. scanf("%d %d",&x,&y);10. insert_edge(g,x,y,directed);11. }12. }
Beispiel für Datenstruktur1. insert_edge(graph *g, int x, int y, bool directed)2. {3. if (g->degree[x] > MAXDEGREE)4. printf("Warning: insertion(%d,%d) exceeds max degree\
n",x,y);
5. g->edges[x][g->degree[x]] = y;6. g->degree[x] ++;
7. if (directed == FALSE)8. insert_edge(g,y,x,TRUE);9. else10. g->nedges ++;11.}
Beispiel für Datenstruktur1. delete_edge(graph *g, int x, int y, bool directed)2. {3. int i; /* counter */
4. for (i=0; i<g->degree[x]; i++) 5. if (g->edges[x][i] == y) {6. g->degree[x] --;7. g->edges[x][i] = g->edges[x][g->degree[x]];
8. if (directed == FALSE)9. delete_edge(g,y,x,TRUE);
10. return;11. }
12. printf("Warning: deletion(%d,%d) not found in g.\n",x,y);13. }
Beispiel für Datenstruktur
1. print_graph(graph *g)2. {3. int i,j; /* counters */
4. for (i=1; i<=g->nvertices; i++) {5. printf("%d: ",i);6. for (j=0; j<g->degree[i]; j++)7. printf(" %d",g->edges[i][j]);8. printf("\n");9. }10. }
Breitensuche
• Problem: durchsuche Graph G=(V,E) systematisch nach Eigenschaften
• Lösung: Breitensuche (breadth-first-search, BFS) oder Tiefensuche (depth-first-search, DFS). Jeder besuchte Knoten bzw. jede besuchte Kante wird markiert, um doppeltes Besuchen zu vermeiden.
Breitensuche1. bool processed[MAXV]; /* which vertices have been processed */2. bool discovered[MAXV]; /* which vertices have been found */3. int parent[MAXV]; /* discovery relation */
4. bool finished = FALSE; /* if true, cut off search immediately */
5. initialize_search(graph *g)6. {7. int i; /* counter */
8. for (i=1; i<=g->nvertices; i++) {9. processed[i] = discovered[i] = FALSE;10. parent[i] = -1;11. }12. }
Breitensuche1. bfs(graph *g, int start)2. {3. queue q; /* queue of vertices to visit */4. int v; /* current vertex */5. int i; /* counter */
6. init_queue(&q);7. enqueue(&q,start);8. discovered[start] = TRUE;
9. while (empty(&q) == FALSE) {10. v = dequeue(&q);11. process_vertex(v);12. processed[v] = TRUE;13. for (i=0; i<g->degree[v]; i++) 14. if (valid_edge(g->edges[v][i]) == TRUE) {15. if (discovered[g->edges[v][i]] == FALSE) {16. enqueue(&q,g->edges[v][i]);17. discovered[g->edges[v][i]] = TRUE;18. parent[g->edges[v][i]] = v;19. }20. if (processed[g->edges[v][i]] == FALSE) 21. process_edge(v,g->edges[v][i]);22. }23. }24. }
Breitensuche - Demo1. process_vertex(int v)2. { printf("processed vertex %d\n",v); }
3. process_edge(int x, int y)4. { printf("processed edge (%d,%d)\n",x,y); }
5. bool valid_edge(int e)6. { return (TRUE); }
7. main()8. {9. graph g;10. int i;
11. read_graph(&g,FALSE);12. print_graph(&g);13. initialize_search(&g);14. bfs(&g,1);15. for (i=1; i<=g.nvertices; i++) printf(" %d",parent[i]);16. printf("\n");17. for (i=1; i<=g.nvertices; i++) find_path(1,i,parent);18. printf("\n");19. }
Anwendung: Suche nach Pfad
• Problem: finde Pfad von „start” nach “end”.
1. find_path(int start, int end, int parents[])2. {3. if ((start == end) || (end == -1))4. printf("\n%d",start);5. else {6. find_path(start,parents[end],parents);7. printf(" %d",end);8. }9. }
Tiefensuche1. dfs(graph *g, int v)2. {3. int i; /* counter */4. int y; /* successor vertex */
5. if (finished) return; /* allow for search termination */
6. discovered[v] = TRUE;7. process_vertex(v);
8. for (i=0; i<g->degree[v]; i++) {9. y = g->edges[v][i];10. if (valid_edge(g->edges[v][i]) == TRUE) {11. if (discovered[y] == FALSE) {12. parent[y] = v;13. dfs(g,y);14. } else 15. if (processed[y] == FALSE)16. process_edge(v,y);17. }18. if (finished) return;19. }
20. processed[v] = TRUE;21. }
Tiefensuche - Demo1. process_vertex(int v)2. { printf("processed vertex %d\n",v); }
3. process_edge(int x, int y)4. {5. if (parent[x] == y) printf("processed tree edge (%d,%d)\n",x,y);6. else printf("processed back edge (%d,%d)\n",x,y);7. }
8. bool valid_edge(int e)9. { return (TRUE); }
10. main()11. {
graph g;12. int i;
13. read_graph(&g,FALSE);14. print_graph(&g);15. initialize_search(&g);16. dfs(&g,1);
17. for (i=1; i<=g.nvertices; i++) find_path(1,i,parent);18. printf("\n");19. }
Anwendung 1: suche Kreis
• Problem: suche nach Kreis in ungerichtetem Graph
1. process_edge(int x, int y)2. {3. if (parent[x] != y) { /* found back edge! */4. printf(“Cycle from %d to %d:”, y, x);5. find_path(y,x,parent);6. finished = TRUE;7. } }
8. process_vertex(int v) { }
Anwendung 2: Zusammenhangskomponenten
• Problem: finde Zusammenhangskomponenten in ungerichtetem Graph
1. connected_components(graph *g)2. {3. int c; /* component number */4. int i; /* counter */
5. initialize_search(g);6. c = 0;7. for (i=1; i<=g->nvertices; i++)8. if (discovered[i] == FALSE) {9. c = c+1;10. printf(“Component %d: “, c);11. dfs(g,i);12. printf(“\n”);13. } }
14. process_vertex(int v) { print(“ %d”, v); }
15. process_edge(int x, int y) { }
Anwendung 3: Topologisches Sortieren
• Problem: sortiere Knoten in Reihe s, so dass für jede Kante (i,j) gilt: s(i) < s(j)
• Lösung:
1. compute_indegrees(graph *g, int in[])2. {3. int i,j; /* counters */
4. for (i=1; i<=g->nvertices; i++) in[i] = 0;
5. for (i=1; i<=g->nvertices; i++) 6. for (j=0; j<g->degree[i]; j++) in[ g->edges[i][j] ] ++;7. }
Anwendung 3: Topologisches Sortieren
1. topsort(graph *g, int sorted[])2. {3. int indegree[MAXV]; /* indegree of each vertex */4. queue zeroin; /* vertices of indegree 0 */5. int x, y; /* current and next vertex */6. int i, j; /* counters */
7. compute_indegrees(g,indegree);8. init_queue(&zeroin);9. for (i=1; i<=g->nvertices; i++)10. if (indegree[i] == 0) enqueue(&zeroin,i);
11. j=0;12. while (empty(&zeroin) == FALSE) {13. j = j+1;14. x = dequeue(&zeroin);15. sorted[j] = x;16. for (i=0; i<g->degree[x]; i++) {17. y = g->edges[x][i];18. indegree[y] --;19. if (indegree[y] == 0) enqueue(&zeroin,y);20. }21. }
22. if (j != g->nvertices)23. printf("Not a DAG -- only %d vertices found\n",j);24. }
Anwendung 3: Topologisches Sortieren
1. main()2. {3. graph g;4. int out[MAXV];5. int i;
6. read_graph(&g,TRUE);7. print_graph(&g);
8. topsort(&g,out);
9. for (i=1; i<=g.nvertices; i++)10. printf(" %d",out[i]);11. printf("\n");
12. }
Recommended