COSC 3B
Chapter 28: Graphs and Applications
Dr. Adriana Badulescu
Objectives ▪ To model real-world problems using graphs and explain the Seven Bridges of
Königsberg problem (§28.1).
▪ To describe the graph terminologies: vertices, edges, simple graphs,
weighted/unweighted graphs, and directed/undirected graphs (§28.2).
▪ To represent vertices and edges using lists, edge arrays, edge objects, adjacency
matrices, and adjacency lists (§28.3).
▪ To model graphs using the Graph interface, the AbstractGraph class, and the
UnweightedGraph class (§28.4).
▪ To display graphs visually (§28.5).
▪ To represent the traversal of a graph using the AbstractGraph.Tree class (§28.6).
▪ To design and implement depth-first search (§28.7).
▪ To solve the connected-circle problem using depth-first search (§28.8).
▪ To design and implement breadth-first search (§28.9).
▪ To solve the nine-tail problem using breadth-first search (§28.10).
Modeling Using Graphs
Seven Bridges of Königsberg
Basic Graph Terminologies
What is a graph? G=(V, E)
Define a graph
Directed vs. undirected graphs
Weighted vs. unweighted graphs
Adjacent vertices
Incident
Degree
Neighbor
loop
Directed vs Undirected Graph
Peter
Cindy
Wendy
Mark
Jane
Basic Graph Terminologies Parallel edge
Simple graph
Complete graph
Spanning tree
Representing Graphs Representing Vertices
Representing Edges: Edge Array
Representing Edges: Edge Objects
Representing Edges: Adjacency Matrices
Representing Edges: Adjacency Lists
Representing Vertices
Representing Edges: Edge Array
int[][] edges = {{0, 1}, {0, 3} {0, 5}, {1, 0}, {1, 2}, … };
Representing Edges: Edge Object
Representing Edges: Adjacency Matrix
Representing Edges: Adjacency Vertex List
Representing Edges: Adjacency Edge List
Representing Adjacency Edge List Using ArrayList
Modeling Graphs
Graph WeightedGraph UnweightedGraph
«interface» Graph<V>
+getSize(): int
+getVertices(): List<V>
+getVertex(index: int): V
+getIndex(v: V): int
+getNeighbors(index: int): List<Integer>
+getDegree(index: int): int
+printEdges(): void
+clear(): void
+addVertex(v: V): boolean
+addEdge(u: int, v: int): boolean
+addEdge(e: Edge): boolean
+remove(v: V): boolean
+remove(u: int, v: int): boolean
+dfs(v: int): UnWeightedGraph<V>.SearchTree
+bfs(v: int): UnWeightedGraph<V>.SearchTree
Returns the number of vertices in the graph.
Returns the vertices in the graph.
Returns the vertex object for the specified vertex index.
Returns the index for the specified vertex.
Returns the neighbors of vertex with the specified index.
Returns the degree for a specified vertex index.
Prints the edges.
Clears the graph.
Returns true if v is added to the graph. Returns false if v
is already in the graph.
Adds an edge from u to v to the graph throws IllegalArgumentException if u or v is invalid. Returns
true if the edge is added and false if (u, v) is already in
the graph.
Adds an edge into the adjacency edge list.
Removes a vertex from the graph.
Removes an edge from the graph.
Obtains a depth-first search tree starting from v.
Obtains a breadth-first search tree starting from v.
.
UnweightedGraph<V>
#vertices: List<V>
#neighbors: List<List<Edge>>
+UnweightedGraph()
+UnweightedGraph(vertices: V[], edges:
int[][])
+UnweightedGraph(vertices: List<V>,
edges: List<Edge>)
+UnweightedGraph(edges: int[][],
numberOfVertices: int)
+UnweightedGraph(edges: List<Edge>,
numberOfVertices: int)
Vertices in the graph.
Neighbors for each vertex in the graph.
Constructs an empty graph.
Constructs a graph with the specified edges and vertices
stored in arrays.
Constructs a graph with the specified edges and vertices
stored in lists.
Constructs a graph with the specified edges in an array
and the integer vertices 1, 2, ....
Constructs a graph with the specified edges in a list and
the integer vertices 1, 2, ….
The generic type V is the type for vertices.
TestGraph
UnweightedGraph
Graph
Graph
Graph Visualization
DisplayUSMapGraphView Displayable
Graph Traversals Depth-first search and breadth-first search Both traversals result in a spanning tree, which can be modeled using a class.
UnweightedGraph<V>.SearchTree
-root: int
-parent: int[]
-searchOrder: List<Integer>
+SearchTree(root: int, parent:
int[], searchOrder: List<Integer>)
+getRoot(): int
+getSearchOrder(): List<Integer>
+getParent(index: int): int
+getNumberOfVerticesFound(): int
+getPath(index: int): List<V>
+printPath(index: int): void
+printTree(): void
The root of the tree.
The parents of the vertices.
The orders for traversing the vertices.
Constructs a tree with the specified root, parent, and
searchOrder.
Returns the root of the tree.
Returns the order of vertices searched.
Returns the parent for the specified vertex index.
Returns the number of vertices searched.
Returns a list of vertices from the specified vertex index
to the root.
Displays a path from the root to the specified vertex.
Displays tree with the root and all edges.
Depth-First Search The depth-first search of a graph is like the depth-first search of a tree discussed in §25.2.3, “Tree Traversal.” In the case of a tree, the search starts from the root. In a graph, the search can start from any vertex.
Input: G = (V, E) and a starting vertex v
Output: a DFS tree rooted at v
Tree dfs(vertex v) {
visit v;
for each neighbor w of v
if (w has not been visited) {
set v as the parent for w;
dfs(w);
}
}
Depth-First Search Example
Depth-First Search Example
Applications of the DFS ▪ Detecting whether a graph is connected. Search the graph starting from
any vertex. If the number of vertices searched is the same as the number of vertices in the graph, the graph is connected. Otherwise, the graph is not connected.
▪ Detecting whether there is a path between two vertices. ▪ Finding a path between two vertices. ▪ Finding all connected components. A connected component is a
maximal connected subgraph in which every pair of vertices are connected by a path.
▪ Detecting whether there is a cycle in the graph. ▪ Finding a cycle in the graph.
The Connected Circles Problem
ConnectedCircles
Breadth-First Search
The breadth-first traversal of a graph is like the breadth- first traversal of a tree discussed in §25.2.3, “Tree Traversal.” With breadth-first traversal of a tree, the nodes are visited level by level. First the root is visited, then all the children of the root, then the grandchildren of the root from left to right, and so on.
Breadth-First Search Algorithm Input: G = (V, E) and a starting vertex v Output: a BFS tree rooted at v
bfs(vertex v) {
create an empty queue for storing vertices to be visited;
add v into the queue;
mark v visited;
while the queue is not empty {
dequeue a vertex, say u, from the queue
process u;
for each neighbor w of u
if w has not been visited {
add w into the queue;
set u as the parent for w;
mark w visited;
}
}
}
Breadth-First Search Example
Applications of the BFS
▪ Detecting whether a graph is connected. A graph is connected if there is a path between any two vertices in the graph.
▪ Detecting whether there is a path between two vertices. ▪ Finding a shortest path between two vertices. You can prove that the path
between the root and any node in the BFS tree is the shortest path between the root and the node.
▪ Finding all connected components. A connected component is a maximal connected subgraph in which every pair of vertices are connected by a path.
▪ Detecting whether there is a cycle in the graph. ▪ Finding a cycle in the graph. ▪ Testing whether a graph is bipartite. A graph is bipartite if the vertices of the
graph can be divided into two disjoint sets such that no edges exist between vertices in the same set.
The Nine Tail Problem The problem is stated as follows. Nine coins are placed in a three by three matrix with some face up and some face down. A legal move is to take any coin that is face up and reverse it, together with the coins adjacent to it (this does not include coins that are diagonally adjacent). Your task is to find the minimum number of the moves that lead to all coins face down.
Representing Nine Coins
Model the Nine Tail Problem
NineTailModel
NineTailModel
#tree: AbstractGraph<Integer>.Tree
+NineTailModel()
+getShortestPath(nodeIndex: int):
List<Integer>
-getEdges():
List<AbstractGraph.Edge>
+getNode(index: int): char[]
+getIndex(node: char[]): int
+getFlippedNode(node: char[],
position: int): int
+flipACell(node: char[], row: int,
column: int): void
+printNode(node: char[]): void
A tree rooted at node 511.
Constructs a model for the nine tails problem and obtains the tree.
Returns a path from the specified node to the root. The path returned
consists of the node labels in a list.
Returns a list of Edge objects for the graph.
Returns a node consisting of nine characters of Hs and Ts.
Returns the index of the specified node.
Flips the node at the specified position and returns the index of the
flipped node.
Flips the node at the specified row and column.
Displays the node on the console.
NineTailNineTailModel