(See related pages)
|
|
|
| An undirected graph consists of a collection of distinct elements called vertices, connected
to other elements by distinct vertex-pairs called edges. If the pairs are ordered,
we have a directed graph.A tree, sometimes called a directed tree, is a directed graph
that either is empty or has an element, called the root element such that:
1. There are no edges coming into the root element. 2. Every nonroot element has exactly one edge coming into it. 3. There is a path from the root to every other element. A network (or undirected network) is a directed graph (or undirected graph) in which each edge has an associated nonnegative number called the weight of the edge. Some of the important graph/network algorithms are: 1. Breadth-first iteration of all vertices reachable from a given vertex. 2. Depth-first iteration of all vertices reachable from a given vertex. 3. Determining if a given graph is connected, that is, if for any two vertices, there is a path from the first vertex to the second. 4. Finding a minimum spanning tree for a network. 5. Finding a shortest path between two vertices in a network. One possible implementation of the Network class is to associate, in a HashMap object, each vertex with its neighbors. Specifically, we declare HashMap<Vertex, LinkedList<VertexWeightPair>>adjacencyMap; Here, adjacencyMap is a HashMap object in which each key is a Vertex object v and each value is a LinkedList object of vertex-weight pairs, <w, weight>, where weight is the weight of edge <v, w>. This is referred to as the adjacency-list implementation. An alternative implementation, the adjacency-matrix implementation, stores the weights in a two-dimensional array with V rows and V columns, where V is the number of vertices. Specifically, the weight of the edge connecting vertex i and vertex j is stored at adjacencyMatrix [i] [j]. The trade-off for this vertex restriction is that some methods—such as containsEdge—take only constant time, even if the number of edges is quadratic in V. With the adjacency-list implementation, the containsEdge method requires linear-in-V time if the number of edges is quadratic in V. Some network problems can be solved through backtracking. The iteration around a given position corresponds to an iteration through the linked list of vertexweight pairs that comprise the neighbors of a given vertex. |