Algos on graph

Construction of a graph from a list of edges

from collections import defaultdict
from collections import deque

edges = [[1,2], [2,3], [5,2], [1, 5]]
graph = defaultdict(list)

for a, b in edges:
    graph[a] += [b]
    graph[b] += [a] # this line for undirected graphs only

BFS

Breadth-first search is a particular search on a graph. Breadth-first search is useful when you need to find the length of a shortest path from one vertex to another (in unweighted graph). Also, with BFS you can traverse a graph Breadth-first search implementation is non-recursive.

bfs(start, target)

Find the length of a shortest path from the start node to the target node in an unweighted graph.

Time complexity: \(O(n + m)\), where n is the number of vertices and m is the number of edges

Maze problem:

For instance, you have a matrix (m x n) with zeros and ones, you can move from the current cell to one of four adjacent cells whenever that adjacent cell is filled by zero initial position is (0, 0), find the length of a shortest path to the right-bottom cell (m - 1, n - 1), if you can’t reach the right-bottom cell, return -1

0 1 0 0 0

0 1 0 1 0

0 1 0 1 0

0 0 0 1 0

answer: 13

bfs_matrix(start)

Find the length of a shortest path to the right-bottom cell (m-1, n-1) in a matrix.

Time complexity: \(O(mn)\)

Space complexity: \(O(mn)\) where m is the number of rows and n is the number of columns in the matrix

Parameters:

start – tuple

Returns:

int

DFS

Depth-First Search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking. DFS is typically implemented recursively, but can be implemented iteratively as well.

Time complexity: \(O(V + E)\)

Space complexity: \(O(V)\), where V is the number of vertices and E is the number of edges in the graph.

Applications:

• Topological sorting

• Finding connected components

• Finding bridges and articulation points

• Finding strongly connected components

• Solving puzzles with only one solution, such as mazes

findCircleNum(isConnected: List[List[int]]) → int

Example problem: https://leetcode.com/problems/number-of-provinces/

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Time complexity: \(O(n^2)\)

Space complexity: \(O(n)\)

numEnclaves(grid: List[List[int]]) → int

Example problem: https://leetcode.com/problems/number-of-enclaves/

You are given an m x n binary matrix grid, where 0 represents a sea cell and 1 represents a land cell.

A move consists of walking from one land cell to another adjacent (4-directionally) land cell or walking off the boundary of the grid.

Return the number of land cells in grid for which we cannot walk off the boundary of the grid in any number of moves.

Time complexity: \(O(mn)\)

Space complexity: \(O(mn)\)

Dijkstra

shortestPath(edges: List[List[int]], costs: List[int], start: int, end: int) → int

Find the shortest path in a weighted graph from the start node to the end node. Dijkstra’s algorithm is a greedy algorithm that finds the shortest path between nodes in a graph.

Time complexity: \(O(E \log V)\)

Space complexity: \(O(E + V)\)

Return type:

int