11. Graph
Graphs are a special type of data structure.
They are used to solve many problems, such as the shortest path problem.
However, if the implementation is not done carefully it can be too slow to use.
11.1. What is a graph?
We will start by giving a definition of a graph.
Definition: Graph
A graph \(G = (V,E)\) consists of a set of vertices \(V\) and a set of edges \(E\).
Each edge is a pair \((v, w)\), where \(v,w\in V\).
Edges are sometimes referred as arcs and vertices as nodes.
Example
In this example we have \(V = \{1, 2, 3\}\).
11.1.1. Directed Graphs
Definition: Directed Graph
When the edges (or arcs) \((v,w)\) are ordered the graph is directed.
Vertex \(w\) is adjacent to \(v\) if and only if \((v,w)\in E\).
Directed graphs are also referred as digraphs.
The following figure represents a digraph:
Activity
Write all the pairs \((v,w) \in E\) of the previous graph.
11.1.2. Undirected Graphs
If there are directed graphs, there are undirected graphs!
Definition: Undirected Graph
In an undirected graph with edges \((v,w)\in E\), there is an edge \((w,v)\in E\).
\(w\) is adjacent to \(v\) and \(v\) is adjacent to \(w\).
Activity
Take the previous graph and transform it to an undirected graph.
Draw the undirected graph that contains the following edges:
\(E = \{(a,b), (b,a), (a,c), (c,a), (b,c), (c,b)\}\)
11.2. Representing graph in memory
Obviously, we cannot represent a graph like this in memory.
We could be as close as possible to the math representation:
Storing a list of nodes
And storing the list of arcs.
Activity
What do you think about this representation?
Do you have a better representation?
There are two ways to represent a graph in memory:
Adjacency matrix
Adjacency list
11.2.1. Adjacency Matrix
The easiest way to represent is with a 2D matrix.
This is called an adjacency matrix.
The idea:
Consider a matrix \(M\).
For each \((u,v) \in E\):
We set \(M[u][v]\) to 1.
Otherwise to 0.
Example
If we take the previous graph.
We can create the following adjacency matrix.
It is very easy to use adjacency matrix and very fast.
However, the space requirement is \(O(|V|^2)\).
It is a lot if the graph has an important number of nodes, but few arcs.
It is appropriate if the graph is dense \(|E| = O(|V|^2)\).
Activity
Why using a matrix for dense graphs is not a problem?
In most problems, graphs are not dense.
Example
Consider a street map of a city.
Assume a Manhattan-like orientation.
Any intersection is attached to roughly 4 streets.
So, if the graph is directed with two-way streets.
The number of edges is \(|E| \approx 4|V|\)
If there are 3 000 intersection.
The number of vertices is 3 000.
And the number of edges is 12 000.
It requires an array of size 9 000 000.
A graph that is not dense is called sparse.
We need another way to represent sparse graph.
11.2.2. Adjacency List
Adjacency list is a better solution when the graph is sparse.
For each vertex, we keep a list of all adjacent vertices.
Example
If we take the previous graph.
We can create the following adjacency list.
The space requirement is \(O(|E|+|V|)\).
It is linear in the size of the graph.
Activity
Why are we not using adjacency lists for dense graphs?
11.2.3. Weighted edges
Consider a problem in which you need to represent the streets and intersections in a city.
You would like to store the distance of each street.
A graph allows us to add weights on edges.
The changes to the previous representation are small:
Adjacency matrix: Instead of 0 and 1, we have the weight of the edge if it exists. If not \(- \infty\) or \(+ \infty\).
Adjacency list: Add a new element in the list.
Activity
Draw the directed graph that contains the following edges:
\(E = \{(a,b,2), (b,a,4), (a,c,3), (c,a,1), (b,c,10)\}\)
Give the adjacency matrix and adjacency lists representation.
11.3. Implementation
Java does not provide an implementation of the Graph ADT.
We will write our own!
We want our ADT to be able to do the following:
Create a graph with the specified number of vertices.
Iterate through all the vertices in the graph.
Iterate through the vertices that are adjacent to a specified vertex.
Determine whether an edge exists between two vertices.
Determine the weight of an edge between two vertices.
Insert an edge into the graph.
11.3.1. The Graph interface
We want to define a Graph interface that will not depend of the memory representation.
It will have the following methods:
int getNumV()
: Returns the number of vertices in the graphint isDirected()
: Return if the graph is directedIterator<Edge> edgeIterator(int source)
: Returns an iterator to the edges that originate from a given vertexEdge getEdge(int source, int dest)
: Gets the edge between two verticesvoid insert(Edge e)
: Insert a new edge into graphboolean isEdge(int source, int dest)
: Determines whether an edge exists fromsource
todest
default void loadEdgesFromFile(Scanner scan)
: A default method that loads the edges from a file associated withscan
1package graph;
2
3import java.util.*;
4
5/** Interface to specify a Graph ADT.
6 * A graph is a set of vertices and a set of edges.
7 * Vertices are represented by integers from 0 to n − 1.
8 * Edges are ordered pairs of vertices.
9 * Each implementation of the Graph interface should
10 * provide a constructor that specifies the number of
11 * vertices and whether the graph is directed.
12 */
13public interface Graph {
14
15 // Accessor Methods
16 /** Return the number of vertices.
17 @return The number of vertices
18 */
19 int getNumV();
20
21 /** Determine whether this is a directed graph.
22 @return true if this is a directed graph
23 */
24 boolean isDirected();
25
26 /** Insert a new edge into the graph.
27 @param edge The new edge
28 */
29 void insert(Edge edge);
30
31 /** Determine whether an edge exists.
32 @param source The source vertex
33 @param dest The destination vertex
34 @return true if there is an edge from source to dest
35 */
36 boolean isEdge(int source, int dest);
37
38 /** Get the edge between two vertices.
39 @param source The source vertex
40 @param dest The destination vertex
41 @return The edge between these two vertices or null if there is no edge
42 */
43 Edge getEdge(int source, int dest);
44
45 /** Return an iterator to the edges connected to a given vertex.
46 @param source The source vertex
47 @return An Iterator<Edge> to the vertices connected to source
48 */
49 Iterator<Edge> edgeIterator(int source);
50
51 /** Read source and destination vertices and weight (optional) for each edge from a file
52 @param scan The Scanner associated with the file
53 */
54 default void loadEdgesFromFile(Scanner scan) {
55 String line;
56 while (scan.hasNextLine()) {
57 line = scan.nextLine();
58 if (!line.isBlank()) {
59 String[] tokens = line.split("\\s+");
60 int source = Integer.parseInt(tokens[0]);
61 int dest = Integer.parseInt(tokens[1]);
62 double weight = 1.0;
63 if (tokens.length == 3) {
64 weight = Double.parseDouble(tokens[2]);
65 }
66 insert(new Edge(source, dest, weight));
67 }
68 }
69 }
70}
11.3.2. Edge Representation
The nodes will be represented by integers, but we need a class to represent the edge.
The class is simple, it contains three attributes:
A source node
A destination node
A weight, \(1\) by default.
1/**
2 * An Edge represents a relationship between two
3 * vertices.
4 */
5public class Edge {
6 // Data Fields
7 /** The source vertex */
8 private final int source;
9 /** The destination vertex */
10 private final int dest;
11 /** The weight */
12 private final double weight;
13
14 // Constructor
15 /** Construct an Edge with a source of from
16 * and a destination of to. Set the weight to 1.0.
17 * @param source - The source vertex
18 * @param dest - The destination vertex
19 */
20 public Edge(int source, int dest) {
21 }
22 /** Construct a weighted edge with a source
23 * of from and a destination of to. Set the
24 * weight to w.
25 * @param source - The source vertex
26 * @param dest - The destination vertex
27 * @param w - The weight
28 */
29 public Edge(int source, int dest, double w) {
30 }
31 // Methods
32 /** Get the source
33 * @return The value of source
34 */
35 public int getSource() {
36 }
37 /** Get the destination
38 * @return The value of dest
39 */
40 public int getDest() {
41 }
42 /** Get the weight
43 * @return the value of weight
44 */
45 public double getWeight() {
46 }
47 /** Return a String representation of the edge
48 * @return A String representation of the edge
49 */
50 @Override
51 public String toString() {
52 }
53 /** Return true if two edges are equal. Edges
54 * are equal if the source and destination
55 * are equal. Weight is not considered.
56 * @param obj The object to compare to
57 * @return true if the edges have the same source
58 * and destination
59 */
60 @Override
61 public boolean equals(Object obj) {
62 if (obj instanceof Edge) {
63 Edge edge = (Edge) obj;
64 return (source == edge.source && dest == edge.dest);
65 } else {
66 return false;
67 }
68 }
69 /** Return a hash code for an edge. The hash
70 * code is the source shifted left 16 bits
71 * exclusive or with the dest
72 * @return a hash code for an edge
73 */
74 @Override
75 public int hashCode() {
76 return (source << 16) ^ dest;
77 }
11.3.3. Adjacency List Representation
We will create a class to represent a graph using a linked list.
This class ListGraph
will implement the interface Graph
and contains three attributes.
1import java.util.*;
2
3/** A ListGraph implements the Graph interface using an
4 array of lists to represent the edges.
5 */
6public class ListGraph implements Graph {
7
8 // Data Fields
9 /** The number of vertices */
10 private final int numV;
11 /** An indicator of whether the graph is directed (true) or not (false)
12 */
13 private final boolean directed;
14 /** An array of Lists to contain the edges that
15 originate with each vertex.
16 */
17 private LinkedList<Edge>[] edges;
18}
The constructor only takes the number of nodes and if the graph is directed as parameters.
1 /** Construct a graph with the specified number of vertices and directionality.
2 @param numV The number of vertices
3 @param directed The directionality flag
4 */
5 public ListGraph(int numV, boolean directed) {
6 this.numV = numV;
7 this.directed = directed;
8 edges = new LinkedList[numV];
9 for (int i = 0; i < numV; i++) {
10 edges[i] = new LinkedList<Edge>();
11 }
12 }
Activity
Implement the following methods of the class.
1 /**
2 * Insert a new edge into the graph.
3 *
4 * @param edge The new edge
5 */
6 @Override
7 public void insert(Edge edge) {
8 }
9 /**
10 * Get the edge between two vertices.
11 *
12 * @param source The source vertex
13 * @param dest The destination vertex
14 * @return The edge between these two vertices
15 * or null if there is no edge
16 */
17 @Override
18 public Edge getEdge(int source, int dest) {
19 }
11.4. More Definitions
Graphs are used in a lot of algorithms.
To use them in these algorithms, we require some last definitions.
Definition: Path
In a graph, a path is a sequence of vertices \(v_1, v_2 \dots, v_N\) such that \((v_i, v_{i+1})\in E\) for \(1 \leq i < N\).
The length of the path is the number of edges on the path (\(N-1\)).
Definition: Cycle
In a cycle in a directed graph is a path of length at least 1 such that \(v_1 = v_N\).
In undirected graph the edges need to be distinct.
If a directed graph does not have a cycle, it is called a acyclic graph.
Activity
Consider the graph given in the first example.
Give an example of a path.
Give a example of a cycle.
11.4.1. Connected Graphs
Definition: Connected graph
An undirected graph is called a connected graph if there is a path from every vertex \(v_i\) to every other vertex \(v_k \in V\).
Definition: Connected component
If a graph is not connected, it is considered unconnected.
A connected component is a subset \(G_i = (V_i, E_i)\), where \(V_i \subset V\) and \(E_i \subset E\) with every pair of vertices \((v_i, v_j), \forall v_i,v_j \in V_i\) are connected by a path.
Example
11.4.2. Graph and Tree
A graph is the most general data structure presented in this course.
It can represent any relationship among the data elements (vertices).
A tree is actually a special case of a graph.
Definition: Tree
A connected graph \(G=(V,E)\) without cycles is a tree.