1 of 59

Graphs�

Mr. Abhijit T. Somnathe

2 of 59

What is Graph?

A Graph is a non-linear data structure consisting of nodes and edges.
The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph.
Graphs are used to solve many real-life problems.

3 of 59

What is Graph?

In the above Graph, the set of vertices V = {0,1,2,3,4} and the set of edges E = {01, 12, 23, 34, 04, 14, 13}.

4 of 59

What is Graph?

Graphs are used to represent networks.
The networks may include paths in a city or telephone network or circuit network.
Graphs are also used in social networks like linkedIn, Facebook, etc.
For example, in Facebook, each person is represented with a vertex(or node). Each node is a structure and contains information like person id, name, gender, locale etc.

5 of 59

Directed and Undirected Graph

A graph can be directed or undirected.
In an undirected graph, edges do not have any direction associated with them.
If an edge is drawn between nodes A and B, then the nodes can be traversed from A to B as well as from B to A.

6 of 59

Directed and Undirected Graph

Figure below shows an undirected graph because it does not give any information about the direction of the edges.

7 of 59

Directed and Undirected Graph

Figure below shows a directed graph.

8 of 59

Directed and Undirected Graph

In a directed graph, edges form an ordered pair.
If there is an edge from A to B, then there is a path from A to B but not from B to A.
The edge (A, B) is said to initiate from node A (also known as initial node) and terminate at node B (terminal node).

9 of 59

Graph Terminology

Vertex − Each node of the graph is represented as a vertex.
Edge − Edge represents a path between two vertices or a line between two vertices.
Adjacency − Two node or vertices are adjacent if they are connected to each other through an edge.

10 of 59

Graph Terminology

Path − Path represents a sequence of edges between the two vertices. In the following example, ABCD represents a path from A-D.

11 of 59

Graph Terminology

Degree of a node - Degree of a node u, deg(u), is the total number of edges containing the node u. If deg(u) = 0, it means that u does not belong to any edge and such a node is known as an isolated node.

Here, Degree of A = C = E = 2 while degree of B = D = 3.

12 of 59

Graph Terminology

Outdegree – The outdegree of a vertex A in a directed graph, is the number of edges starting from the vertex A.
Indegree – The indegree of a vertex A in a directed graph, is the number of edges termination at the vertex A.

In the graph, Vertex C has Indegree = 1 and Outdegree = 1. Vertex B has Indegree = 2 and Outdegree = 1.

13 of 59

Graph Terminology

Source − A vertex V is known as Source if its outdegree is 1 or more than 1 but its Indegree is 0.
Sink − A vertex V is known as Sink if its Indegree is 1 or more than 1 but its outdegree is 0.

In figure, Vertex 0 is Source while Vertex 2 is Sink.

14 of 59

Graph Terminology

Strongly Connected − Graph is said to be strongly connected if there is a path from each vertex to every other vertex.

15 of 59

Graph Terminology

Weakly Connected − In a weakly connected graph the nodes cannot be visited by a single path.

16 of 59

Graph Terminology

Weighted Graph − Graph is said to be weighted if edges in it are assigned weights.

17 of 59

Graph Terminology

Multi Graph - Any graph which contain some parallel edges but doesn’t contain any self-loop is called multi graph. For example - A Road Map.

18 of 59

Graph Representation

Graph can be represented using various ways. The two standard approaches for representing graphs are,
Sequential representation by using adjacency matrix.
Adjacency List.

19 of 59

Adjacency Matrix

Suppose, G = {V_g, E_g} is a directed graph having n nodes.
Suppose, vertices are ordered by using v₁, v₂, v₃, v₄,…., v_n. Then adjacency matrix A for the graph G will be a square matrix of order n such that,
a_ij = 1, if an edges lies between the vertices v_i and v_j.
a_ij = 0, if there is no edges between the vertices v_i and v_j.

20 of 59

Adjacency Matrix

For example, consider the following undirected graph representation.

21 of 59

Adjacency Matrix

Consider the following directed graph representation.

22 of 59

Incidence Matrix

In this representation, the graph is represented using a matrix of size total number of vertices by a total number of edges.

23 of 59

Incidence Matrix

In above graph having 5 vertices and 8 edges is represented using a matrix of size 5X8.
In this matrix, rows represent vertices and columns represents 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.

24 of 59

Incidence Matrix

25 of 59

Linked Representation

The adjacency matrix representation has a number of drawbacks. In this representation, it is difficult to store additional information about the vertices and edges in the graph.
One major problem with this representation is its static nature. Before storing any graph, it is necessary to find the number of vertices in it.

26 of 59

Linked Representation

It becomes very difficult to insert and delete the vertices from the graph when it is represented using the adjacency matrix, as it requires change in the dimensions of the matrix.
In the linked representation, an adjacency list is used to store the Graph into the computer's memory.

27 of 59

Linked Representation

An adjacency list is maintained for each node present in the graph which stores the node value and a pointer to the next adjacent node to the respective node.
If all the adjacent nodes are traversed then store the NULL in the pointer field of last node of the list.
Consider the undirected graph shown in the following figure and check the adjacency list representation.

28 of 59

Linked Representation

29 of 59

Linked Representation

Consider the directed graph shown in the following figure and check the adjacency list representation of the graph.

30 of 59

Linked Representation

In a directed graph, the sum of lengths of all the adjacency lists is equal to the number of edges present in the graph.
In the case of weighted directed graph, each node contains an extra field that is called the weight of the node.
The adjacency list representation of a directed graph is shown in the following figure.

31 of 59

Linked Representation

32 of 59

Graph Traversal

The most fundamental graph problem is to traverse every edge and vertex in a graph on a systematic way.
Graph traversal is a process of visiting (checking and/or updating) each vertex in a graph. Such traversals are classified by the order in which the vertices are visited.
There are mainly 2 types.
Depth First Search (DFS)
Breadth First Search (BFS)

33 of 59

Depth First Search (DFS)

Depth First Search (DFS) algorithm traverses a graph in a depthward motion and uses a stack to remember to get the next vertex to start a search, when a dead end occurs in any iteration.

34 of 59

Depth First Search (DFS)

35 of 59

Depth First Search (DFS)

As in the example given above, DFS algorithm traverses from S to A to D to G to E to B first, then to F and lastly to C. It employs the following rules.
Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Push it in a stack.
Rule 2 − If no adjacent vertex is found, pop up a vertex from the stack. (It will pop up all the vertices from the stack, which do not have adjacent vertices.)
Rule 3 − Repeat Rule 1 and Rule 2 until the stack is empty.

36 of 59

Depth First Search (DFS)

37 of 59

Depth First Search (DFS)

38 of 59

Depth First Search (DFS)

39 of 59

Depth First Search (DFS)

40 of 59

Depth First Search (DFS)

41 of 59

Depth First Search (DFS)

42 of 59

Depth First Search (DFS)

43 of 59

Depth First Search (DFS)

As C does not have any unvisited adjacent node so we keep popping the stack until we find a node that has an unvisited adjacent node.
In this case, there's none and we keep popping until the stack is empty.

44 of 59

Breadth First Search (BFS)

Breadth First Search (BFS) algorithm traverses a graph in a breadthward motion and uses a queue to remember to get the next vertex to start a search, when a dead end occurs in any iteration.

45 of 59

Breadth First Search (BFS)

46 of 59

Breadth First Search (BFS)

As in the example given above, BFS algorithm traverses from S-A, S-B, S-C then A-D, B-E and C-F then D-G. It employs the following rules.
Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Insert it in a queue.
Rule 2 − If no adjacent vertex is found, remove the first vertex from the queue.
Rule 3 − Repeat Rule 1 and Rule 2 until the queue is empty.

47 of 59

Breadth First Search (BFS)

48 of 59

Breadth First Search (BFS)

49 of 59

Breadth First Search (BFS)

50 of 59

Breadth First Search (BFS)

51 of 59

Breadth First Search (BFS)

52 of 59

Breadth First Search (BFS)

53 of 59

Breadth First Search (BFS)

54 of 59

Breadth First Search (BFS)

At this stage, we are left with no unmarked (unvisited) nodes.
But as per the algorithm we keep on dequeuing in order to get all unvisited nodes.
When the queue gets emptied, the program is over.

55 of 59

Topological Sorting

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge u v, vertex u comes before v in the ordering.
Topological Sorting for a graph is not possible if the graph is not a DAG.

56 of 59

Topological Sorting

For example, a topological sorting of the following graph is “5 4 2 3 1 0”.

57 of 59

Topological Sorting

There can be more than one topological sorting for a graph.
For example, another topological sorting of the following graph is “4 5 2 3 1 0”.
The first vertex in topological sorting is always a vertex with in-degree as 0 (a vertex with no incoming edges).

58 of 59

Topological Sorting vs Depth First Traversal (DFS)

In DFS, we print a vertex and then recursively call DFS for its adjacent vertices.
In topological sorting, we need to print a vertex before its adjacent vertices.
For example, in the given graph, the vertex ‘5’ should be printed before vertex ‘0’, but unlike DFS, the vertex ‘4’ should also be printed before vertex ‘0’.
So Topological sorting is different from DFS.
For example, a DFS of the shown graph is “5 2 3 1 0 4 / 5 2 3 1 4 0”, but it is not a topological sorting.

1 of 59

2 of 59

3 of 59

4 of 59

5 of 59

6 of 59

7 of 59

8 of 59

9 of 59

10 of 59

11 of 59

12 of 59

13 of 59

14 of 59

15 of 59

16 of 59

17 of 59

18 of 59

19 of 59

20 of 59

21 of 59

22 of 59

23 of 59

24 of 59

25 of 59

26 of 59

27 of 59

28 of 59

29 of 59

30 of 59

31 of 59

32 of 59

33 of 59

34 of 59

35 of 59

36 of 59

37 of 59

38 of 59

39 of 59

40 of 59

41 of 59

42 of 59

43 of 59

44 of 59

45 of 59

46 of 59

47 of 59

48 of 59

49 of 59

50 of 59

51 of 59

52 of 59

53 of 59

54 of 59

55 of 59

56 of 59

57 of 59

58 of 59

59 of 59