Table of Contents#### Download Safari Books Online apps: Apple iOS | Android | BlackBerry

### CHAPTER 13

Entire Site

Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

A power distribution network would be difficult to represent as a hierarchical structure, since the power-generating stations and supply substations may be cross-connected in a number of ways, rather than there being predecessor and successor installations. A node in a tree structure may have only one 'parent' node, but an electricity substation may receive power via one or more routes. The installations may be represented by a graph's vertices, with the connecting cables as the edges of the graph. The linkage between installations might be uni- or bidirectional, with the edge weightings corresponding to the power transmission capacity of the network's various cables.

See discussion in the text.

Contents of the adjacency matrix:

Vertex[0] = "Sleepytown"; Vertex[1] = "Much Snoring"; Vertex[2] = "Great Snoring"; Vertex[3] = "Little Snoring"; Vertex[4] = "Lesser Snoring"; Vertex[5] = "Snoring on Sea"; Vertex[6] = "Snoring on the Hill"; Edge[0][1] = 50; //

Edge[1][0] = 50;*Sleepytown to Much Snoring*Edge[1][2] = 150; //*// Much Snoring to Sleepytown*Edge[2][1] = 150; //*Much Snoring to Great Snoring*Edge[3][1] = 80; //*Great Snoring to Much Snoring*Edge[2][3] = 180; //*Little Snoring to Much Snoring*Edge[2][6] = 150;*Great Snoring to Little Snoring*Edge[2][5] = 200;*// Great Snoring to Snoring on the Hill*Edge[5][2] = 200; //*// Great Snoring to Snoring by Sea*Edge[6][4] = 50; //*Snoring on Sea to Great Snoring*Edge[4][2] = 180; //*Snoring on the Hill to Lesser Snoring**Lesser Snoring to Great Snoring*

Code View: Scroll / Show All*Breadth-first using Queue From Sleepytown: queue holds 0 Dequeue: Enqueue 1: Dequeue: Enqueue 2: Dequeue: Enqueue 3 5 6: Dequeue all: Enqueue 4: Dequeue Traversal: 0 1 2 3 5 6 4: Sleepytown - Much - Great - Little - Snoring on Sea - Snoring on the Hill - Lesser Snoring Depth-first using Stack From Sleepytown: stack holds 0 Pop, push 1: pop: push 2: pop: push 3 5 6 : pop 6: push 4: pop 4: pop 5: pop 3 Traversal: 0 1 2 6 4 5 3 Sleepytown - Much -Great - Snoring on the Hill - Lesser -Snoring on Sea - Little Snoring*

If the flight from Great Snoring to Much Snoring is withdrawn, then row subscript 2 is affected. Edges[2][1] is changed from 150 to 0 as shown in bold in the following table:

A return flight is introduced from Snoring on the Hill to Great Snoring, a distance of 150 miles. Since the starting point is Vertex[5] then Edges[5][2] is changed to 150.

For explanations of terms, see Chapter 13 (Section 13.19). Application to the first exercise: It would help in planning routes for power lines and associated installations, depending upon terrain—flat, hilly, water crossing—and on costs of underground or overhead cabling.6.

Use the example given in Chapter 13 (Section 13.17), and view the animated sequence in the Graphs presentation. Starting with A, note distances to node A neighbours. They are

B (10) C (5). Mark A checked

At C, get distances from A:

E (14) F (8). C checked

At B, distances from A:

D (14) B checked

Get distance via F: G - destination (16) F

Distance via E: H (18) E

Distance via D: H (21) – larger than via E, don't replace. D

Distance via H: I(24) H

Distance via I: G(29) – larger than via F, don't replace I

All vertices are checked—shortest distances are shown. Path is A—C—F—G, and the shortest distance is 16.

Use the same process for F to D with the result shown alongside. Path is F—C—A—B—D, and the shortest distance is 22

Apply Kruskal's algorithm by creating an ordered list of edges and weightings:

Construct the tree by adding edges, in the increasing order of weight (shown in bold lines in the following figure):

Add to tree:

F-G

E-F

A-C

A-B

C-E

omit B-E as this would produce a cycle

D-G

All vertices are now connected.

See example in Chapter 13 (Section 13.19). Apply Prim's algorithm by choosing a start point, and then its nearest neighbour.

Start at C: Choose A, then B. Next nearest neighbour is E. Now F, G, D. Produces the same tree as Kruskal's algorithm.

No solution given since this is a practical exercise.

Major changes are required, including the following:

An extra row and column must be added to the matrix, requiring redeclaration of the arrays Vertex as String[8], Edges as int[8][8] and Visited as boolean[8].

Statements must be written so as to add values as follows (also Visited[7] = false):

The traversal and search methods will need to be changed to take into account that the matrix now contains eight columns …

*for (int column = 0; column <**8**; column++) { if (Edge[current][column] != 0 && !visited[column]) myStack.push(column); }*

… as will the method that displays the matrix contents:

*for (int i = 0; i <**8**; i++) { System.out.print(Vertex[i]); for (int j = 0; j <**8**; j++) System.out.print(Edge[i][j] + " "); System.out.println(); }*