< Free Open Study > |
Binary trees provide a very useful way of representing relationships in which a hierarchy exists. That is, a node is pointed to by at most one other node (its parent), and each node points to at most two other nodes (its children). If we remove the restriction that each node can have at most two children, we have a general tree, as pictured here:
If we also remove the restriction that each node may have only one parent node, we have a data structure called a graph. A graph is made up of a set of nodes called vertices and a set of lines called edges (or arcs) that connect the nodes.
Graph A data structure that consists of a set of nodes and a set of edges that relate the nodes to one another
Vertex A node in a graph
Edge (arc) A pair of vertices representing a connection between two nodes in a graph
Undirected graph A graph in which the edges have no direction
Directed graph (digraph) A graph in which each edge is directed from one vertex to another (or the same) vertex
The set of edges describes relationships among the vertices. For instance, if the vertices are the names of cities, the edges that link the vertices could represent roads between pairs of cities. Because the road that runs between Houston and Austin also runs between Austin and Houston, the edges in this graph have no direction. This structure is called an undirected graph. However, if the edges that link the vertices represent flights from one city to another, the direction of each edge is important. The existence of a flight (edge) from Houston to Austin does not assure the existence of a flight from Austin to Houston. A graph whose edges are directed from one vertex to another is called a directed graph, or digraph
From a programmer's perspective, vertices represent whatever is the subject of our study: people, houses, cities, courses, and so on. Mathematically, vertices are the undefined concept upon which graph theory rests. In fact, a great deal of formal mathematics is associated with graphs. In other computing courses, you will probably analyze graphs and prove theorems about them. This textbook introduces the graph as an abstract data type, explains some basic terminology, discusses how you might implement a graph, and describes how algorithms that manipulate graphs make use of stacks, queues, and priority queues.
Formally, a graph G is defined as follows:
G = (V, E)
where
V(G) is a finite, nonempty set of vertices
E(G) is a set of edges (written as pairs of vertices)
To specify the set of vertices, list them in set notation, within {} braces. The following set defines the four vertices of the graph pictured in Figure 9.8(a):
V(Graph 1) = {A, B, C, D}
The set of edges is specified by listing a sequence of edges. To denote each edge, write the names of the two vertices it connects in parentheses, with a comma between them. For instance, the vertices in Graph1 in Figure 9.8(a) are connected by the four edges described below:
E(Graph1) = {(A, B), (A, D), (B, C), (B, D)}
Because Graph1 is an undirected graph, the order of the vertices in each edge is unimportant. The set of edges in Graph1 can also be described as follows:
E(Graph1) = {(B, A), (D, A), (C, B), (D, B)}
If the graph is a digraph, the direction of the edge is indicated by which vertex is listed first. For instance, in Figure 9.8(b), the edge (5, 7) represents a link from vertex 5 to vertex 7. However, Graph2 does not contain corresponding edge (7, 5). Note that in pictures of digraphs, the arrows indicate the direction of the relationship.
If two vertices in a graph are connected by an edge, they are said to be adjacent. In Graph 1 (Figure 9.8a), vertices A and B are adjacent, but vertices A and C are not. If the vertices are connected by a directed edge, then the first vertex is said to be adjacent to the second, and the second vertex is said to be adjacent from the first. For example, in Graph2 (in Figure 9.8b), vertex 5 is adjacent to vertices 7 and 9, while vertex 1 is adjacent from vertices 3 and 11.
Adjacent vertices Two vertices in a graph that are connected by an edge
Path A sequence of vertices that connects two nodes in a graph
Complete graph A graph in which every vertex is directly connected to every other vertex
Weighted graph A graph in which each edge carries a value
Graph3 in Figure 9.8(c) may look familiar; it is the tree we examined earlier in connection with the nonlinked representation of a binary tree. A tree is a special case of a directed graph, in which each vertex may be adjacent from only one other vertex (its parent node) and one vertex (the root) is not adjacent from any other vertex.
A path from one vertex to another consists of a sequence of vertices that connect them. For a path to exist, an uninterrupted sequence of edges must go from the first vertex, through any number of vertices, to the second vertex. For example, in Graph2, a path goes from vertex 5 to vertex 3, but not from vertex 3 to vertex 5. Note that in a tree, such as Graph3 (Figure 9.8c), a unique path exists from the root to every other node in the tree.
In a complete graph, every vertex is adjacent to every other vertex. Figure 9.9 shows two complete graphs. If there are N vertices, there will be N * (N - 1) edges in a complete directed graph and N * (N - 1) / 2 edges in a complete undirected graph.
In a weighted graph, each edge carries a value. Weighted graphs can be used to represent applications in which the value of the connection between the vertices is important, not just the existence of a connection. For instance, in the weighted graph pictured in Figure 9.10, the vertices represent cities and the edges indicate the Air Busters Airlines flights that connect the cities. The weights attached to the edges represent the air distances between pairs of cities.
To see whether we can get from Denver to Washington, we look for a path between the two cities. If the total travel distance is determined by the sum of the distances between each pair of cities along the way, we can calculate the travel distance by adding the weights attached to the edges that constitute the path between them. Note that multiple paths may connect two vertices. Later in this chapter, we discuss a way to find the shortest path between two vertices.
We have described a graph at the abstract level as a set of vertices and a set of edges that connect some or all of the vertices to one another. What kind of operations are defined on a graph? In this chapter, we specify and implement a small set of useful graph operations. Many other operations on graphs can be defined; we have chosen operations that are useful in the graph applications described later in the chapter. First, however, we must define the operations necessary to build and process the graph.
We need to add vertices and edges, determine the weight on an edge, and get access to vertices that are adjacent from a vertex. Let's collect our observations about creating a graph into a CRC card:
Here is the specification for the Graph ADT:
Our Graph ADT specification includes only the most basic operations. It provides no traversal operations. As you might imagine, we can traverse a graph in many different orders. As a result, we consider traversal to be a graph application rather than an innate operation. The basic operations given in our specification allow us to implement different traversals independently of how the graph itself is implemented.
In Chapter 8, we discussed the postorder tree traversal, which goes to the deepest level of the tree and works up. This strategy of going down a branch to its deepest point and moving up is called a depth-first strategy. Another systematic way to visit each vertex in a tree is to visit each vertex on Level 0 (the root), then each vertex on Level 1, then each vertex on Level 2, and so on. Visiting each vertex by level in this way is called a breadth-first strategy. With graphs, both depth-first and breadth-first strategies are useful. We outline both algorithms within the context of the airline example.
Depth-First Searching One question we can answer with the graph in Figure 9.10 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, let's develop an algorithm that finds a path 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 ends. Otherwise, we examine all vertices that can be reached in one step (are adjacent from) this vertex. Meanwhile, we need to store the other vertices that are adjacent from startVertex. 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 we do not find the endVertex, a stack is a good structure for storing the vertices.
Here is the algorithm we use:
Let's apply this algorithm to the airline-route graph depicted in Figure 9.10. We want to fly from Austin to Washington. We initialize our search by pushing our starting city onto the stack (Figure 9.11a). At the beginning of the loop, we pop the current city, Austin, from the stack. The places we can reach directly from Austin are Dallas and Houston; we push both these vertices onto the stack (Figure 9.11b). At the beginning of the second iteration, we pop 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; we push Atlanta onto the stack (Figure 9.11c). Again we pop 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.
But we just came from Houston! We don't want to fly back to cities that we have already visited; this could cause an infinite loop. Our algorithm must take care of cycling. That is, we must mark a city as having been visited so that it is not investigated a second time. Let's assume that we have marked the cities that have already been tried, and continue our example. Houston has already been visited, so we ignore it. The second adjacent vertex, Washington, has not been visited so we push it onto the stack (Figure 9.11d). Again we pop the top vertex from the stack. Washington is our destination, so the search is complete. The path from Austin to Washington, using a depth-first search, is illustrated in Figure 9.12.
This search is called a depth-first search because we go to the deepest branch, examining all paths beginning at Houston before we come back to search from Dallas. When you have to backtrack, you take the branch closest to where you dead-ended. That is, you go as far as you can down one path before you take alternative choices at earlier branches.
Before we look at the source code of the depth-first search algorithm, let's talk a little more about "marking" vertices on the graph. Before we begin the search, we must clear any marks in the vertices to indicate they are not yet visited. Let's call this function ClearMarks. As we visit each vertex during the search, we mark it. Let's call this function MarkVertex. Before we process each vertex, we can ask, "Have we visited this vertex before?" The answer to this question is returned by the function IsMarked. If we have already visited this vertex, we ignore it and go on. We must add these three functions to the specifications of the Graph ADT.
The function DepthFirstSearch receives a graph object, a starting vertex, and a target vertex. It uses the depth-first strategy to determine whether a path connects the starting city to the ending city, displaying the names of all cities visited in the search. Note that nothing in the function depends on the implementation of the graph. The function is implemented as a graph application; it uses the Graph ADT operations (including the mark operations) without knowing how the graph is represented.
In the following function, we assume that the header files for StackType and QueType have been included. We also assume that VertexType is a type for which the "==" and the "<<" operators are defined.
template<class VertexType> void DepthFirstSearch(GraphType<VertexType> graph, VertexType startVertex, VertexType endVertex) // Assumes VertexType is a type for which the "==" and "<<" // operators are defined. { using namespace std; StackType<VertexType> stack; QueType<VertexType> vertexQ; bool found = false; VertexType vertex; VertexType item; graph.ClearMarks(); stack.Push(startVertex); do { stack.Pop(vertex); if (vertex == endVertex) { cout << vertex; found = true; } else { if (!graph.IsMarked(vertex)) { graph.MarkVertex(vertex); cout << vertex; graph.GetToVertices(vertex, vertexQ); while (!vertexQ.IsEmpty()) { vertexQ.Dequeue(item); if (!graph.IsMarked(item)) stack.Push(item); } } } } while (!stack.IsEmpty() && !found); if (!found) cout << "Path not found." << end1; }
Breadth-First Searching 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 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 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 an appropriate 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 the 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. Searching for a path from Austin to Washington, we first enqueue all cities that can be reached directly from Austin: Dallas and Houston (Figure 9.13a). Then we dequeue the front queue element. Dallas is not the destination we seek, so we enqueue all adjacent cities that have not yet been visited: Chicago and Denver (Figure 9.13b). (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. Houston is not the desired destination, so we continue the search. Only one flight goes out of Houston, to Atlanta. Because we haven't visited Atlanta before, it is enqueued (Figure 9.13c).
Now we know that we cannot reach Washington with one stop, so we start examining the two-stop connections. We dequeue Chicago; this is not our destination, so we put its adjacent city, Denver, into the queue (Figure 9.13d). Now an interesting situation arises: Denver is in the queue twice. Should we mark a city as having been visited when we put it in the queue or after it has been dequeued, when we are examining its outgoing flights? If we mark it only after it is dequeued, the queue may include multiple copies of the same vertex (so we need to check whether a city is marked after it is dequeued).
An alternative approach is to mark the city as having been visited before it is put into the queue. Which technique is better? It depends on the processing. You may want to know whether alternative routes exist, in which case you would want to put a city into the queue more than once.
Back to our example. We have put Denver into the queue in one step and removed its previous entry at the next step. Denver is not our destination, so we put its adjacent cities that we haven't already marked (only Atlanta) into the queue (Figure 9.13e). This processing continues until Washington is put into the queue (from Atlanta) and finally dequeued. We have found the desired city, and the search is complete. This search is illustrated in Figure 9.14.
The source code for the BreadthFirstSearch function is identical to that for the depth-first search, except for the replacement of the stack with a FIFO queue.
template<class VertexType> void BreadthFirstSearch(GraphType<VertexType> graph, VertexType startVertex, VertexType endVertex) // Assumption: VertexType is a type for which the "==" and // "<<" operators are defined. { using namespace std; QueType<VertexType> queue; QueType<VertexType> vertexQ; bool found = false; VertexType vertex; VertexType item; graph.ClearMarks(); queue.Enqueue(startVertex); do { queue.Dequeue(vertex); if (vertex == endVertex) { cout << vertex; found = true; } else { if (!graph.IsMarked(vertex)) { graph.MarkVertex(vertex); cout << vertex; graph.GetToVertices(vertex, vertexQ); while (!vertexQ.IsEmpty()) { vertexQ.Dequeue(item); if (!graph.IsMarked(item)) queue.Enqueue(item); ) } } } while (!queue.IsEmpty() && !found); if (!found) cout << "Path not found." << end1; }
The Single-Source Shortest-Path Problem We know from the two search operations just discussed that multiple paths may connect one vertex to another. Suppose that we want to find the shortest path from Austin to each of the other cities that Air Busters serves. By "shortest path," we mean the path whose edge values (weights), when added together, have the smallest sum. Consider the following two paths from Austin to Washington:
Clearly, the first path is preferable, unless you want to collect frequent-flyer miles.
Let's develop an algorithm that displays the shortest path from a designated starting city to every other city in the graph-this time we will not search for a path between a starting city and an ending city. As in the two graph searches described earlier, we need an auxiliary structure for storing cities that we process later. By retrieving the city that was most recently put into the structure, the depth-first search tries to keep going "forward." It tries a one-flight solution, then a two-flight solution, then a three-flight solution, and so on. It backtracks to a fewer-flight solution only when it reaches a dead end. In contrast, by retrieving the city that has been in the structure for the longest time, the breadth-first search tries all one-flight solutions, then all two-flight solutions, and so on. The breadth-first search finds a path with a minimum number of flights.
But the minimum number of flights does not necessarily mean the minimum total distance. Unlike the depth-first and breadth-first searches, the shortest-path traversal must use the number of miles (edge weights) between cities. We want to retrieve the vertex that is closest to the current vertex-that is, the vertex connected with the minimum edge weight. If we consider minimum distance to be the highest priority, then we know of a perfect structure-the priority queue. Our algorithm can use a priority queue whose elements are flights (edges) with the distance from the starting city as the priority. That is, the items on the priority queue are struct variables with three data members: fromVertex, toVertex, and distance.
The algorithm for the shortest-path traversal is similar to those we used for the depth-first and breadth-first searches, albeit with two major differences:
We use a priority queue rather than a FIFO queue or a stack.
We stop only when there are no more cities to process; we have no destination.
Here is the source code for the shortest-path algorithm. This code assumes that the header files for QueType and PQType have been included. Notice that ItemType (the type of the items to be placed into the priority queue) must overload the relational operators such that a smaller distance indicates a higher priority. As a result, the priority queue is implemented with a minimum heap. That is, for every item in the heap, item.distance is less than or equal to the distance member of each of its children.
template<class VertexType> struct ItemType { bool operator<(ItemType otherItem); // "<" means shorter distance. bool operator==(ItemType otherItem); bool operator<=(ItemType otherItem); VertexType fromVertex; VertexType toVertex; int distance; }; template<class VertexType> void ShortestPath(GraphType<VertexType> graph, VertexType startVertex) { using namespace std; ItemType item; int minDistance: PQType<VertexType> pq(10); // Assume at most 10 vertices. QueType<VertexType> vertexQ; VertexType vertex; graph.ClearMarks(); item.fromVertex = startVertex; item.toVertex = startVertex; item.distance = 0; pq.Enqueue(item); cout << "Last Vertex Destination Distance" << end1; cout << "----------------------------------" << end1; do { pq.Dequeue(item); if (!graph.IsMarked(item.toVertex)) { graph.MarkVertex(item.toVertex); cout << item.fromVertex; cout << " "; cout << item.toVertex; cout << " " << item.distance << end1; item.fromVertex = item.toVertex; minDistance = item.distance; graph.GetToVertices(item.fromVertex, vertexQ); while (!vertexQ.IsEmpty()) { vertexQ.Dequeue(vertex); if (!graph.IsMarked(vertex)) { item.toVertex = vertex; item.distance = minDistance + graph.WeightIs(item.fromVertex, vertex); pq.Enqueue(item); } } } } while (!pq.IsEmpty()); }
The output from this function is a table of city pairs (edges), showing the total distance from startVertex to each of the other vertices in the graph, as well as the last vertex visited before the destination. If graph contains the information shown in Figure 9.10, the function call
ShortestPath(graph, startVertex);
where startVertex corresponds to Washington, would print a table like this:
Last Vertex |
Destination |
Distance |
---|---|---|
Washington |
Washington |
0 |
Washington |
Atlanta |
600 |
Washington |
Dallas |
1300 |
Atlanta |
Houston |
1400 |
Dallas |
Austin |
1500 |
Dallas |
Denver |
2080 |
Dallas |
Chicago |
2200 |
The shortest-path distance from Washington to each destination appears in the second and third columns. For example, our flights from Washington to Chicago total 2,200 miles. The first column shows which city immediately preceded the destination in the traversal.
Let's figure out the shortest path from Washington to Chicago. We see from the first column that the next-to-last vertex in the path is Dallas. Now we look up Dallas in the Destination (second) column: The vertex before Dallas is Washington. The whole path is Washington-Dallas-Chicago. (We might want to consider another airline for a more direct route!)
Array-Based Implementation A simple way to represent V(graph), the vertices in the graph, is with an array where the elements are of the type of the vertices (VertexType). For example, if the vertices represent cities, VertexType would be some representation of strings. A simple way to represent E(graph), the edges in a graph, is with an adjacency matrix, a two-dimensional array of edge values (weights). Thus a graph consists of a data member numVertices, a one-dimensional array vertices, and a two-dimensional array edges. Figure 9.15 depicts the implementation of the graph of Air Busters flights between seven cities. For simplicity, we omit additional Boolean data needed to mark vertices as "visited" during a traversal. While the city names in Figure 9.15 are in alphabetical order, there is no requirement that the elements in this array be sorted.
Adjacency matrix For a graph with N nodes, an N by N table that shows the existence (and weights) of all edges in the graph
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] . . vertices [numVertices - 1].
E(graph) is contained in the square array edges [0] [0] . . edges [numVertices - 1][numVertices - 1].
The names of the cities are contained in graph.vertices. The weight of each edge in graph.edges represents the air distance between two cities that are connected by a flight. For example, the value in graph.edges [1] [3] tells us that a direct flight goes between Austin and Dallas, and that the air distance is 200 miles. A NULL_EDGE value (0) in graph.edges [1] [6] tells us that the airline has no direct flights between Austin and Washington. Because this is a weighted graph with the weights consisting of air distances, we use the int type for EdgeValueType. If this were not a weighted graph, EdgeValueType would be bool, and each position in the adjacency matrix would be true if an edge exists between the pair of vertices and false if no edge exists.
Here is the definition of the class GraphType. For simplicity, we assume that EdgeValueType is int.
template<class VertexType> // Assumption: VertexType is a type for which the "=", // "==", and "<<" operators are defined. class GraphType { public: GraphType(); // Default is 50 vertices GraphType(int maxV); // maxV <= 50 ~GraphType(); void MakeEmpty(); bool IsEmpty() const; bool IsFull() const; void AddVertex(VertexType); void AddEdge(VertexType, VertexType, int); int WeightIs(VertexType, VertexType); void GetToVertices(VertexType, QueType<VertexType>&); void ClearMarks(); void MarkVertex(VertexType); bool IsMarked(VertexType); private: int numVertices; int maxVertices; VertexType* vertices; int edges[50][50] ; bool* marks; // marks[i] is the mark for vertices[i]. };
The class constructors are usually the easiest operations to write, but not for GraphType. We have to allocate the space for vertices and marks (the Boolean array indicating whether a vertex has been marked). The default constructor sets up space for 50 vertices and marks. The parameterized constructor lets the user specify the maximum number of vertices. Why don't we put edges in dynamic storage? We could, but allocating storage for a two-dimensional array is rather complex, and we do not wish to divert our attention from the main issue: the Graph ADT.
template<class VertexType> GraphType<VertexType>::GraphType() // Post: Arrays of size 50 are dynamically allocated for // marks and vertices. numVertices is set to 0: // maxVertices is set to 50. { numVertices = 0; maxVertices = 50; vertices = new VertexType[50]; marks = new bool[50]; } template<class VertexType> GraphType<VertexType>::GraphType(int maxV) // Post: Arrays of size maxV are dynamically allocated for // marks and vertices. // numVertices is set to 0; maxVertices is set to maxV. { numVertices = 0; maxVertices = maxV; vertices = new VertexType[maxV]; marks = new bool[maxV]; } } template<class VertexType> GraphType<VertexType>::~GraphType() // Post: Arrays for vertices and marks have been deallocated. { delete [] vertices; delete [] marks; }
The AddVertex operation puts vertex into the next free space in the array of vertices. Because the new vertex has no edges defined yet, we also initialize the appropriate row and column of edges to contain NULL_EDGE (0 in this case).
const int NULL_EDGE = 0; template<class VertexType> void GraphType<VertexType>::AddVertex(VertexType vertex) // Post: vertex has been stored in vertices. // Corresponding row and column of edges have been set // to NULL_EDGE. // numVertices has been incremented. { 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 we want to add. These parameters to AddEdge are of type VertexType. To index the correct matrix slot, we need the index in the vertices array that corresponds to each vertex. Once we know the indexes, it is a simple matter to set the weight of the edge in the matrix. Here is the algorithm:
To find the index of each vertex, let's write a search function that receives the name of a vertex and returns its location (index) in vertices. Because the precondition of AddEdge states that fromVertex and toVertex are in V(graph), the search function is very simple. We code it as the helper function IndexIs:
template<class VertexType> int IndexIs(VertexType* vertices, VertexType vertex) // Post: Returns the index of vertex in vertices. { int index = 0; while (!(vertex == vertices[index])) index++; return index; } template<class VertexType> void GraphType<VertexType>::AddEdge(VertexType fromVertex, VertexType toVertex, int weight) // Post: Edge (fromVertex, toVertex) is stored in edges. { int row; int col; row = IndexIs(vertices, fromVertex); col = IndexIs(vertices, toVertex); edges[row][col] = weight: }
The WeightIs operation is the mirror image of AddEdge:
template<class VertexType> int GraphType<VertexType>::WeightIs (VertexType fromVertex, VertexType toVertex) // Post: Returns the weight associated with the edge // (fromVertex, toVertex). { int row: int col; row = IndexIs(vertices, fromVertex); col = IndexIs(vertices, toVertex); return edges [row] [col] ; }
The last graph operation that we specified is GetToVertices. This function takes a vertex as a parameter, and returns a queue of vertices that are adjacent from the designated vertex. That is, it returns a queue of all vertices that you can reach from this vertex in one step. Using an adjacency matrix to represent the edges, it is a simple matter to determine the nodes 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 another vertex to the queue.
template<class VertexType> void GraphType<VertexType>::GetToVertices(VertexType vertex, QueType<VertexType>& adjVertices) // Post: Returns a queue of vertices adjacent from vertex. { int fromIndex; int toIndex; fromIndex = IndexIs(vertices, vertex); for (toIndex = 0; toIndex < numVertices; toIndex++) if (edges[fromIndex][toIndex] != NULL_EDGE) adjVertices.Enqueue(vertices[toIndex]): }
We leave the completion and testing of this implementation as a programming assignment.
Linked Implementation The advantages to representing the edges in a graph with an adjacency matrix relate to its speed and simplicity. Given the indexes 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 is O(N^{2}), where N is the maximum number of vertices in the graph. If the maximum number of vertices is large, adjacency matrices may waste a lot of space.
In the past, we have tried to save space by allocating memory as we need it at run time, using linked structures. We can use a similar approach when implementing graphs. Adjacency lists are linked lists, one list per vertex, that identify the vertices to which each vertex is connected. You can implement adjacency lists in several ways. Figure 9.16 shows two adjacency list representations of the graph in Figure 9.10.
Adjacency list A linked list that identifies all vertices to which a particular vertex is connected; each vertex has its own adjacency list
In Figure 9.16(a), the vertices are stored in an array. Each component of this array contains a pointer to a linked list of edge nodes. Each node in these linked lists contains an index number, a weight, and a pointer to the next node in the adjacency list. Let's look at the adjacency list for Denver. The first node in the list indicates that a 1,400-mile flight goes from Denver to Atlanta (the vertex whose index is 0) and a 1,000-mile flight goes from Denver to Chicago (the vertex whose index is 2).
The implementation illustrated in Figure 9.16(b) does not use any arrays. Instead, the list of vertices is implemented as a linked list. Now each node in the adjacency lists contains a pointer to the vertex information rather than the index of the vertex. Because so many of these pointers appear in Figure 9.16(b), we have used text to describe the vertex that each pointer designates rather than draw them as arrows.
We leave the implementation of the GraphType member functions using these implementations as Programming Assignments 3 and 4, Chapter 9.
< Free Open Study > |
Converted from CHM to HTML with chm2web Pro 2.85 (unicode) |