Data Structures - Graph Data structure

<<Previous

Next >>





Graph is:

  • a collection of nodes called vertices and
  • a collection of line segments connecting pairs of vertices. In short, Line segments are called lines or edges.

Graph is represented by two sets:

  • a set of vertices V
  • a set of edges E which link the vertices
G = (V, E)

Each edge is a pair of vertices (v, w), where v,w ∈ V.

Edges are also referred to as a arcs.

Graph Applications

  • Graphs are used to represent real life applications.
  • Graph can be used to solve complex problems. For example: for designing and routing airline, to route messages over a computer network from one node to another and so on.

Graph - How it differs from Tree

  • It is a non-linear data structure. It is differ from tree data structure.
  • In graph, each node may have multiple predecessors as well as multiple successors where as in tree, each node has a multiple successors but just one predecessor.

Graph Properties

Adjacent Vertices(or) Neighbors

If there is an edge between two vertices, then these two vertices are said to be adjacent vetices. For example, from the above graph (Figure 2) A and B are adjacent vertices, but A and D are not.

Path

It is the sequence of vertices in which each vertex is adjacent to next one. For example, let us take the above graph (Figure 2) A, B, C, E is one path and A, B, D, E is another path.

Cycle

It is a path consisting of, at least 3 vertices that starts and ends with the same vertex.

Loop

It is a special case of cycle, in which a single arc begins and ends with same vertex.

Connected

If there is a path between two vertices, then we say that two vertices are connected


Graph Variants

Based on Directed or Undirected

Directed Graph (or) Digraph

It is graph in which each edge has a direction to its successor.

Fig 1. Directed Graph

Undirected Graph

It is a graph in which there is no direction on the edges. The flow between two vertices can go in either direction.

Figure 2. Undirected Graph

Based on Weighted or Unweighted

Weighted Graph

If the graph has a some cost or weight on the edge, then we say that graph is said to be a weighted graph. Weight can be applied in both Directed and Undirected graph.


Figure 3. Weighted Directed Graph

Unweighted Graph

If there is no cost or weight on the edge, then we say that graph is an Unweighted Graph. For example, Figure 2 is the Unweighted Undirected graph


Based on How Connected the Graph is

Strongly Connected Graph

If there is a path from each vertex to every other vertex in the directed graph, then only we say that directed graph is said to be Strongly connected graph.

Weakly Connected Graph

If there are at least two vertices that are not connected, then we say that directed graph is said to be weakly connected graph.

Disjoint Graph

The graph is a disjoint, if it is not connected.

Complete Graph

If there is an edge between every pair of vertices, then we say that graph is said to be complete graph.


Acyclic Graph

A graph is acyclic if it has no cycles.

Directed Acyclic Graph

A directed acyclic graph is directed graph without any directed cycles. Referred by its short name DAG

PolyTree

PolyTree is a directed graph without any undirected cycles

Forest

Forest is a undirected graph without any cycles



Quantifying the Graph

Degree of a Vertex

Degree of vertex is the number of lines associated with it. For example, let us consider the above graph(Figure 1). Degree of a vertex B is 4.

Indegree of a Vertex

It is the number of arcs entering the vertex. For example, let us consider the above graph(Figure 1). Indegree of vertex B is 1.

Outdegree of Vertex

It is the number of arcs leaving the vertex. For example, let us consider the above graph(Figure 1). Outdegree of vertex B is 3.


Graph Representation

There are different ways to represent Graph

Adjacency Matrix Representation

One simple way is to use adjacency matrix representation which uses a two-dimensional array. This means that vertices are adjacent to one another.

  • If there is an edge between two vertices, then we set A[vi][vj]=1.
  • Otherwise we set the entry in the array to 0.

For adjacency matrix, put 1 in the table if Vi and Vj have edge in the graph else put 0.

Figure 4. Matrix Representation of Unweighted Graph


Suppose, if the edge is associated with weight, then we can set A[vi][vj] equal to the weight. The memory space required for this adjacency matrix is O(|V|2).


Figure 5. Matrix Representation of Weighted Directed Graph


For adjacency matrix, put the weightage in the table if Vi and Vj have edge with weightage else put some constant C. Here we take the constant as .The self ending weightage is 0. If the graph is dense, an adjacency matrix is suitable representation.

Adjacency List Representation

Suppose, if the graph is sparse, then an adjacency list is the better solution for graph representation. In adjacency list representation, for each vertex, we maintain a list of all adjacent vertices. If the edges have weights, then this extra information is also stored in the list cells. The memory space required for adjacency list is O(|E|+|V|).

Fig 6. Adjacency List Representation of Directed Graph



<< Previous

Next >>




What is the difference between Java and Javascript?

Krivalar.com © 2017