Java Reference
In-Depth Information
0
2
6
7
4
1
3
5
Figure11.2 An undirected graph with three connected components. Vertices 0,
1, 2, 3, and 4 form one connected component. Vertices 5 and 6 form a second
connected component. Vertex 7 by itself forms a third connected component.
A subgraph S is formed from graph G by selecting a subset V s of G's vertices
and a subset E s of G's edges such that for every edge E in E s , both of E's vertices
are in V s .
An undirected graph is connected if there is at least one path from any vertex
to any other. The maximally connected subgraphs of an undirected graph are called
connected components. For example, Figure 11.2 shows an undirected graph with
three connected components.
A graph without cycles is called acyclic. Thus, a directed graph without cycles
is called a directed acyclic graph or DAG.
A free tree is a connected, undirected graph with no simple cycles. An equiv-
alent definition is that a free tree is connected and has jVj 1 edges.
There are two commonly used methods for representing graphs. The adja-
cency matrix is illustrated by Figure 11.3(b). The adjacency matrix for a graph
is a jVjjVj array. Assume that jVj = n and that the vertices are labeled from
v 0 through v n1 . Row i of the adjacency matrix contains entries for Vertex v i .
Column j in row i is marked if there is an edge from v i to v j and is not marked oth-
erwise. Thus, the adjacency matrix requires one bit at each position. Alternatively,
if we wish to associate a number with each edge, such as the weight or distance
between two vertices, then each matrix position must store that number. In either
case, the space requirements for the adjacency matrix are (jVj 2 ).
The second common representation for graphs is the adjacency list, illustrated
by Figure 11.3(c). The adjacency list is an array of linked lists. The array is
jVj items long, with position i storing a pointer to the linked list of edges for Ver-
tex v i . This linked list represents the edges by the vertices that are adjacent to
Vertex v i . The adjacency list is therefore a generalization of the “list of children”
representation for trees described in Section 6.3.1.
Example11.1 The entry for Vertex 0 in Figure 11.3(c) stores 1 and 4
because there are two edges in the graph leaving Vertex 0, with one going
 
Search WWH ::




Custom Search