Graphs

Network that help define and visualize relationships between various components.

More formally -

A graph $G = (V, E)$ is a set of vertices $V$ and edges $E$ . where each edge $(u,v)$ is a connection between vertices. $u, v \in V$ .

Edge is usually represented as a pair of vertices.
Vertices are also referred to as nodes.
Mathematically, graphs are represented using Set notation.

$E = \{(0,1), (0,2), (0,3), (1,3), (2,3), (3,4)\}$

Some Graph Terminology

Neighbours: Directly connected nodes.
Degree of a node: Number of neighbours of the node.
Path: Sequence of vertices connected by edges.
Path Length: Number of edges in the path.
Cycle: Path that ends at the same vertex.
Connectivity
- Two vertices are connected if a path exists between them
- Graph is connected if all vertices are connected.
- Connected component is a subset of vertices that are connected in an otherwise disconnected graph.

Types of Graphs

Undirected Graphs

Graph where relation goes both ways i.e. bidirectional edges.

Edge $(u,v)$ implies $(v,u)$ .

Directed Graphs

Edges are unidirectional.

Directed graphs have their own subclasses on the basis of presence of a cycle in the graph.

Directed Acyclic Graphs (DAGs)

A special case of directed graphs which do not contain a cycle. Trees are a special kind of DAG.

These are quite frequently used since these can be used to represent sequence of steps or non-cyclic dependencies. Some examples of such real-world situations:

Program build dependencies
College class prerequisites
Event Scheduling
Assembly instructions

#Topological Sort can be used to determine the correct sequencing.

Weighted Graphs

When edges in the graph are assigned some weightage. The weight can be used to model quantities such as traffic on a route, distance, etc.

Representation

Graphs can be represented in the following forms in memory.

Adjacency Matrix

A_{ij} = 1 \;\;\; if \ edge(i,j) \\ \;\;\;\;\;\; 0 \;\;\; otherwise

	0	1	2	3	4
0	0	1	1	1	0
1	1	0	0	1	0
2	1	0	0	1	0
3	0	1	1	0	1
4	0	0	0	0	1

Edge Set

E = \{(0,1), (0,2), (0,3), (1,3), (2,3), (3,4)\}

Harder to extract information about vertices of the graph => Not that common.

Adjacency List

Easy access to neighbours of a node – useful in graph algorithms.
Most real world graphs are sparse. That is, large number of nodes with fewer number of edges. For example, in a social network, there could be billions of people (nodes), but each person (node) will only have thousands of edges at most.

Traversal

Depth-first Search (DFS)

Start at root node.
Explore each branch as far as possible (till its depth).
No more vertex left in that branch?
Come back to where you can find vertices and start again.

Start - explore - backtrack - repeat.

Preorder and Postorder DFS

Preorder: When the node is "visited" while traversing to the depth.
Postorder: When the node is "visited" once we have encountered the leaf node.

Applications of DFS

Cycle Detection
Finding connected components
Topological Sort
Maze generation

Implementation

Recursive

void dfs(GraphNode v){
	visit(v);
	for(GraphNode w: v.neighbours)
		dfs(G,w);
}

The only issue in the above algorithm is that we'll end up visiting nodes we have already visited. Thus, we need to mark the already visited nodes.

private HashMap<GraphNode, Boolean> marked;
void dfs(GraphNode v){
	visit(v);
	marked.put(v, true);
	for(GraphNode w: v.neighbours)
		if(marked.getOrDefault(w,false)==false)
			dfs(G,w);
}

Time complexity: $O(V+E)$ ;

$V$ = no. of vertices $E$ = no. of edges

Cleaner and more readable than iterative implementation.

For Trees#Binary Trees, since there are only two nodes:

void dfs(TreeNode root){
	visit(v);
	dfs(root.left);
	dfs(root.right);
}

Implementation for Postorder DFS

Just move the visit() call to the end.

private HashMap<GraphNode, Boolean> marked;
void dfs(GraphNode v){
	marked.put(v, true);
	for(GraphNode w: v.neighbours)
		if(marked.getOrDefault(w,false)==false)
			dfs(G,w);
	visit(v);
}

Iterative

private HashMap<GraphNode, Boolean> marked;
void dfs(GraphNode v){
	Stack<GraphNode> s = new Stack<>(v);
	while(s.size()>0){
		v = stack.pop()
		if(marked.getOrDefault(w,false)==false){
			visit(v);
			marked.put(v, true);
		
		for(GraphNode w: v.neighbours)
			if(marked.getOrDefault(w,false)==false)
				stack.push(w);
		}
	}
}

Time complexity: $O(V+E)$ ;

$V$ = no. of vertices $E$ = no. of edges

More generalizable and extensible than recursive. As in, it can be tweaked to incorporate other algorithms.
Using Iterative Implementation, you can explicitly specify the stack size. While recursive approach uses the OS' default stack size, which is still typically small - and thus can cause stack overflow.

Breadth-first Search (BFS)

Queue based

Add root to queue
Loop while queue is not empty
- For breadth (number of directions - in case of array, level length - in trees etc.)
  - poll queue
  - visit polled node (add to result, visited array etc)
  - add neighbors to queue

BFS on 2D array of graph

private void bfs(char[][] grid, boolean[][] visited, int i, int j){
	Queue<Cell> q= new LinkedList<>();
	q.add(new Cell(i,j));
	int[] dir_row = {-1,1,0,0};
	int[] dir_col = {0,0,-1,1};

	while(!q.isEmpty()){
		Cell cell = q.poll();
		i = cell.row;
		j = cell.col;
		for(int direction=0; direction<4; direction++ ){
			int ni = i + dir_row[direction];
			int nj = j + dir_col[direction];
			
			if(ni>=0 && nj>=0 
			&& ni<visited.length 
			&& nj<visited[0].length
			&& !visited[ni][nj]){
				
				visited[ni][nj] = true;
				
				if(grid[ni][nj] == '1') q.add(new Cell(ni, nj));
			}	
		}
	}
}

Sorting

Topological Sort

It is a way of sorting a #Directed Acyclic Graphs (DAGs) in an order where for any edge $u \to v$ , u always comes before v in the sort.

For a Topological Sort, the nodes should be executed in order of their direction.

The nodes with no prerequisites (no arrows pointing towards them) are the leaf nodes.
The leaf nodes come first in a postorder search and we trace back our steps from their.
For a Topological Sort, the nodes with no prerequisites should be executed last.

NOTE: Topological orderings are NOT unique.

Why being acyclic is a requirement for topological sort? => Topological sort determines the correct sequencing of steps to be performed, but if there is a cycle in the graph, which step should be performed first? We get stuck in a cycle.

Take below graph for example, 3 is dependent on 2, but 2 is dependent on 0 which in turn is dependent on 3 again. This results in ambiguity and computers have zero-tolerance for nonsense.

Determining Topological Sort

Postorder DFS

Since, the last node of topological sort is the first node of the postorder DFS traversal, and this order is maintained throughout the traversal => reversing postorder DFS automatically gives a topological sort for a Graph.

Kahn's Algorithm

Repeatedly remove nodes from the graph without any dependencies, and add them to the topological ordering - until all nodes are processed or a cycle is discovered (invalid case).

References

Amazing analogy on why BFS is optimal to find a path

i have started learning graph 3 days ago, correct me if i am wrong, but i have this imagination in mind, in the first part of the amazing spider man, when he is trying to hunt the lizard, he goes to the sewer.

Now when he is at that intersection where he plays video game on his phone, he can go to any of the tunnels and the lizard is at one of the end points. what did he do , did he send a single string down a tunnel? did he do a dfs ? or he send multiple strings in all the directions (the bfs), to reach his path?

He does a bfs , that way he can evenly distribute his search, send em strings in all directions in order to get to the target the quickest. And next things you know, there are several lizards coming at your from one of the strings and you know he's there. Spider-Man vs The Lizard - Sewer Fight Scene - The Amazing Spider-Man (2012) Movie CLIP HD - YouTube