In the 18th Century, the Prussian town of Konigsberg (now Kaliningrad) was famous for the seven bridges connecting its two central islands with the banks of the River Pregel, as shown in the diagram.
(* Possible methods of "removal" include: blowing up, weighing down with love-locks until it collapses, blocking permanently with Sydney Buses, etc.)
Answer:It helps to have an annotated version of the bridges map. In the version below, the regions of land are the vertices and the bridges are the edges. There are only four vertices (A = north bank, B = small island, C = large island, D = south bank). Note also that this graph allows multiple edges between two vertices. We label these, so as to be able to distinguish the bridges
No you can't ... but try a few first just to see.
Removing bridge 1 allows starting from C and crossing bridges 3,2,4,7,5,6.
Removing bridge 2 allows starting from C and crossing bridges 3,1,4,7,5,6.
Removing bridge 3 allows starting from B and crossing bridged 1,2,4,7,5,6.
Removing bridge 4 allows starting from A and crossing bridges 1,2,3,7,5,6.
Removing bridge 5 allows starting from C and crossing bridges 4,6,7,3,2,1.
Removing bridge 6 allows starting from A and crossing bridges 4,5,7,3,2,1.
Removing bridge 7 allows starting from A and crossing bridges 1,2,3,4,5,6.
In fact, removing any one bridge allows you to solve the problem.
See previous answer, which gives one path for each case. Other paths also exist.
This, of course, is an instance of the Euler Path problem.
Graph Search - Comparing DFS and BFS
Show what would be printed by the iterative depth-first and breadth-first traversals in the functions below on the following graph:
When choosing which neighbour to visit next, always choose the smallest unvisited neighbour. Show the state of the Stack (DFS) or Queue (BFS) explicitly in each step.
void dfs (Graph g, Edge e) {
int i;
Stack s = newStack();
StackPush (s,e);
while (!StackIsEmpty(s)) {
e = StackPop(s);
if (pre[e.w] == -1) {
pre[e.w] = count++;
st[e.w] = e.v;
for (i = 0; i < g->nV; i++) {
if ((g->edges[e.w][i] == 1)&&
(pre[i] == -1)) {
StackPush (s,mkEdge(g,e.w,i));
}
}
}
}
}
|
void bfs (Graph g, Edge e) {
int i;
Queue q = newQueue();
QueueJoin(q,e);
while (!QueueIsEmpty(q)) {
e = QueueLeave(q);
if(pre[e.w] == -1){
pre[e.w] = count++;
st[e.w] = e.v;
for (i = 0; i < g->nV; i++){
if ((g->edges[e.w][i] != 0)&&
(pre[i] == -1)) {
QueueJoin (q,mkEdge(g,e.w,i));
}
}
}
}
}
|
Show the results for each of the following function calls:
dfs(g,0); dfs(g,3); bfs(g,0); bfs(g,3);
For dfs(g,0):
Order# ST Pre(Visited) Stack (top at left)
- - - Push(0,0) {(0,0)}
0 0 0 Pop(0,0) Push(0,1) {(0,1)}
1 0 1 Pop(0,1) Push{(1,2)(1,3)(1,4)} {(1,2)(1,3)(1,4)}
2 2 2 Pop(1,2) Push{(2,3)(2,5)} {2,3)(2,5)(1,3)(1,4)}
3 3 3 Pop(2,3) Push{(3,4)(3,5)} {(3,4)(3,5)(2,5)(1,3)(1,4)}
4 4 4 Pop(3,4) Push{(4,5)} {(4,5)(3,5)(2,5)(1,3)(1,4)}
5 5 5 Pop(4,5) Push{(5,6),(5,7)} {(5,6)(5,7)(3,5)(2,5)(1,3)(1,4)}
6 6 6 Pop(5,6) - {(5,7)(3,5)(2,5)(1,3)(1,4)}
7 6 7 Pop(5,7) - {(3,5)(2,5)(1,3)(1,4)}
Pop({(3,5)(2,5)(1,3)(1,4)}} -
For dfs(g,3):
For the next 3 examples, for clarity, if an edge, E(v,w) is added to stack or queue, only the destination vertex w is shown. The pop and push operations are similar to the above example
Order# ST Pre(Visited) Stack (top at left)
- - 3
0 3 3 1 2 4 5
1 3 1 0 2 4 2 4 5
2 1 0 2 4 2 4 5
3 1 2 5 4 2 4 5
4 2 5 6 7 4 2 4 5
5 6 6 7 4 2 4 5
6 6 7 4 2 4 5
7 4 4 2 4 5
- // After popping the last 3 elements of the stack - pop(2,4,5)
For bfs(g,0):
Order# ST Visited(Pre) Queue (front at left)
- - 0
0 0 0 1
1 1 1 2 3 4
2 2 2 3 4 3 5
3 3 3 4 3 5 4 5
4 4 4 3 5 4 5 5
5 5 5 4 5 5 6 7
6 6 6 7
7 7 7 -
For bfs(g,3):
# ST Visited Queue (front at left)
- - 3
3 3 3 1 2 4 5
1 3 1 2 4 5 0 2 4
2 1 2 4 5 0 2 4 5
4 2 4 5 0 2 4 5 5
5 4 5 0 2 4 5 5 6 7
0 5 0 2 4 5 5 6 7
6 0 6 7
7 6 7 -
In what order would you visit the nodes if you started at vertex 0 and used the cheapest least visited approach from assn2 and you had stamina of 100000? (Show the first 10 vertices you would visit in the order you would travel to them). Answer:
0 2 0 7 1 7 6 4 3 5 3
What about if you had a stamina level of 50?
0 2 2 0 0 7 7 1 7 7 6
Directed Graph - DFS and BFS
Directed Graph - DFS
What order would the nodes be visited while performing a depth first search starting at node d. What about if we started at node g? Answer:
If we called dfsR with starting node d we would get d b a c g f We would have to call dfsR again starting at node e to get all nodes in graph. So overall: d b a c g f e If we called dfsR with starting node g we would get node g We would have to call dfsR again, starting at say node a, then again starting at node e to visit all nodes So overall: g a d b c f e
Directed Graph BFS
What order would the nodes be visited while performing a breadth first search starting at node d. What about if we started at node g?
If we called bfs with starting node d we would get d b f g a c We would then have to call bfs with starting node e So overall: d b f g a c e If we called bfs with starting node g we would get g We would have to call bfs again, starting at say node a, then again starting at node e to visit all nodes So overall: g a d b f c e
Adjcency Matrix The standard adjacency matrix representation for a graph uses a full V×V matrix and stores each edge twice (at [v,w] and [w,v]). This consumes a lot of space, and wastes a lot of space when the graph is sparse. One simple way to improve the space usage would be to define the matrix elements as bool rather than int, e.g.
int **edges; // matrix of booleans (0 or 1) ... becomes ... bool **edges; // matrix of booleans (0 or 1) ... where bool is defined as ... typedef unsigned char bool;
We could use even less space by storing just the upper (or lower) triangular part of the matrix, as shown in the diagram below:
The V×V matrix has been replaced by a single array containing just the "useful" parts of the matrix. This gives a new Graph representation:
// Upper-triangluar adjacency matrix graph representation
struct graphRep {
int nV; // #vertices
int nE; // #edges
bool *edges; // array of booleans (0 or 1)
};
Accessing the elements is no longer as simple as edges[v][w]. Write a function that takes two vertices from an edge and determines the corresponding index in the edges array which holds the boolean value for this edge. Use the following function template:
int indexOf(Vertex v, Vertex w)
{
assert(v != w); // no self-edges
if (v > w) { Vertex tmp = v; v = w; v = tmp; }
...
}
Answer:
int indexOf(Vertex v, Vertex w)
{
assert(v != w); // no self-edges
if (v > w) { Vertex tmp = v; v = w; v = tmp; }
assert(w > v); // redundant
int i; // counts the number of iterations
int j; // gives the increment for eah iteration
int k; // accumulates the index value
for (i = 0, j = nV-1, k = 0; i < v; i++, j--) {
k += j;
}
k += w-1;
return k;
}
The standard implementation of the adjacency list representation for graphs stores each edge twice. The edge (v,w) appears as a w stored in the adjacency list for v and as a v stored in the adjacency list for w. A more storage efficient representation (analgous to storing just the top-right half of the adjacency matrix), would be store information for each edge just once.
Re-implement the following functions from lectures to use this each-edge-stored-once variation of adjacency lists:
void insertE(Graph g, Edge e); void removeE(Graph g, Edge e); int neighbours(Graph g, Vertex x, Vertex y);
You should not assume that supplied Edge values will necessarily satisfy (e.v < e.w). Assume the code for adjacency List given to you in the lectures and that functions insertVList, deleteVList, searchVList to add,delete and add an edge to a list exist.
Answer:The following functions support the each-edge-stored-once variation of adjacency lists:
Edge normalise(Edge e)
{
if (e.v > e.w) {
Vertex tmp = e.v; e.v = e.w; e.w = tmp;
}
return e;
}
void insertE(Graph g, Edge e)
{
assert(g != NULL);
assert(validV(g,e.v) && validV(g,e.w));
e = normalise(e);
int orig = length(g->edges[e.v]);
g->edges[e.v] = insertVList(e.w,g->edges[e.v]);
if (length(g->edges[e.v]) > orig) g->nE++;
}
void removeE(Graph g, Edge e)
{
assert(g != NULL);
assert(validV(g,e.v) && validV(g,e.w));
e = normalise(e);
g->edges[e.v] = deleteVList(g->edges[e.v], e.w);
if (length(g->edges[e.v]) < orig) g->nE--;
}
int neighbours(Graph e, Vertex v, Vertex w)
{
if (v > w) { Vertex t = v; v = w; w = t; }
return searchVList(g->edges[v], w);
}