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
.html , as shown in Figure  28.4. The tool allows you to add/remove/move vertices and
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