Java Reference
In-Depth Information
Edges may be weighted or unweighted. For example, you can assign a weight for each edge
in the graph in Figure 28.1 to indicate the flight time between the two cities.
Two vertices in a graph are said to be
adjacent
if they are connected by the same edge.
Similarly, two edges are said to be
adjacent
if they are connected to the same vertex. An edge
in a graph that joins two vertices is said to be
incident
to both vertices. The
degree
of a vertex
is the number of edges incident to it.
Two vertices are called
neighbors
if they are adjacent. Similarly, two edges are called
neighbors
if they are adjacent.
A
loop
is an edge that links a vertex to itself. If two vertices are connected by two or more
edges, these edges are called
parallel edges
. A
simple graph
is one that has doesn't have any
loops or parallel edges. In a
complete graph
, every two pairs of vertices are connected, as
shown in Figure 28.3b.
A graph is
connected
if there exists a path between any two vertices in the graph. A
subgraph
of a graph
G
is a graph whose vertex set is a subset of that of
G
and whose edge set
is a subset of that of
G
. For example, the graph in Figure 28.3c is a subgraph of the graph in
Figure 28.3b.
Assume that the graph is connected and undirected. A
cycle
is a closed path that starts from
a vertex and ends at the same vertex. A connected graph is a
tree
if it does not have cycles.
A
spanning tree
of a graph
G
is a connected subgraph of
G
and the subgraph is a tree that
contains all vertices in G.
weighted vs. unweighted
graphs
adjacent vertices
incident edges
degree
neighbor
loop
parallel edge
simple graph
complete graph
connected graph
subgraph
cycle
tree
spanning tree
Pedagogical Note
Before we introduce graph algorithms and applications, it is helpful to get acquainted with
graphs using the interactive tool at
www.cs.armstrong.edu/liang/animation/GraphLearningTool
draw edges using mouse gestures. You can also find depth-first search (DFS) trees and
breadth-first search (BFS) trees, and a shortest path between two vertices.
graph learning tool on
Companion Website
F
IGURE
28.4
You can use the tool to create a graph with mouse gestures and show DFS/BFS trees and shortest paths.
Search WWH ::
Custom Search