Let us analyze algorithm EulerPath. The important operation done by the algorithm is an examination of the elements of the adjacency matrix, which occurs
in the line marked at the end with an asterisk ( * ). In the worst case, the while loop
in the algorithm is executed n times, once for each row. Within the while loop, the
for loop, containing line ( * ), is executed n times, once for each column. EulerPath
is therefore an Θ(n
2
) algorithm in the worst case.
At the cost of some extra decision logic, we could modify the algorithm because we never have to examine the last row of the matrix. We know from the
theorem on Euler paths that the total number of odd nodes is even. If the number
of odd nodes after processing the next-to-last row is odd, then the last row must
represent an odd node; if that number is even, then the last row must represent an
even node. This modification results in (n − 1)n elements to examine in the worst
case, which is still Θ(n
2
).
If we represented the graph G by an adjacency list rather than an adjacency matrix, then the corresponding version of the algorithm would have to count the length
of the adjacency list for each node and keep track of how many are of odd length.
There would be n adjacency lists to examine, just as there were n rows of the adjacency matrix to examine, but the length of each adjacency list might be shorter than
n, the length of a row of the matrix. It is possible to reduce the order of magnitude
below n
2
if the number of arcs in the graph is small, but the worst case is still Θ(n
2
).
example 7
The adjacency matrix for the graph of Figure 7.6a follows.
E
0 2 1 0 0
2 0 1 0 0
1 1 0 1 1
0 0 1 0 2
0 0 1 2 0
U
When the algorithm first enters the while loop, total is 0 and i is 1. Then degree is
initialized to 0. Within the for loop, the values of row 1 of the adjacency matrix are
added in turn to degree, resulting in a value for degree of 3. The odd function applied
to degree returns the value “true,” so the value of total is increased from 0 to 1; one
node of odd degree has been found. Then i is incremented to 2. Neither the bounds on
total nor the bounds on the array size have been exceeded, so the while loop executes
again, this time for row 2 of the array. Once again, degree is found to be odd, so the
value of total is changed to 2. When the while loop is executed for row 3 of the array, the value of degree is even (4), so total does not change, and the while loop is
executed again with i = 4. Row 4 again produces an odd value for degree, so total
is raised to 3. This terminates the while loop. The bad news is written that there is no
Euler path because the number of odd nodes exceeds 2.
Section 7.2 Euler Path and Hamiltonian Circuit
575
praCtiCe 10 Write the adjacency matrix for the Königsberg walk problem and trace the execution of
algorithm EulerPath.
■
in the line marked at the end with an asterisk ( * ). In the worst case, the while loop
in the algorithm is executed n times, once for each row. Within the while loop, the
for loop, containing line ( * ), is executed n times, once for each column. EulerPath
is therefore an Θ(n
2
) algorithm in the worst case.
At the cost of some extra decision logic, we could modify the algorithm because we never have to examine the last row of the matrix. We know from the
theorem on Euler paths that the total number of odd nodes is even. If the number
of odd nodes after processing the next-to-last row is odd, then the last row must
represent an odd node; if that number is even, then the last row must represent an
even node. This modification results in (n − 1)n elements to examine in the worst
case, which is still Θ(n
2
).
If we represented the graph G by an adjacency list rather than an adjacency matrix, then the corresponding version of the algorithm would have to count the length
of the adjacency list for each node and keep track of how many are of odd length.
There would be n adjacency lists to examine, just as there were n rows of the adjacency matrix to examine, but the length of each adjacency list might be shorter than
n, the length of a row of the matrix. It is possible to reduce the order of magnitude
below n
2
if the number of arcs in the graph is small, but the worst case is still Θ(n
2
).
example 7
The adjacency matrix for the graph of Figure 7.6a follows.
E
0 2 1 0 0
2 0 1 0 0
1 1 0 1 1
0 0 1 0 2
0 0 1 2 0
U
When the algorithm first enters the while loop, total is 0 and i is 1. Then degree is
initialized to 0. Within the for loop, the values of row 1 of the adjacency matrix are
added in turn to degree, resulting in a value for degree of 3. The odd function applied
to degree returns the value “true,” so the value of total is increased from 0 to 1; one
node of odd degree has been found. Then i is incremented to 2. Neither the bounds on
total nor the bounds on the array size have been exceeded, so the while loop executes
again, this time for row 2 of the array. Once again, degree is found to be odd, so the
value of total is changed to 2. When the while loop is executed for row 3 of the array, the value of degree is even (4), so total does not change, and the while loop is
executed again with i = 4. Row 4 again produces an odd value for degree, so total
is raised to 3. This terminates the while loop. The bad news is written that there is no
Euler path because the number of odd nodes exceeds 2.
Section 7.2 Euler Path and Hamiltonian Circuit
575
praCtiCe 10 Write the adjacency matrix for the Königsberg walk problem and trace the execution of
algorithm EulerPath.
■