DATA STRUCTURES AND
ALGORITHMS
Graphs and Applications
What is a graph?
• A graph is a mathematical structure that represents
relationships among entities in the real world.
• The graph in the following slide represents the flights among
cities.
Modeling Using Graphs
3
Graph Animation
[Link]
4
Basic Graph Terminologies
What is a graph? G=(V, E)
Define a graph
Directed vs. undirected graphs
Weighted vs. unweighted graphs
Adjacent vertices
Incident (Two edges sharing the same common point)
Degree (The number of edges of a point)
Neighbor
Loop ( a loop is an edge that connects a vertex to itself)
5
Directed vs Undirected Graph
Peter Jane
Cindy Mark
Wendy
6
Basic Graph Terminologies
• Parallel edge: If two vertices are connected by two or more Edges
• Simple graph : is one that doesn’t have any loops or parallel edges.
• Complete graph: every two pairs of vertices are connected
• Spanning tree of a graph G is a connected subgraph of G, and the
subgraph is a tree that contains all vertices in G.
A D
A D
B E
B E
7
Representing Graphs
Representing Vertices
Representing Edges: Edge Array
Representing Edges: Edge Objects
Representing Edges: Adjacency Matrices
Representing Edges: Adjacency Lists
8
Representing Vertices
String[] vertices = {“Seattle“, “San Francisco“, “Los Angles”,
“Denver”, “Kansas City”, “Chicago”, … };
City[] vertices = {city0, city1, … };
public class City {
List<String> vertices;
9
Representing Edges: Edge Array
int[][] edges = {{0, 1}, {0, 3} {0, 5}, {1, 0}, {1, 2}, … };
10
Representing Edges: Edge Object
public class Edge {
int u, v;
public Edge(int u, int v) {
this.u = u;
this.v = v;
}
List<Edge> list = new ArrayList<>();
[Link](new Edge(0, 1));
[Link](new Edge(0, 3)); …
11
Representing Edges: Adjacency Matrix
int[][] adjacencyMatrix = {
{0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0}, // Seattle
{1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}, // San Francisco
{0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0}, // Los Angeles
{1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0}, // Denver
{0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0}, // Kansas City
{1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0}, // Chicago
{0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0}, // Boston
{0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0}, // New York
{0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1}, // Atlanta
{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1}, // Miami
{0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1}, // Dallas
{0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0} // Houston
};
12
Representing Edges: Adjacency Vertex List
List<Integer>[] neighbors = new List[12];
Seattle neighbors[0] 1 3 5
San Francisco neighbors[1] 0 2 3
Los Angeles neighbors[2] 1 3 4 10
Denver neighbors[3] 0 1 2 4 5
Kansas City neighbors[4] 2 3 5 7 8 10
Chicago neighbors[5] 0 3 4 6 7
Boston neighbors[6] 5 7
New York neighbors[7] 4 5 6 8
Atlanta neighbors[8] 4 7 9 10 11
Miami neighbors[9] 8 11
Dallas neighbors[10] 2 4 8 11
Houston neighbors[11] 8 9 10
List<List<Integer>> neighbors = new ArrayList<>();
13
Representing Edges: Adjacency Edge List
List<Edge>[] neighbors = new List[12];
Seattle neighbors[0] Edge(0, 1) Edge(0, 3) Edge(0, 5)
San Francisco neighbors[1] Edge(1, 0) Edge(1, 2) Edge(1, 3)
Los Angeles neighbors[2] Edge(2, 1) Edge(2, 3) Edge(2, 4) Edge(2, 10)
Denver neighbors[3] Edge(3, 0) Edge(3, 1) Edge(3, 2) Edge(3, 4) Edge(3, 5)
Kansas City neighbors[4] Edge(4, 2) Edge(4, 3) Edge(4, 5) Edge(4, 7) Edge(4, 8) Edge(4, 10)
Chicago neighbors[5] Edge(5, 0) Edge(5, 3) Edge(5, 4) Edge(5, 6) Edge(5, 7)
Boston neighbors[6] Edge(6, 5) Edge(6, 7)
New York neighbors[7] Edge(7, 4) Edge(7, 5) Edge(7, 6) Edge(7, 8)
Atlanta neighbors[8] Edge(8, 4) Edge(8, 7) Edge(8, 9) Edge(8, 10) Edge(8, 11)
Miami neighbors[9] Edge(9, 8) Edge(9, 11)
Dallas neighbors[10] Edge(10, 2) Edge(10, 4) Edge(10, 8) Edge(10, 11)
Houston neighbors[11] Edge(11, 8) Edge(11, 9) Edge(11, 10)
14
«interface» The generic type V is the type for vertices.
Graph<V>
+getSize(): int Returns the number of vertices in the graph.
+getVertices(): List<V> Returns the vertices in the graph.
+getVertex(index: int): V Returns the vertex object for the specified vertex index.
+getIndex(v: V): int Returns the index for the specified vertex.
+getNeighbors(index: int): List<Integer> Returns the neighbors of vertex with the specified index.
+getDegree(index: int): int Returns the degree for a specified vertex index.
+printEdges(): void
Prints the edges.
+clear(): void Clears the graph.
+addVertex(v: V): boolean Returns true if v is added to the graph. Returns false if v
is already in the graph.
+addEdge(u: int, v: int): boolean 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 Graph
the graph.
Adds an edge into the adjacency edge list.
+addEdge(e: Edge): boolean
+remove(v: V): boolean Removes a vertex from the graph.
+remove(u: int, v: int): boolean Removes an edge from the graph.
+dfs(v: int): UnWeightedGraph<V>.SearchTree Obtains a depth-first search tree starting from v.
+bfs(v: int): UnWeightedGraph<V>.SearchTree Obtains a breadth-first search tree starting from v.
.
UnweightedGraph<V>
#vertices: List<V>
#neighbors: List<List<Edge>>
Vertices in the graph.
Neighbors for each vertex in the graph.
UnweightedGraph
+UnweightedGraph() Constructs an empty graph.
+UnweightedGraph(vertices: V[], edges: Constructs a graph with the specified edges and vertices
int[][]) stored in arrays.
+UnweightedGraph(vertices: List<V>, Constructs a graph with the specified edges and vertices
edges: List<Edge>)
stored in lists.
+UnweightedGraph(edges: int[][], Constructs a graph with the specified edges in an array
and the integer vertices 1, 2, ....
TestGraph
numberOfVertices: int)
+UnweightedGraph(edges: List<Edge>, Constructs a graph with the specified edges in a list and
numberOfVertices: int) the integer vertices 1, 2, ….
15
Graph Example
Graph Example
Graph Example
Output:
The number of vertices in graph1: 12
The vertex with index 1 is San Francisco
The index for Miami is 9
The edges for graph1:
Seattle (0): (Seattle, San Francisco) (Seattle, Denver) (Seattle, Chicago)
San Francisco (1): (San Francisco, Seattle) (San Francisco, Los Angeles) (San Francisco, Denver)
Los Angeles (2): (Los Angeles, San Francisco) (Los Angeles, Denver) (Los Angeles, Kansas City) (Los Angeles, Dallas)
Denver (3): (Denver, Seattle) (Denver, San Francisco) (Denver, Los Angeles) (Denver, Kansas City) (Denver, Chicago)
Kansas City (4): (Kansas City, Los Angeles) (Kansas City, Denver) (Kansas City, Chicago) (Kansas City, New York) (Kansas City, Atlanta) (Kansas City, Dallas)
Chicago (5): (Chicago, Seattle) (Chicago, Denver) (Chicago, Kansas City) (Chicago, Boston) (Chicago, New York)
Boston (6): (Boston, Chicago) (Boston, New York)
New York (7): (New York, Kansas City) (New York, Chicago) (New York, Boston) (New York, Atlanta)
Atlanta (8): (Atlanta, Kansas City) (Atlanta, New York) (Atlanta, Miami) (Atlanta, Dallas) (Atlanta, Houston)
Miami (9): (Miami, Atlanta) (Miami, Houston)
Dallas (10): (Dallas, Los Angeles) (Dallas, Kansas City) (Dallas, Atlanta) (Dallas, Houston)
Houston (11): (Houston, Atlanta) (Houston, Miami) (Houston, Dallas)
Graph Example
Graph Example
Output:
The number of vertices in graph2: 5
The edges for graph2:
Peter (0): (Peter, Mark)
Jane (1): (Jane, Mark)
Mark (2): (Mark, Wendy)
Cindy (3): (Cindy, Wendy)
Wendy (4):
Applications of the Graph
`
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.
21
References
1. Introduction to Java Programming and Data Structures,
comprehensive version 11th Edition, Y Daniel Liang, 2018
