Graphs
Graph is a non-linear data structure. It contains a set of points
known as nodes (or vertices) and a set of links known as edges
(or Arcs). Here edges are used to connect the vertices. A graph is
defined as follows...
Graph is a collection of vertices and arcs in which vertices
are connected with arcs
OR
Graph is a collection of nodes and edges in which nodes
are connected with edges
Generally, a graph G is represented as G = (V, E), where V is set
of vertices and E is set of edges.
Example
The following is a graph with 5 vertices and 6 edges.
This 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)}.
Fig(a)
Graph Terminologies
We use the following terms in graph data structure...
Vertex
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.
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). For example, in above graph the link between vertices A
and B is represented as (A, B). In above example graph, there are
7 edges (i.e., (A, B), (A, C), (A, D), (B, D), (B, E), (C, D), (D, E)).
Edges are three types.
1. Undirected Edge - An undirected edge is a bidirectional
edge. If there is 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 directed edge between vertices A and B then edge
(A, B) is not equal to edge (B, A).
3. Weighted Edge - A weighted edge is an edge with value
(cost) on it.
Undirected Graph
A graph with only undirected edges is said to be undirected
graph.
Directed Graph
A graph with only directed edges is said to be directed graph.
Adjacent
If there is an edge between vertices A and B then both A and B
are said to be adjacent. In other words, vertices A and B are said
to be adjacent if there is an edge between them.
Outgoing Edge
A directed edge is said to be outgoing edge on its origin vertex.
Incoming Edge
A directed edge is said to be incoming edge on its destination
vertex.
Degree
Total number of edges connected to a vertex is said to be degree
of that vertex.
In-degree
Total number of incoming edges connected to a vertex is said to
be in-degree of that vertex.
Out-degree
Total number of outgoing edges connected to a vertex is said to
be out-degree of that vertex.
Successor
For an edge (U,V), the edge begins at U and terminates at V, V is
the successor of U.
Predecessor
For an edge (U,V), the edge begins at U and terminates at V, U is
the predecessor of V.
Relation
The term relation is used in connection with sets. A relation is a
set of ordered pair of elements.
For the graph shown in figure, relation ‘R’ can be defined as
R= {<0, 1>, <1, 2>, <2, 0>, <3, 2>}
Sink
A sink is a vertex which has no edge emanating from it, and all
other vertices have an edge towards the sink.
Articulation Point
A vertex in an undirected connected graph is an articulation point
(or cut vertex) if removing it (and edges through it) disconnects
the graph.
Parallel edges or multiple edges
If there are two undirected edges with same end vertices and two
directed edges with same origin and destination, such edges are
called parallel edges or multiple edges.
Self-loop
Edge (undirected or directed) is a self-loop if its two endpoints
coincide with each other.
Path
A path is a sequence of distinct vertices, each adjacent to the
next.
e.g. in fig(a), A-B-D is a path but A-B-C is not a path.
Graph Representations
Graph data structure is represented using following
representations...
1. Adjacency Matrix
2. Incidence Matrix
3. Adjacency List
Adjacency Matrix
In this representation, the graph is represented using a matrix of
size total number of vertices by a total number of vertices. That
means a graph with 4 vertices is represented using a matrix of
size 4X4. In this matrix, both rows and columns represent
vertices. This matrix is filled with either 1 or 0. Here, 1 represents
that there is an edge from row vertex to column vertex and 0
represents that there is no edge from row vertex to column
vertex.
For example, consider the following undirected graph
representation...
Directed graph representation
Incidence Matrix
In this representation, the graph is represented using a matrix of
size total number of vertices by a total number of edges. That
means graph with 4 vertices and 6 edges is represented using a
matrix of size 4X6. In this matrix, rows represent vertices and
columns represent edges. This matrix is filled with 0 or 1 or -1.
Here, 0 represents that the row edge is not connected to column
vertex, 1 represents that the row edge is connected as the
outgoing edge to column vertex and -1 represents that the row
edge is connected as the incoming edge to column vertex.
For example, consider the following directed graph
representation...
Adjacency List
In this representation, every vertex of a graph contains list of its
adjacent vertices.
For example, consider the following directed graph representation
implemented using linked list...
