A simple way to represent V(graph), the vertices in the graph, is to use an array where the array elements are the vertices. For example, if the vertices represent city names, the array might hold strings. A simple way to represent E(graph), the edges in a graph, is to use an adjacency matrix, a two-dimensional array of edge values (weights), where the indices of a weight correspond to the vertices connected by the edge. Thus, a graph consists of an integer variable numVertices, a one-dimensional array vertices, and a two-dimensional array edges. Figure 10.5 depicts the implementation of the graph of Air Busters’ flights among the seven cities shown in Figure 10.3. For simplicity, we omit the additional boolean data needed to mark vertices as “visited” during a traversal from the figure. Although the city names in Figure 10.5 are in alphabetical order, there is no requirement that the elements in this array be sorted.

At any time, within this representation of a graph,

• numVertices is the number of vertices in the graph.

• V(graph) is contained in vertices[0] to vertices [numVertices - 1].

• E(graph) is contained in the square matrix edges[0][0] to edges[numVertices - 1][numVertices 1].

The names of the cities are contained in vertices. The weight of each edge in edges represents the air distance between two cities that are connected by a flight. For example, the value in edges[1][3] tells us that there is a direct flight between Austin and Dallas, and that the air distance is 200 miles. A NULL_EDGE value (0) in edges[1][6] tells us that the airline has no direct flights between Austin and Washington. Because this is a weighted graph in which the weights are air distances, we use int for the edge value type. If it were not a weighted graph, the edge value type could be boolean, with each position in the adjacency matrix being true if an edge exists between the pair of vertices, and false if no edge exists.

Here is the beginning of the definition of class WeightedGraph. We assume that the edge value type is int and that a null edge is indicated by a 0 value.

//---------------------------------------------------------------------------
// WeightedGraph.java            by Dale/Joyce/Weems               Chapter 10
//
// Implements a directed graph with weighted edges.
// Vertices are objects of class T and can be marked as having been visited.
// Edge weights are integers.
// Equivalence of vertices is determined by the vertices' equals method.
//
// General precondition: Except for the addVertex and hasVertex methods,
// any vertex passed as an argument to a method is in this graph.
//---------------------------------------------------------------------------

package ch10.graphs;

import ch04.queues.*;

public class WeightedGraph<T> implements WeightedGraphInterface<T>
{
  public static final int NULL_EDGE = 0;
  private static final int DEFCAP = 50;  // default capacity
  private int numVertices;
  private int maxVertices;
  private T[] vertices;
  private int[][] edges;
  private boolean[] marks;  // marks[i] is mark for vertices[i]

  public WeightedGraph()
  // Instantiates a graph with capacity DEFCAP vertices.
  {
    numVertices = 0;
    maxVertices = DEFCAP;
    vertices = (T[]) new Object[DEFCAP];
    marks = new boolean[DEFCAP];
    edges = new int[DEFCAP][DEFCAP];
  }

  public WeightedGraph(int maxV)
  // Instantiates a graph with capacity maxV.
  {
    numVertices = 0;
    maxVertices = maxV;
    vertices = (T[]) new Object[maxV];1
    marks = new boolean[maxV];
    edges = new int[maxV][maxV];
  }

The class constructors have to allocate the space for vertices, marks (the boolean array indicating whether a vertex has been marked), and edges. The default constructor sets up space for a graph with DEFCAP (50) vertices. The parameterized constructor lets the user specify the maximum number of vertices.

The addVertex operation puts a vertex into the next free space in the array of vertices and increments the number of vertices. Because the new vertex has no edges defined yet, it also initializes the appropriate row and column of edges to contain NULL_EDGE (0 in this case).

public void addVertex(T vertex)
// Preconditions:   This graph is not full.
//                  vertex is not already in this graph.
//                  vertex is not null.
//
// Adds vertex to this graph.
{
  vertices[numVertices] = vertex;
  for (int index = 0; index < numVertices; index++)
  {
     edges[numVertices][index] = NULL_EDGE;
     edges[index][numVertices] = NULL_EDGE;
  }
  numVertices++;
}

To add an edge to the graph, we must first locate the fromVertex and toVertex that define the edge being added. These values become the arguments to addEdge and are of the generic T class. Of course, the client really passes references to the vertex objects, because that is how we manipulate objects in Java. We are implementing our graphs “by reference” so this strategy should not pose a problem for the client. To index the correct matrix slot, we need the index in the vertices array that corresponds to each vertex. Once we know the indices, it is a simple matter to set the weight of the edge in the matrix.

To find the index of each vertex, let us write a private search method that receives a vertex and returns its location (index) in vertices. Based on the general precondition stated in the opening comment of the WeightedGraph class, we assume that the fromVertex and toVertex arguments passed to addEdge are already in V(graph). This assumption simplifies the search method, which we code as helper method indexIs. Here is the code for indexIs and addEdge:

private int indexIs(T vertex)
// Returns the index of vertex in vertices.
{
  int index = 0;
  while (!vertex.equals(vertices[index]))
    index++;
  return index;
}

public void addEdge(T fromVertex, T toVertex, int weight)
// Adds an edge with the specified weight from fromVertex to toVertex.
{
  int row;
  int column;

  row = indexIs(fromVertex);
  column = indexIs(toVertex);
  edges[row][column] = weight;
}

The weightIs operation is the mirror image of addEdge.

public int weightIs(T fromVertex, T toVertex)
// If edge from fromVertex to toVertex exists, returns the weight of edge;
// otherwise, returns a special "null-edge" value.
{
  int row;
  int column;

  row = indexIs(fromVertex);
  column = indexIs(toVertex);
  return edges[row][column];
}

The last graph operation that we address is getToVertices. This method receives a vertex as an argument, and it returns a queue of vertices that the vertex is adjacent to (or, another way of looking at it, that are adjacent from the designated vertex). That is, it returns a queue of all the vertices that we can get to from this vertex in one step. Using an adjacency matrix to represent the edges, it is a simple matter to determine the vertices to which the vertex is adjacent. We merely loop through the appropriate row in edges; whenever a value is found that is not NULL_EDGE, we add the corresponding vertex to the queue.

public QueueInterface<T> getToVertices(T vertex)
// Returns a queue of the vertices that are adjacent from vertex.
{
  QueueInterface<T> adjVertices = new LinkedQueue<T>();
  int fromIndex, toIndex;
  fromIndex = indexIs(vertex);
  for (toIndex = 0; toIndex < numVertices; toIndex++)
    if (edges[fromIndex][toIndex] != NULL_EDGE)
      adjVertices.enqueue(vertices[toIndex]);
  return adjVertices;
}

We leave writing isFull, isEmpty, hasVertex, and the marking operations (clearMarks, markVertex, isMarked, and getUnmarked) for you as exercises.

The advantages of representing the edges in a graph with an adjacency matrix are twofold: speed and simplicity. Given the indices of two vertices, determining the existence (or the weight) of an edge between them is an O(1) operation. The problem with adjacency matrices is that their use of space to store the edge information is O(N²), where N is the maximum number of vertices in the graph. If the maximum number of vertices is large but the number of actual vertices is small, or if a graph is sparse (the ratio between the number of edges and number of vertices is small), adjacency matrices waste a lot of space. We can save space by allocating memory as needed at run time, using linked structures. Adjacency lists are linked lists, one list per vertex, that identify the vertices to which each vertex is connected. They can be implemented in several different ways. Figures 10.6 and 10.7 show two different adjacency list representations of the graph in Figure 10.3.

In Figure 10.6, the vertices are stored in an array. Each component of this array contains a reference to a linked list of edge information. Each item in these linked lists contains an index number, a weight, and a reference to the next item in the adjacency list. Look at the adjacency list for Denver. The first item in the list indicates that there is a 1,400-mile flight from Denver to Atlanta (the vertex whose index is 0) and the second item indicates a 1,000-mile flight from Denver to Chicago (the vertex whose index is 2).

No arrays are used in the implementation illustrated in Figure 10.7. Instead, the list of vertices is also implemented as a linked list. Now each item in the adjacency list contains a reference to the vertex information rather than the index of the vertex. Because Figure 10.7 includes so many of these references, we have used text to describe the vertex that each reference designates rather than draw them as arrows.

We leave the implementation of the Graph class methods using the linked approaches as a programming exercise.

One question we can answer using the graph in Figure 10.3 is “Can I get from city X to city Y on my favorite airline?” This is equivalent to asking, “Does a path exist in the graph from vertex X to vertex Y?” Using a depth-first strategy, we develop an algorithm IsPathDF that determines whether a path exists from startVertex to endVertex.

We need a systematic way to keep track of the cities as we investigate them. With a depth-first search, we examine the first vertex that is adjacent from startVertex; if it is endVertex, the search is over. Otherwise, we examine all of the vertices that can be reached in one step (are adjacent) from this first vertex. While we examine these vertices, we need to store the remaining vertices adjacent from startVertex that have not yet been examined. If a path does not exist from the first vertex, we come back and try the second vertex, third vertex, and so on. Because we want to travel as far as we can down one path, backtracking if the endVertex is not found, a stack is a good structure for storing the vertices.

However, there is a problem with the approach we just described. Graphs can contain cycles. We can fly from Washington to Dallas to Denver and then back to Washington. Do you see why this is an issue in the approach described above? Not only is it likely that we will unnecessarily repeat the processing of a city (a vertex), it is even possible to get caught in an infinite loop (e.g., when processing Washington we push Atlanta onto the stack, and when processing Atlanta we push Washington onto the stack). We did not have this issue when designing our tree traversals in Chapter 7 because trees by definition do not have cycles.

How can we fix this? You probably recall that addressing this problem was the reason we included the ability to mark vertices within our Graph ADT. Our solution is to mark vertices to indicate that they have been placed on the stack. And, of course, to use those marks to prevent pushing a vertex onto the stack more than once. This way we eliminate repetitiously processing a vertex and the possibility of an infinite loop. Here is the algorithm:

Let us apply this algorithm to the sample airline-route graph in Figure 10.3. We will trace the algorithm applied to the case where Austin is the starting city and Washington is the desired destination. In Figure 10.8 we repeat the airport graph, abbreviating the names of the cities using their first two letters and dropping the distances, because they are not pertinent to our current question. We use boldface to indicate that a city has been processed—that it has been checked to see if it is the destination and if not then its adjacent cities have been placed on the stack if appropriate. We also sequentially number the entry edge into a city when it is processed, the edge that is followed to lead to the processing of the city. Finally, we indicate that a city has been marked by placing a checkmark beside it.

Okay, so we want to fly from Austin to Washington. We initialize our search by marking our starting city and pushing it onto the stack (Figure 10.8a). At the beginning of the do-while loop we retrieve the current city, Austin, from the stack using the top method and then remove it from the stack using the pop method. Because Austin is not our final destination we examine the places we can reach directly from it—Dallas and Houston (we will process adjacent vertices in alphabetical order); neither of these is marked so we mark them and push them onto the stack (Figure 10.8b). That completes the processing of Austin.

At the beginning of the second iteration we retrieve and remove the top vertex from the stack—Houston. Houston is not our destination, so we resume our search from there. There is only one flight out of Houston, to Atlanta; Atlanta has not yet been marked so we mark it and push it onto the stack (Figure 10.8c), finishing our processing of Houston. Again we retrieve and remove the top vertex from the stack. Atlanta is not our destination, so we continue searching from there. Atlanta has flights to two cities: Houston and Washington. Houston was already marked so at this stage we mark only Washington and push it onto the stack (Figure 10.8d).

Finally, we retrieve and remove the top vertex from the stack, Washington. This is our destination, so the search is complete (Figure 10.8e).

As indicated by the final part of Figure 10.8e we had a very successful and efficient search, processing only four cities during our search including the source and destination cities. Although the algorithm (since it is correct!) guarantees success in that it will always correctly identify whether a path exists, it might not always be so efficient. Consider a new question: can we fly from Dallas to Austin. A quick check of the graph tells us that yes we can, in fact it is a one hop trip. Yet in this case the algorithm will process every vertex in the graph before determining that the path exists. The reader is encouraged to verify this for themselves by tracing the algorithm on the new problem.

Method isPathDF receives a graph object, a starting vertex, and a target vertex. It uses the depth-first algorithm described above to determine whether a path exists from the starting city to the ending city, displaying the names of all cities processed in the search. Nothing in the method depends on the implementation of the graph. The method is implemented as a graph application; it uses the Graph ADT operations without knowing how the graph is represented. We use a graph of strings, since we can represent a city by its name. In the following code, we assume that a stack and a queue implementation have been imported into the client class. (The isPathDF method is included in the UseGraph.java application, available in the ch10.apps package.)

private static boolean isPathDF(WeightedGraphInterface<String> graph,
                                String startVertex, String endVertex)
// Returns true if a path exists on graph, from startVertex to endVertex;
// otherwise returns false. Uses depth-first search algorithm.
{
  StackInterface<String> stack = new LinkedStack<String>();
  QueueInterface<String> vertexQueue = new LinkedQueue<String>();

  boolean found = false;
  String currVertex;       // vertex being processed
  String adjVertex;        // adjacent to currVertex

  graph.clearMarks();
  graph.markVertex(startVertex);
  stack.push(startVertex);

  do
  {
    currVertex = stack.top();
    stack.pop();
    System.out.println(currVertex);
    if (currVertex.equals(endVertex))
       found = true;
    else
    {
      vertexQueue = graph.getToVertices(currVertex);
      while (!vertexQueue.isEmpty())
      {
        adjVertex = vertexQueue.dequeue();
        if (!graph.isMarked(adjVertex))
        {
          graph.markVertex(adjVertex);
          stack.push(adjVertex);
        }
      }
    }
  } while (!stack.isEmpty() && !found);
  return found;
}

A breadth-first search looks at all possible paths at the same depth before it goes to a deeper level. In our flight example, a breadth-first search checks all possible one-stop connections before checking any two-stop connections. For most travelers, this strategy is the preferred approach for booking flights.

When we come to a dead end in a depth-first search, we back up as little as possible. We then try another route from a recent vertex—the route on top of our stack. In a breadth-first search, we want to back up as far as possible to find a route originating from the earliest vertices. The stack is not the right structure for finding an early route, because it keeps track of things in the order opposite of their occurrence—the latest route is on top. To keep track of things in the order in which they happened, we use a FIFO queue. The route at the front of this queue is a route from an earlier vertex; the route at the back of the queue is from a later vertex. To modify the search to use a breadth-first strategy, we change all calls to stack operations to the analogous FIFO queue operations in the previous algorithm. Just as we did with the depth-first search, we mark a vertex before placing it in the queue, to avoid repetitive processing. Here is the breadth-first algorithm:

Figure 10.9 shows the sequence in which vertices are visited for several depth-first and breadth-first searches using our flights example. The numbers in the figure indicate the order in which entry edges are used to “visit” vertices. Keep in mind our assumption that vertices are placed into the queue (or stack) in alphabetical order.

Let us revisit our previous example, searching for a path from Austin to Washington, but this time with a breadth-first search. We start with Austin in the queue. We dequeue Austin and enqueue all the cities that can be reached directly from it: Dallas and Houston. Then we dequeue the front queue element, Dallas (indicated by the circled 1 in Figure 10.9b). Because Dallas is not the destination we seek, we enqueue all the adjacent cities from Dallas that have not yet been marked: Chicago and Denver. (Austin has been visited already, so it is not enqueued.) Again we dequeue the front element from the queue. This element is the other “one-stop” city: Houston (indicated by the circled 2 in Figure 10.9b). Houston is not the desired destination, so we continue the search. There is only one flight out of Houston, and it is to Atlanta. Because we have not marked Atlanta before, it is enqueued. This processing continues until Washington is put into the queue (from Atlanta), and is finally dequeued. We have found the desired city, and the search is complete.

As you can see in Figure 10.9b the breadth-first search of a path from Austin to Washington processed every city in the graph before determining that the path existed. It was not as efficient as the depth-first search for the same path (Figure 10.9a). On the other hand, a comparison of Figures 10.9c and 10.9d shows that in another case, searching for a path from Dallas to Austin, the breadth-first search is more efficient. It is really just a matter of luck— the number of steps depends on the graph configuration and the source and destination vertices. Comparing Figures 10.9e and 10.9f shows an example, searching for a path from Washington to Austin, where the same number of entry edges are used in each approach.

The source code for the breadth-first search approach is identical to the depth-first search code, except for the replacement of the stack with a FIFO queue. It is also included in the UseGraph.java application, as the method isPathBF, available in the ch10.apps package.

You may have noticed that in all of our examples so far we have been able to “reach” all of the other vertices in our graphs from our given starting vertex. What if this is not the case? Consider the weighted graph in Figure 10.10, which depicts a new set of airline-flight legs. It is identical to Figure 10.3 except that we removed the Washington–Dallas leg. If we invoke our shortestPaths method, passing it this graph and a starting vertex of Washington, we get the following output:

A careful study of the new graph confirms that one can reach Atlanta and Houston only, when starting in Washington, at least when flying Air Buster Airlines.

Suppose we extend the specification of our shortestPaths method to require that it also prints the unreachable vertices. How can we determine the unreachable vertices after we have generated the information about the reachable ones? Easy! The unreachable vertices are the unmarked vertices. We simply need to check whether any vertices remain unmarked. Our Graph ADT provides the operation getUnmarked specifically for this situation. So we simply add the following code to our method:

System.out.println("The unreachable vertices are:");
vertex = graph.getUnmarked();
while (vertex != null)
{
  System.out.println(vertex);
  graph.markVertex(vertex);
  vertex = graph.getUnmarked();
}

Now the output from the call to shortestPaths would be

In Exercise 43 we ask you to investigate counting the “connected components” of a graph. This is another interesting application of the getUnmarked method.

12. Classify the methods defined in the WeightedGraphInterface as observers or transformers or both.

13. It is possible to define more operations for a Graph ADT. Describe two operations that you think would be useful additions to the WeightedGraphInterface, and explain why.

14. Suppose g has been declared to be of type WeightedGraphInterface and instantiated as an object of a class that implements that interface. Assume that g consists of seven vertices A, B, C, D, E, F, G and seven directed edges A-B, B-C, C-D, D-C, D-F, F-B, and G-E with all weights equal to 1. Show the expected output of the section of code below. Assume that capital letters A through G are of type T (the vertex type), that getToVertices returns a queue with the vertices in alphabetical order, that getUnmarked returns unmarked vertices in alphabetical order, that the null edge value is 0, and that printing a vertex displays its corresponding letter.

    System.out.println(g.isEmpty());
    System.out.println(g.weightIs(A,B));
    System.out.println(g.weightIs(B,A));
    System.out.println(g.weightIs(A,C));
    g.clearmarks(); g.markVertex(A); g.markVertex(C);
    System.out.println(g.ismarked(B));
    
    g.markVertex(g.getUnmarked()))
    System.out.println(g.isMarked(B));
    System.out.println(g.getUnmarked());
    System.out.println(g.getToVertices(D).dequeue());

15. Draw the adjacency matrix for EmployeeGraph (see Exercise 5). Store the vertices in alphabetical order.

16. Draw the adjacency matrix for ZooGraph (see Exercise 7). Store the vertices in alphabetical order.

    Note: Exercises 18–22, 38, and 42 are dependent on the completion of Exercise 17.

17. Complete the implementation of the Weighted Graph (WeightedGraph.java) that we began in this chapter by providing bodies for the methods isEmpty, isFull, hasVertex, clearMarks, markVertex, isMarked, and getUnmarked in the WeightedGraph.java file. Test the completed implementation using the UseGraph class. When implementing hasVertex, do not forget to use the equals method to compare vertices.

18. For each of the methods in the WeightedGraph implementation, identify its order of growth efficiency.

19. Class WeightedGraph in this chapter is to be extended to include a boolean edgeExists operation that determines whether two vertices are connected by an edge.

    1. Write the declaration of this method. Include adequate comments.

    2. Implement the method.

20. Class WeightedGraph in this chapter is to be extended to include an int connects operation, passed two arguments a and b of type T representing two vertices in the graph (guaranteed as a precondition that both a and b are vertices) that returns a count of the number of vertices v such that v is connected to both a and b.

    1. Write the declaration of this method. Include adequate comments.

    2. Implement the method.

21. Class WeightedGraph in this chapter is to be extended to include a removeEdge operation that removes a given edge.

    1. Write the declaration of this method. Include adequate comments.

    2. Implement the method.

22. Class WeightedGraph in this chapter is to be extended to include a removeVertex operation that removes a vertex from the graph.

    1. Deleting a vertex is more complicated than deleting an edge from the graph. Discuss the reasons for this operation’s greater complexity. Write the declaration of this method. Include adequate comments.

    2. Implement the method.

23. Graphs can be implemented using arrays or references. For the states graph (see Exercise 10):

    1. Show the adjacency matrix that would describe the edges in this graph. Store the vertices in alphabetical order.

    2. Show the array of adjacency lists that would describe the edges in this graph.

24. What percent of the adjacency matrix representation of a graph consists of null edges if the graph contains

    1. 10 vertices and 10 edges?

    2. 100 vertices and 100 edges?

    3. 1,000 vertices and 1,000 edges?

25. Assuming an adjacency matrix-based directed graph implementation as described in Section 10.3, “Implementations of Graphs,” describe an algorithm that solves each of the following problems; include an efficiency analysis of your solutions.

    1. Return the number of vertices in the graph.

    2. Return the number of edges in the graph.

    3. Return the highest number of “out edges” exhibited by a vertex; for example, for the graph in Figure 10.3 this would return 3 because Dallas has three cities adjacent to it

    4. Return the highest number of “in edges” exhibited by a vertex. For example, for the graph in Figure 10.3 this would return 3 because Atlanta has three cities it is adjacent from.

    5. Return the number of “singleton” vertices, that is, vertices that are not connected to any other vertex.

26. Repeat Exercise 25 using the adjacency list–directed graph implementation approach represented in Figure 10.6.

27. Specify, design, and code an undirected, weighted graph class using an adjacency matrix representation.

28. Specify, design, and code an undirected, unweighted graph class using an adjacency matrix representation.

29. Design and code a reference-based weighted graph class with the vertices stored in an array as in Figure 10.6. Your class should implement our WeightedGraphInterface.

30. Design and code a reference-based weighted graph class with the vertices stored in a linked list as in Figure 10.7. Your class should implement our WeightedGraphInterface.

For exercises 31–36 assume getToVertices and getUnmarked return information in alphabetical order.

31. Using the EmployeeGraph (see Exercise 5) describe both the order in which vertices would be marked and the order they would be visited/processed using the depth-first “is there a path” algorithm, when searching for a path:

    1. from Susan to Lance

    2. from Brent to John

    3. from Sander to Darlene

32. Repeat Exercise 31 using the breadth-first algorithm.

33. Using the StateGraph (see Exercise 10) describe both the order in which vertices would be marked and the order they would be visited/processed using the depth-first “is there a path” algorithm, when searching for a path:

    1. from Texas to Alaska

    2. from Hawaii to California

    3. from Hawaii to Texas

34. Repeat Exercise 33 using the breadth-first algorithm.

35. We reconfigure the Air Busters Airlines graph in Figure 10.3 so that the edges from Dallas to Austin and from Denver to Atlanta are dropped and an edge from Denver to Washington with weight 700 is added. Describe both the order in which vertices would be marked and the order they would be visited/processed using the depth-first “is there a path” algorithm, when searching for a path:

    1. from Dallas to Houston

    2. from Denver to Austin

36. Repeat Exercise 35 using the breadth-first algorithm.

37. Consider the following full graph of seven vertices.

    

    1. Recreate the drawing of the graph so that it shows only the lead-in edges to vertices that would be visited by a depth-first search starting from the vertex at the top of the image. Note that there are many possible answers.

    2. Recreate the drawing of the graph so that it shows only the lead-in edges to vertices that would be visited by a breadth-first search starting from the vertex at the top of the image. Note that there is only one possible answer.

38. A text file contains information about a directed unweighted graph, where the vertices are strings, by listing the edges line by line. Each line contains the from-vertex, followed by the symbol #, followed by the to-vertex. For example,

    heap#priority queue

    represents an edge from the vertex “heap” to the vertex “priority queue” perhaps in this case representing the fact that a heap is used to implement a priority queue.

    Create an application that is given the name of such a text file as a command line argument, generates the corresponding graph using WeightedGraph from the ch10.graphs package, and then repeatedly prompts the user to enter a from-vertex and a to-vertex, reporting back to the user (a) one or both of the vertices does not exist or (b) whether there exists a path from the given from-vertex to the given to-vertex.

    Create a suitable input file and test your program. Submit a report.

39. Trace the Shortest Paths algorithm (or code) including the latter section about unreachable vertices and show what it would output for our Air Busters Airlines example (Figure 10.3) if the starting vertex is

    1. Dallas

    2. Atlanta

40. We reconfigure the Air Busters Airlines graph in Figure 10.3 so that the edges from Dallas to Austin, Denver to Atlanta, Washington to Dallas, and Austin to Houston are dropped and an edge from Denver to Washington with weight 700 is added. Trace the Shortest Paths algorithm (or code) including the latter section about unreachable vertices and show what it would output for this new graph if the starting vertex is

    1. Austin

    2. Atlanta

41. For the StateGraph (see Exercise 10) list the unreachable vertices for each of the vertices in the graph.

42. Our shortestPaths method is concerned with the minimum distance between two vertices of a graph. Create a minEdges method that returns the minimum number of edges that exist on a path between two given vertices. You can put your new method in our useGraph class and use it to test your code.

43. Counting connected components. Informally, a connected component of a graph is a subset of the vertices of the graph such that all of the vertices in the subset are connected to each other by a path. For example, the following graph consists of three connected components.

    

    1. Create an undirected, unweighted graph ADT (similar to Exercise 26 but you can use a linked representation if you wish).

    2. Test it.

    3. Create an application that generates a graph and counts the number of connected components. The graph can be “hard coded,” read from a file, or randomly generated.

    4. Create an application that generates graphs with 26 vertices and:

       • 4, 8, 12, 16, 20, 24, 28, 32, 36, and 40 unique random edges.

       • five graphs for each of the number of edges (so you are generating 50 random graphs altogether).

       • outputs the average number of connected components for each edge count.

    5. Submit a report that contains your code, the output, and a discussion.