Data Structures - Graph Data structure
- 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.
- 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.
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.
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.
It is a path consisting of, at least 3 vertices that starts and ends with the same vertex.
It is a special case of cycle, in which a single arc begins and ends with same vertex.
If there is a path between two vertices, then we say that two vertices are connected
Based on Directed or Undirected
Directed Graph (or) Digraph
It is graph in which each edge has a direction to its successor.
It is a graph in which there is no direction on the edges. The flow between two vertices can go in either direction.
Based on Weighted or Unweighted
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.
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.
The graph is a disjoint, if it is not connected.
If there is an edge between every pair of vertices, then we say that graph is said to be complete 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 is a directed graph without any undirected cycles
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.
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.
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).
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|).