CSC508 Data Structures
Topic 13 : Graph 1
Compiled & edited by: Zahid Zainal
Recap
Hashing
Hash Method
Collision Resolution
Load Factor
Compiled & edited by: Zahid Zainal
Topic Structure
Kőnigsberg Bridge Problem
Graph Definition
Graph Representations
Compiled & edited by: Zahid Zainal
Learning Outcomes
At the end of this lesson, students should be able to:
Explain the concept of graph data structure
Describe graph representations
Describe graph traversals
Compiled & edited by: Zahid Zainal
Kőnigsberg Bridge Problem
River Pregel (Pregolya) flows around
the island Kneiphof
Divides into two
River has four land areas (A, B,C, D)
Bridges are labeled a, b, c, d, e, f, g
Problem : Starting at one land area,
is it possible to walk across all the
bridges exactly once and return to
the starting land area?
In 1736, Euler represented The birth of graph
theory!!!
Königsberg bridge problem as graph
Compiled & edited by: Zahid Zainal
What is Graph?
A data structure that consists of a set of vertices (nodes)
and a set of edges (links, or arcs) that relate the nodes to
each other
Edges describe relationships among the objects
(represented by vertices)
A useful structure to represent non-linear relationships
between objects/entities, like connectivity, dependency,
interactivity, etc.
used in the analysis of electrical circuits and network
communications, finding shortest route between two places, and
in applications related to project planning, linguistics, genetics,
social sciences, and many more
Compiled & edited by: Zahid Zainal
Compiled & edited by: Zahid Zainal
Graph Definitions & Notations
A graph G is a pair, G = (V, E),
where V is a finite nonempty set, called the set of vertices of G,
and E V x V
E are the pair of elements of V. E is called the set of edge
Let V(G) denote the set of vertices, and E(G) denote the
set of edges of a graph G. If the elements of E(G) are
ordered pairs, g is called a directed graph or digraph;
Otherwise, g is called an undirected graph
In an undirected graph, the pairs (u, v) and (v, u)
represent the same edge
Compiled & edited by: Zahid Zainal
Samples of Undirected Graphs
Compiled & edited by: Zahid Zainal
Samples of Directed Graphs
Compiled & edited by: Zahid Zainal
Graph Definitions & Notations (cont.)
Compiled & edited by: Zahid Zainal
Graph Representation
Graph can be represented in two ways:
Adjacency matrix
Adjacency list
Compiled & edited by: Zahid Zainal
Adjacency Matrix
Let G be a graph with n vertices, where n > 0
Let V(G) = {v1 , v2 , ..., vn }
The adjacency matrix AG is a two-dimensional n × n matrix
such that the (i, j)th entry of AG is 1 if there is an edge
from vi to vj; otherwise, the (i, j)th entry is zero
Compiled & edited by: Zahid Zainal
Adjacency Matrix - Samples
Compiled & edited by: Zahid Zainal
Adjacency List
In adjacency list representation, corresponding to each
vertex, v, is a linked list such that each node of the linked
list contains the vertex u, such that (v, u) E(G)
Array, A, of size n, such that A[i] is a reference variable
pointing to address of first node of linked list containing
the vertices to which vi is adjacent
Each node has two components, (vertex and link)
Component vertex contains index of vertex adjacent to
vertex i
Compiled & edited by: Zahid Zainal
Adjacency List - samples
Compiled & edited by: Zahid Zainal
References
Carrano, F. & Savitch, W. 2005. Data Structures and
Abstractions with Java, 2nd ed. Prentice-Hall.
Malik D.S, & Nair P.S., Data Structures Using Java,
Thomson Course Technology, 2003.
Rada Mihalcea, CSCE 3110 Data Structures and Algorithm
Analysis notes, U of North Texas.
Compiled & edited by: Zahid Zainal