Please enable JavaScript.
Coggle requires JavaScript to display documents.
Graphs, J1 (J2, J3), 0 (2, 4), Algorithm: void toposort(G g, int v, STACK…
Graphs
DFS
Algorithm: void graphTraverse(G g)
- for v ← 0 to n(g) − 1 do
- ----setMark(g, v, UNVISITED);
- for v ← 0 to n(g) − 1 do
- ----if getMark(g, v) = UNVISITED then
- --------DFS(g, v) ;
Algorithm: void DFS(G g, int v)
- preVisit(g, v);
- setMark(g, v, VISITED);
- w ← first(g, v);
- while w < n(g) do
- ----if getMark(g, w) = UNVISITED then
- --------DFS(g, w) ;
- ----w ← next(g, v, w);
- posVisit(g, v);
DFS: topological sorting
Let G be a DAG (directed acyclic graph), find a solution considering the informed prerequisites
- Assumption: u → v means that u is a prerequisite of v
BFS
Algorithm: void graphTraverse(G g)
- for v ← 0 to n(g) − 1 do
- ----setMark(g, v, UNVISITED);
- for v ← 0 to n(g) − 1 do
- ----if getMark(g, v) = UNVISITED then
- --------BFS(g, v) ;
Algorithm: void BFS(G g, int start)
- Q ← create queue();
- enqueue(Q, start);
- setMark(g, start, VISITED);
- while length(Q) > 0 do
- ----v ← dequeue(Q);
- ----preVisit(g, v);
- ----w ← first(g, v);
- ----while w < n(g) do
- --------if getMark(g, w) = UNVISITED then
- ------------setMark(g, w, VISITED);
- ------------enqueue(Q, w);
- --------w ← next(g, v, w);
- ----posVisit(g, v);
-
- Graph: a collection of nodes (vertices), some of them connected by
- edges (arcs) – G = (V, E), where V 6= ∅, and E ∈ V ↔ V
In general
Algorithm: void graphTraverse(G g)
- for v ← 0 to n(g) − 1 do
- ----setMark(g, v, UNVISITED);
- for v ← 0 to n(g) − 1 do
- ----if getMark(g, v) = UNVISITED then
- --------traverse(g, v);
Choosing the most appropriate implementation
- Space efficiency: dense graph vs. sparse graph
- Time efficiency (graph traversal): Θ(| V |² vs. Θ(| V | + | E |)
Operations
- int n(G g);
- int e(G g);
- int first(G g, int v);
- int next(G g, int v, int w);
- void setEdge(G g, int i, int j, int wt);
- void delEdge(G g, int i, int j);
- boolean isEdge(G g, int i, int j);
- int weight(G g, int i, int j);
- void setMark(G g, int v, int val);
- int getMark(G g, int v);
Algorithm: G create graph(int n)
- g.Mark ← new int[n];
- g.matrix ← new int[n][n];
- g.numEdge ← 0;
- return g;
-
Algorithm: int first(G g, int v)
- for i ← 0 to n(g) − 1 do
- ----if g.matrix[v][i] != 0 then return i;
- return n(g);
Algorithm: int next(G g, int v, int w)
- for i ← w + 1 to n(g) − 1 do
- ----if g.matrix[v][i] != 0 then return i;
- return n(g);
Algorithm: void setEdge(G g, int i, int j, int wt)
- if wt = 0 then error ;
- if g.matrix[i][j] = 0 then g.numEdge++;
- g.matrix[i][j] ← wt;
Algorithm: void delEdge(G g, int i, int j)
- if g.matrix[i][j] != 0 then g.numEdge--;
- g.matrix[i][j] ← 0;
Composite type: G
- int[][] matrix ; // adjacency matrix
- int numEdge ; // number of edges
- int[] Mark ; // auxiliary marking array
Possible traversals
- DFS: depth-first search
- BFS: breadth-first search
-
-
Algorithm: void toposort(G g, int v, STACK s)
- setMark(g, v, VISITED);
- w ← first(g, v);
- while w < n(g) do
- ----if getMark(g, w) = UNVISITED then
- --------toposort(g, w, s);
- ----w ← next(g, v, w);
- push(s, v); // we will have in s a solution
s = (bottom) J7, J5, J4, J6, J2, J3, J1 (top)
Let the origin be 0 and the destination be 5, solution = 0 → 2 → 5