Suppose the director shifts his shooting location to a venue where buildings are no longer arranged in a nice rectangular grid.
Assume we have N buildings 1,2,...,N and a list of pairs {(i1,j1), (i2,j2), ..., (iM,jM)} where each pair (i,j) says that building i and building j are "neighbours" --- that is, they are near enough in distance and height for the hero to jump from i to j or j to i. The hero has to start at building 1 and the captive is in building N.
For instance, suppose we have 7 buildings 1,2,...,7 and the list of neighbours are given by
{(1,2),(1,3),(2,3),(3,4),(5,6),(7,6),(5,7}.
Can the hero rescue the captive?
No, because there is no way to go from the set of buildings {1,2,3,4} to the set of buildings {5,6,7}.
If we draw this as a picture, it is easy to see that this problem has no solution:
2
/ \
/ \
1 --------- 3 -------- 4
5 --------- 6
\ /
\ /
7
Here, each building is labelled and we draw a line from i to j if i and j are neighbours. From the picture, it is immediate that there is no way to travel from {1,2,3,4} to {5,6,7}.
This kind of picture is called a graph. A graph is a pair G = (V,E) where
How do we check reachability in this framework? We can use a queue as before:
Notice that we have used exactly the same algorithm as we did for the rectangular grid. The only difference is that instead of implicitly identifying neighbours with respect to grid positions, we are explicitly given the neighbours for each node.
A graph is given by a pair G = (V,E), were V is the set of vertices E is the set of edges. Each edge e in E connects a pair of vertices (v,v'), so E is a subset of V×V, where V×V denotes the set set of all pairs of vertices. We normally assume that there are no self loops: that is, no edges of the form (v,v).
By convention, N or n = |V| = number of vertices, M or m = |E| = number of edges.
The degree of a vertex v is the number of edges with v as one end point. The sum of the degrees of all the vertices in a graph is even. Each edge adds 1 to the degree of the vertex at both end points. Thus,
sum degree(v) = 2 |E| = 2m
v in V
A path is a sequence v_1 v_2 … v_k of distinct vertices such that each adjacent pair v_i v_i+1 is an edge. (Note: a path cannot visit the same vertex twice. If a vertex is visited more than once in such a sequence, it is called a walk, not a path.)
A cycle is a sequence of vertices v_1 v_2 ... v_k v_1, where v_1 v_2 ... v_k is a path and v_k v_1 is an edge. (i.e. a cycle is a path that is closed by an edge from the last vertex in the path back to the initial vertex.)
Nodes u and v are connected if there is a path from u to v. A graph is connected if every pair of nodes is connected.
How do we check if a graph is connected? An undirected graph is connected precisely when depth first search or breadth first search marks all vertices (you can choose any start vertex v).
A tree is connected graph without cycles.
o-----o
/ \
o-------o o-------o
/ |\
/ | \
o o o
A tree as a minimal connected graph. By induction, we can show that a tree on n vertices always has exactly n-1 edges. In any tree, there is a unique path between any pair of vertices.
If we attach a cost with each edge we get a weighted graph. The cost could represent distance, or time, or some other natural quantity associated with traversing the edge.
o
7 / \ 8
/ 6 \
o-----o
\ /
2 \ / 5
o
©IARCS 2012–2016
Pěstujeme web | visit: Skluzavky