Search

# Placement Practice | Graphs - I

In this blog, we will deep dive into Graphs. So bear with us till the last 😊

Introduction to Graphs

A graph is a data structure (V, E) that is a collection of nodes that have data and are connected to other nodes:

• A finite set of vertices V also called nodes.

• A collection of edges E represented as ordered pairs of vertices (u,v)

Vertices and Edges of Graph
```V = {0, 1, 2, 3}
E = {(0,1), (0, 2), (1,2), (0,3)}
G = {V, E}```

Let's try to understand this through an example. On Facebook, everything is a node. That includes User, Photo, Album, Event, Group, Page, Comment, Story, Video, Link, Note...anything that has data is a node.

### Graphs Terminology:

• Adjacency: A vertex is said to be adjacent to another vertex if there is an edge connecting them. Vertices 2 and 3 are not adjacent because there is no edge between them.

• Path: A sequence of edges that allows you to go from vertex A to vertex B is called a path. 0-1, 1-2, and 0-2 are paths from vertex 0 to vertex 2.

• Directed Graph: A graph in which an edge (u,v) doesn't necessarily mean that there is an edge (v, u) as well. The edges in such a graph are represented by arrows to show the direction of the edge.

• Undirected Graphs: Undirected graphs are such graphs in which the edges are bi-directional or in other words directionless. That is, if there is an edge between vertices u and v then it means we can use the edge to go from both u to v and v to u.

### Graph Representation:

Graphs are commonly represented in two ways:

Let us look at each one of the above two methods in details:

• It is a 2D array of V x V vertices. Each row and column represent a vertex.

• If the value of any element a [ i ][ j ] is 1, it represents that there is an edge connecting vertex i and vertex j.

• The adjacency matrix for the undirected graph is always symmetric.

• Adjacency Matrix is also used to represent weighted graphs.

• If adj [ i ][ j ] = w, then there is an edge from vertex i to vertex j with weight w.

• Since it is an undirected graph, for edge (0,2), we also need to mark edge (2,0); making the adjacency matrix symmetric about the diagonal.

Pros: Representation is easier to implement and follow. Removing an edge takes O(1) time.

Cons: Consumes more space O(V^2). Even if the graph is sparse, it consumes the same space. Adding a vertex is O(V^2) time.

• It represents a graph as an array of linked lists.

• The index of the array represents a vertex and each element in its linked list represents the other vertices that form an edge with the vertex.

• An adjacency list is efficient in terms of storage because we only need to store the values for the edges.

Pros: Saves space O(|V|+|E|). In the worst case, there can be C(V, 2) number of edges in a graph thus consuming O(V^2) space. Adding a vertex is easier.

Cons: Queries like whether there is an edge from vertex u to vertex v are not efficient and can be done O(V).

Happy Coding!

Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.

See All