Introduction to graphs

                                                             

What is a graph?

A graph is a pair of sets (V, E) where V is set of vertices and E is a set of edges connecting the vertices.

Terminologies of a Graph :

• Vertices - These are the nodes of a graph
• Edges - The edges connect the nodes
• Unweighted Graph - A graph in which no weight is associated with any of its edges
• Weighted Graph - A graph in which a weight is associated with the edges.
• Undirected Graph - The Graph in which edges don't have a direction associated with them.
• Directed Graph -  The Graph in which edges have a direction associated with them.
• Cyclic Graph - A cyclic graph is a graph having at least one loop or cycle. That means if we start from a node we can get back to the same node.
• Acyclic Graph - A graph that does not have any cycle or loop.

''A tree is a directed unweighted acyclic graph.''

            Why?

1. Because a node in a tree points to its children. We can go from parents to children but not from children to parents. Hence, directed.
2. Because an edge in a tree is all the same with no weight, hence unweighted.
3. Because we can't arrive at the start node again in any way while traversing. Hence, acyclic.

             

Types of Graph :

There are 6 types of graphs :

1. Unweighted Undirected Graph [no weight of edge, no direction of edges]
2. Unweighted Directed Graph [no weight of edge but has the direction of edges]
3. Positive Weighted Directed Graph [Positive weight for edges and has the direction of edges] 
4. Negative Weighted Directed Graph [Negative weight for edges and has the direction of edges]
5. Positive Weighted UnDirected Graph [Positive weight for edges, no direction of edges]
6. Negative Weighted Undirected Graph [Negative weight for edges, no direction of edges]

It will be more clear with this diagram :

              

How Graph is Represented?

There are commonly two ways to represent any graph :

1. Adjacency Matrix 

An Adjacency Matrix is a binary square matrix (can have only values 0 or 1 and total_rows = total_columns) used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. 

For the adjacent pair of vertices, eg - A-B in the below diagram, we mark the entry Adjacency_Matrix[A][B]  and Adjacency_Matrix[B][A] as 1. Similarly, we mark 1 for other adjacent pairs of vertices.

The adjacency matrix can also be modified for the weighted graph in which instead of storing 0 or 1 in $A_{i,j}$, the weight or cost of the edge will be stored.

In an undirected graph, if $A_{i,j}$ = 1, then $A_{j,i}$ = 1. In a directed graph, if $A_{i,j}$ = 1, then $A_{j,i}$ may or may not be 1.

Time Complexity for checking if two nodes are adjacent in adjacency matrix : O(1)

Space Complexity for adjacency matrix - O(V^2) where V is no. of vertices

Following is the adjacency matrix for unweighted and undirected graph :

        

2. Adjacency List

Adjacency List is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex (or node) in a graph.

For a weighted graph, the weight or cost of the edge is stored along with the vertex in the list. In an undirected graph, if vertex j is in list $A_i$ then vertex i will be in list $A_j$.

Time Complexity to check if two nodes are adjacent to each other  - O(E)

Space Complexity for the adjacency list is O(V+E) as only those edges are stored which are really there.

  

"So now we have two ways to represent a graph, but is there some condition when one way is preferable over other ?"

         Yes,

• If a graph is complete or near to complete (this means most of the cells in the adjacency matrix are marked as 1), then we should use Adjacency Matrix.
• But if the number of edges are few, then we should use Adjacency List