Unit 12

Graphs

Dr. Saleh Alhazbi

CMPS303‐ Data Structures
 Graphs
A Graph is a collection of vertices (or nodes) and the connections among them (edges).

Each vertex (node) contains an element

Each edge connects two vertices (nodes)

together (or possibly the same node
to itself), may contain an edge attribute.

It is a non-linear data structure.

Generally, no restriction is imposed on the number of nodes in the graph or on the connections one node
can have to other nodes.
 Graph Applications
Modeling routs between cities. Modeling flights between airports.

Modeling computer networks

Relationships on social networks.
 Graph terminology
A graph is a pair (V, E), where
V is a set of nodes, called vertices
E is a collection of pairs of vertices, called edges
Vertices and edges store elements

V = {A,B,C,D}
E = {(A,B),(A,C),(C,B),(C,D),(B,D)}

The size of a graph is the number of nodes in it

If two nodes are connected by an edge, they are neighbors (and the nodes are adjacent to each other)
example A,B or A,C

The degree of a node is the number of edges it has, example degree of node A is 2
 Graph types

Directed graph Undirected Graph

The edges have directions The edges do not have directions

 Graph terminology
For directed graphs:
If a directed edge goes from node S to node D, we call S the source and D the destination of the edge.

The edge is an out-edge of S and an in-edge of D.

Flight A234 is an out-edge of SFO, and in-edge of ORD

The in-degree of a node is the number of in-edges it has.

For example the in-degree of ORD is 2.

The out-degree of a node is the number of out-edges it has.

For example, the out-degree of LAX is 2.
 Graph terminology
A path is a list of edges such that each node (but the last) is the
predecessor of the next node in the list

We may have more than one path between two

nodes.

Example: (London, Bristol, Birmingham,

London, Dover) is a path

A cycle is a path whose first and last nodes

are the same

Example: (London , Bristol, Birmingham, London) is a cycle

A cyclic graph contains at least one cycle

An acyclic graph does not contain any cycles

 Weighted Graph
Weighted graph is a graph where each edge is associated with a numeric label represents the weight of
that edge.

This weight might represent the length of the route, the cost, the energy required to move between the two
locations, etc.

The weighted graph also can be directed or undirected.

 Graph Implementation
1) Adjacency Matrix (Undirected Graph)
Assume vertices are numbered 1, 2, …|V|
The representation consists of 2D array (matrix) A |V|x |V|:

aij = 1 if (i, j)  E (edge between vertex i and vertex j)

0 otherwise

For undirected graphs, matrix A is symmetric about the main diagonal

 Graph Implementation
Adjacency Matrix (directed Graph)
Assume vertices are numbered 1, 2, …|V|
The representation consists of 2D array (matrix) A |V|x |V|:

aij = 1 if (i, j)  E (edge between vertex i and vertex j)

0 otherwise

For direct graphs, matrix A might not be symmetric.

public class Vertex
{
public char label;
public boolean wasVisited;
public Vertex(char lab)
{
label = lab;
wasVisited = false;
}
}
public class Graph
{
private final int MAX_VERTS = 20;
private Vertex vertexList[];
private int adjMat[][];
private int nVerts;

public Graph()
{
vertexList = new Vertex[MAX_VERTS];
adjMat = new int[MAX_VERTS][MAX_VERTS];
nVerts = 0;
for(int j=0; j<MAX_VERTS; j++)
for(int k=0; k<MAX_VERTS; k++)
adjMat[j][k] = 0;
}
 public void addVertex(char lab)
{
vertexList[nVerts++] = new Vertex(lab);
}
// ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
public void addEdge(int start, int end)
{
adjMat[start][end] = 1;
adjMat[end][start] = 1;
}
// ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
public void displayVertex(int v)
{
System.out.print(vertexList[v].label);
}
// ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
}
 Graph Implementation
2) Adjacency List

An array of |V| lists, one for each vertex in V

Each list A[u] contains all the vertices v that are adjacent to u (i.e., there is an edge from u to v)

Can be used for both directed and undirected graphs

 Searching or traversing a graph
You can start with any node

Depth-first search (DFS) Breadth-first search (BFS).

Order of visiting the

Order of visiting the nodes in DFS nodes in BFS
ABFHCDGIE ABCDEFGHI

Implemented with a stack Implemented with a queue.

Starting by vertex D Starting by vertex A

DFS: DBACE BFS: DBCEA DFS: ABEDFC BFS: ACDBFE

DECBA DCBEA ACFDEB ACDBEF
DCEBA DECBA ADFCEB ABDCFE
Depth-first search (DFS)
public int getAdjUnvisitedVertex(int v)
{
for(int j=0; j<nVerts; j++)
if(adjMat[v][j]==1 && vertexList[j].wasVisited==false)
return j;
return ‐1; // no such vertices
} // end getAdjUnvisi
public void dfs()
{
Stack<Integer> theStack=new Stack<>();
vertexList[0].wasVisited = true;
displayVertex(0);
theStack.push(0);
while( !theStack.isEmpty() ),
{
int v = getAdjUnvisitedVertex( theStack.top() );
if(v == ‐1)
theStack.pop();
else // if it exists,
{
vertexList[v].wasVisited = true; // mark it
displayVertex(v); // display it
theStack.push(v); // push it
}
}
}
Breadth-first search (BFS)
public void bfs()
{
Queue<Integer> theQueue=new Queue<>();
vertexList[0].wasVisited = true;
displayVertex(0);
theQueue.enqueue(0);
int v2;
while( !theQueue.isEmpty() )
{
int v1 = theQueue.dequeue();
while( (v2=getAdjUnvisitedVertex(v1)) != ‐1 )
{
vertexList[v2].wasVisited = true;
displayVertex(v2);
theQueue.enqueue(v2);
}
}
}
 The Shortest-Path Problem
Perhaps the most commonly encountered problem associated
with weighted graphs is that of finding the shortest path
between two given vertices.

Dijkstra’s Algorithm
The solution for the shortest-path problem is called Dijkstra’s
algorithm, after Edsger Dijkstra, who first described it in 1959.
The algorithm used with weighted graph.

It can be used with directed as well as undirected graph.

It finds the shortest path between a specific vertex and all other vertices.
 Dijkstra’s Algorithm
If e=(u,v), the di(u,v) denotes the edge length,
dt(s,u) denotes the shortest distance from s to u
1.S = {s}
2.Set
d(s,s) = 0,
dt(s,v) = di(s,v) for all v adjacent to s
dt(s,v) = infinity for all remaining vertices
3.while V–S is not empty do
4. Select a vertex u in V–S of minimum distance
5. Add u to S
6. For each v adjacent to u do:
7. If dt(s,v) > dt(s,u)+di(u,v) then update dt(s,v)
 Dijkstra’s Algorithm Operation
Adjacent Nodes

2
1 5
2
3
3
S={1}
1
2 3
1 6
V = { 1, 2, 3, 4, 5, 6, 7}
3 3 2
3
V – S = { 2, 3, 4, 5, 6, 7 }
4 7
1

1 2 3 4 5 6 7
0 3 2 3 ∞ ∞ ∞
 Dijkstra’s Algorithm Operation
2
1 5
2
3
3
S = { 1, 3 }
1
2 3
1 6
V – S = { 2, 4, 5, 6, 7 }
3 3 2
3

4 7
1

1 2 3 4 5 6 7
0 3 2 3 ∞5 ∞3 ∞
 Dijkstra’s Algorithm Operation
2
1 5
2
3
3
S = { 1, 3, 4 }
1
2 3
1 6
V – S = { 2, 5, 6, 7 }
3 3 2
3

4 7
1

1 2 3 4 5 6 7
0 3 2 3 5 3 ∞4
 Dijkstra’s Algorithm Operation
2
1 5
2
3
3
S = { 1, 3, 4, 2 }
1
2 3
1 6
V – S = { 5, 6, 7 }
3 3 2
3

4 7
1

1 2 3 4 5 6 7
0 3 2 3 54 3 4
 Dijkstra’s Algorithm Operation
2
1 5
2
3
3
S = { 1, 3, 4, 2, 6 }
1
2 3
1 6
V – S = { 5, 7 }
3 3 2
3

4 7
1

1 2 3 4 5 6 7
0 3 2 3 4 3 4
 Dijkstra’s Algorithm Operation
2
1 5
2
3
3
S = { 1, 3, 4, 2, 6, 7 }
1
2 3
1 6
V–S={5}
3 3 2
3

4 7
1

1 2 3 4 5 6 7
0 3 2 3 4 3 4
 Dijkstra’s Algorithm Operation
2
1 5
2
3
3
S = { 1, 3, 4, 2, 6, 7, 5 }
1
2 3
1 6
V–S={ }
3 3 2
3

4 7
1

1 2 3 4 5 6 7
0 3 2 3 4 3 4