1
UNIT 5 - GRAPHS
The Graph ADT Introduction
Definition
Graph representation
Elementary graph operations BFS, DFS
Introduction to Graphs
Graph is a non linear data structure; A map is a well-known example of a graph. In a map various connections are
made between the cities. The cities are connected via roads, railway lines and aerial network. We can assume that
the graph is the interconnection of cities by roads. Euler used graph theory to solve Seven Bridges of Königsberg
problem. Is there a possible way to traverse every bridge exactly once – Euler Tour
Figure: Section of the river Pregal in Koenigsberg and Euler's graph.
Defining the degree of a vertex to be the number of edges incident to it, Euler showed that there is a walk starting
at any vertex, going through each edge exactly once and terminating at the start vertex iff the degree of each,
vertex is even. A walk which does this is called Eulerian. There is no Eulerian walk for the Koenigsberg bridge
problem as all four vertices are of odd degree.
A graph contains a set of points known as nodes (or vertices) and set of links known as edges (or Arcs) which
connects the vertices.
A graph is defined as Graph is a collection of vertices and arcs which connects vertices in the graph. A graph G is
represented as G = ( V , E ), where V is set of vertices and E is set of edges.
Example: graph G can be defined as G = ( V , E ) Where V = {A,B,C,D,E} and
E = {(A,B),(A,C)(A,D),(B,D),(C,D),(B,E),(E,D)}. This is a graph with 5 vertices and 6 edges.
Graph Terminology
1.Vertex : An individual data element of a graph is called as Vertex. Vertex is also known as node. In above
example graph, A, B, C, D & E are known as vertices.
2.Edge : An edge is a connecting link between two vertices. Edge is also known as Arc. An edge is represented as
(starting Vertex, ending Vertex).
In above graph, the link between vertices A and B is represented as (A,B).
Edges are three types:
1.Undirected Edge - An undirected edge is a bidirectional edge. If there is an undirected edge between vertices A
and B then edge (A , B) is equal to edge (B , A).
2.Directed Edge - A directed edge is a unidirectional edge. If there is a directed edge between vertices A and B
then edge (A , B) is not equal to edge (B , A).