Java Reference
In-Depth Information
a dot, called a
vertex
or a
node
, and each bridge with a line, called an
edge
, as shown in
Figure 28.2b. This structure with vertices and edges is called a
graph
.
Looking at the graph, we ask whether there is a path starting from any vertex, traversing
all edges exactly once, and returning to the starting vertex. Euler proved that for such a path
to exist, each vertex must have an even number of edges. Therefore, the Seven Bridges of
Königsberg problem has no solution.
Graph problems are often solved using algorithms. Graph algorithms have many appli-
cations in various areas, such as in computer science, mathematics, biology, engineering,
economics, genetics, and social sciences. This chapter presents the algorithms for depth-first
search and breadth-first search, and their applications. The next chapter presents the algo-
rithms for finding a minimum spanning tree and shortest paths in weighted graphs, and their
applications.
A graph consists of vertices, and edges that connect the vertices.
This chapter does not assume that you have any prior knowledge of graph theory or discrete
mathematics. We use plain and simple terms to define graphs.
What is a graph? A
graph
is a mathematical structure that represents relationships among
entities in the real world. For example, the graph in Figure 28.1 represents the flights among
cities, and the graph in Figure 28.2b represents the bridges among land masses.
A graph consists of a nonempty set of vertices (also known as
nodes
or
points
), and a set of
edges that connect the vertices. For convenience, we define a graph as G
Key
Point
what is a graph?
define a graph
(V, E), where V
represents a set of vertices and E represents a set of edges. For example, V and E for the graph
in Figure 28.1 are as follows:
=
V = {
"Seattle"
,
"San Francisco"
,
"Los Angeles"
,
"Denver"
,
"Kansas City"
,
"Chicago"
,
"Boston"
,
"New York"
,
"Atlanta"
,
"Miami"
,
"Dallas"
,
"Houston"
};
E = {{
"Seattle"
,
"San Francisco"
},{
"Seattle"
,
"Chicago"
},
{
"Seattle"
,
"Denver"
}, {
"San Francisco"
,
"Denver"
},
...
};
A graph may be directed or undirected. In a
directed graph
, each edge has a direction, which
indicates that you can move from one vertex to the other through the edge. You can model
parent/child relationships using a directed graph, where an edge from vertex A to B indicates
that A is a parent of B. Figure 28.3a shows a directed graph.
directed vs. undirected graphs
Peter (0)
Jane (1)
A
A
D
D
E
E
B
B
Cindy (3)
Mark (2)
C
C
Wendy (4)
(a) A directed graph
(b) A complete graph
(c) A subgraph of the graph in (b)
F
IGURE
28.3
Graphs may appear in many forms.
In an
undirected graph
, you can move in both directions between vertices. The graph in
Figure 28.1 is undirected.
Search WWH ::
Custom Search