Graphs

Terminology

A graph \(G\) is composed of a set of vertices (or nodes) \(V\), and a set of edges \(E\), where each edge connects a pair of nodes.

• An Edge e in E is represented as a two-element subset of V: e = {u, v} for some u, v in V.
• Directed Graph: A directed graph G' consists of a set of nodes V and a set of directed Edges E'. Each e' in E' is an ordered pair (u,v).
• When an edge connects 2 vertices, the vertices are said to be adjacent.
• A connected graph with no cycles is called a tree.
• A degree of a vertex is the number of edges incident on it.
• A subgraph is a subset of a graph's edges that form a graph.
• A path in an undirected graph G = (V, E) is a sequence of nodes \(v_1, v_2, \dots v_{k-1}, v_k\) with property that each consecutive pair \(v_i\), \(v_{i+1}\) is joined by an edge in G.
• An undirected graph is connected if, for every pair of nodes u and v, there is a path from u to v.
• If a graph is not connected, then it consists of a set of connected components.
• Spanning tree: a subgraph of a connecting graph that contains all of a graph's vertices and is a single tree.
• Bipartite graph: a graph whose vertices can be divided into 2 sets such that all edges connect a vertex in one set with a vertex in another set.
• A Hamiltonian path is a path in a graph that visits each vertex exactly once.
• An Eulerian Path is a path that visits each edge once; vertices can be repeated.

Representations

Adjacency Matrix

class Graph {
    val V: Int
    val E: Int
    val adjMatrix: List<List<Int>>
}

Adjacency Matrix is a square matrix of size V x V, with boolean values. The value at [u, v] is set to 1 if there is an edge from vertex u to vertex v.
Adjacency Matrix is good if the graph is dense. The matrix requires O(\(V^2\)) bits of storage and O(\(V^2\)) for initialization. If the graph is sparse, initialization time dominates.

Adjacency List

All the vertices connected to a vertex v are in a list (linked list, array).

class Graph {
    val V: Int
    val E: Int
    val adjList: List<LinkedList<Int>>
}

This representation is slow for some operations. Checking is an edge exists between vertex u and v takes O(V).

Adjacency Set

Similar to an Adjacency list but instead of Linked lists, uses Disjoint sets.

Traversals

Depth First Search

In DFS, we go as deep as possible on one path before backtracking and trying a different one. Initially, all vertices are marked unvisited.

fun dfs(graph: Map<String, List<String>>, start: String) {
    val visited = mutableSetOf<String>()
    val stack = ArrayDeque<String>()

    stack.add(start)
    while(stack.isNotEmpty()) {
        node = stack.removeLast()
        if (node !in visited) {
            // Process Node
            visited.add(node)
            stack.addAll(graph[node]?.reversed())
        }
    }
}

DFS traversal creates a tree, we call it as a DFS tree. The edges that are not part of the tree are called back edges.

Breadth First Search

In BFS, we explore all nodes in the next level before going deeper. Similar to level-order traversal in a tree.

fun bfs(graph: Map<String, List<String>>, start: String) {
    val visited = mutableSetOf<String>()
    val queue = LinkedList<String>()
    queue.add(start)

    while(queue.isNotEmpty()) {
        val node = queue.removeFirst()
        if (node !in visited) {
            // Process Node
            visited.add(node)
            queue.addAll(graph[node]?.filter{ it !in visited})
        }
    }
}

In general, BFS requires more memory than DFS, as BFS requires storing all children at each level.
BFS: Shortest paths.
DFS: Minimal memory use, maze puzzles.

Topological Sort

We have a series of tasks where we cannot start one task until after its prerequisites are completed. We want to organize the tasks in a linear order that allows us to complete one at a time. We can model the problem as a DAG. The process of getting linear order from a DAG is called topological sort.

Topological sort is an ordering of vertices in a DAG in which each node comes before all noes to which it has outgoing edges.

Algo:

1. Count the indegree—number of edges that lead to a vertex.
2. Push all nodes with indegree equal to 0 to a queue.
3. While the queue is not empty, pop a node add it to sort order and decrease indegree of all adjacent nodes. Add nodes with 0 indegree to the queue.

// Using adjacency matrix representation

fun getInDegree(graph: List<List<Int>>, node: Imt): Int {
    var cnt = 0
    graph.forEach {
        if(it[node] == 1) cnt ++
    }
    return cnt
}

fun topologicalSort(graph: Graph): List<Int> {
    val topSort = mutableListOf<Int>()
    val queue = ArrayDeque<Int>()

    val inDegree = MutableListOf<Int>(graph.size)

    (0 until graph.V).forEach { node ->
        inDegree[node] = getInDegree(graph.adjMatrix, node)
        if (inDegree[node] == 0) queue.add(node)
    }

    while(queue.isNotEmpty) {
        val node = queue.removeFirst()
        topSort.add(node)
        graph.adjMatrix[node].forEach { adjs ->
            adjs.forEachIndexed{ idx, isEdge ->
                if(isEdge == 1) {
                    inDegree[idx]--
                    if(inDegree[idx] == 0) queue.add(idx)
                }
            }
        }
    }

    return topSort
}

Shortest Path Algorithms

Given a graph G and a vertex s, we need to find the shortest path from s to every other vertex in G.

Unweighted Graph

The algorithm is similar to BFS.

// adjacency list
fun shortestPath(graph: Graph, s: Int) {
    val distances = MutableList(graph.V) { -1 }
    val path = MutableList(graph.V) { -1 }
    val queue = ArrayDeque<Int>()
    queue.add(s)
    distances[s] = 0

    while(queue.isNotEmpty()) {
        val node = queue.removeFirst()
        graph.adjList[node].forEach {
            if (distances[it] != -1) { // Not yet visited
                queue.add(it)
                distances[it] = distances[node] + 1
                path[it] = node
            }
        }
    }
}

Time Complexity: O(\(|E| + |V|\)) if an adjacency list is used. O(\(|V|^2\)) if an adjacency matrix is used

Weighted Graph (Dijkstra's)

• Initialize distances to -1. Use a priority queue to get a node with the smallest distance.
• Pick an unvisited node with the smallest known distance. For each of its neighbors, calculate distance. If weight is less than recorded update distance. Mark the node as visited.

fun dijkstra(graph: Graph, weights: List<List<Int>>, s: Int) {
    val distances = MutableList(graph.V) { -1 }
    val path = MutableList(graph.V) { -1 }
    val pq = PriorityQueue(comapreBy<Pair<Int, Int>> { it.second })

    pq.add(Pair(s, 0))
    distances[s] = 0

    while(pr.isNotEmpty()) {
        val (node, dis) = pq.poll()

        if(dis > distances[node]) continue

        graph.adjList[node].forEach {
            val newDist = dis + weights[node][it]
            if(distances[it] == -1 || newDist < distaces[it]) {
                distances[it] = newDist
                path[it] = node
                pq.add(Pair(it, newDist))
            }
        }
    }
}

Negative edges (Bellman-Ford)

Dijkstra's algorithm doesn't work with negative weighted edges. Dijkstra’s algorithm works by always expanding the node with the current smallest known distance. It locks in that distance and never revisits the node again.

Relaxation means updating the shortest distance to a node if a shorter path is found through another node. A shortest path between two vertices can have at most (V - 1) edges. It is not possible to have a simple path with more than (V - 1) edges (otherwise it would form a cycle). Therefore, repeating the relaxation process (V - 1) times ensures that all possible paths between source and any other node have been covered.

Algo:

• Initialize distances to max value.
• For each edge u -> v with weight w: if dist[u] + 2 < dist[v], update dist[v] = dist[u] + 2
• check for negative weight cycles

fun bellmanFord(graph: Graph, weights: List<List<Int>>, s: Int) {
    val distances = MutableList(graph.V) { Int.MAX_VALUE }
    val path = MutableList(graph.V) { -1 }
    distances[s] = 0

    for(i in 1 until graph.V) {
        graph.adjList.forEachIndexed { u, edges ->
            edges.forEach { v ->
                if(dist[u] != Int.MAX_VALUE && dist[u] + weights[u][v] < dist[v]) {
                    dist[v] = dist[u] + weights[u][v]
                    path[v] = u
                }
            }
        }
    }


}

Time Complexity: O(VE)

Shortest Path Faster Algorithm

An improvement of the Bellman-Ford algorithm which takes advantage of the fact that not all attempts at relaxation will work. The main idea is to create a queue containing only the vertices that were relaxed but that still could further relax their neighbors. And whenever you can relax some neighbor, you should put it in the queue.

fun spfa(graph: Graph, weights: List<List<Int>>, s: Int) {
    val distances = MutableList(graph.V) { Int.MAX_VALUE }
    val inQueue = BooleanArray(graph.V) { false }
    val count = IntArray(graph.V) { 0 }

    val queue = ArrayDeque<Int>()
    distances[s] = 0
    queue.add(s)
    inQueue[s] = true

    while(queue.isNotEmpty()) {
        val node = queue.removeFirst()
        inQueue[node] = false

        graph.adjList[node].forEach {
            if(distances[mode] != Int.MAX_VALUE && distances[node] + weights[node][it] < distances[it]) {
                distances[it] = distances[node] + weigths[node][it]
                if(!inQueue[it]) {
                    queue.add(it)
                    inQueue[it] = true
                    count[it]++
                    if (count[it] > graph.V) {
                        return // Negative cycles
                    }
                }
            }
        }
    }
}

Floyd Warshall

Shortest path distance between all pairs of nodes i and j in the graph.

Refer DP

Minimal spanning tree

A subgraph of a graph that contains all the vertices and is also a tree is called a spanning Tree. The cost of a spanning tree is the sum of weights of all the edges of the tree. A minimum spanning tree of an undirected graph G is a tree formed from graph edges that connect all vertices with minimum total cost. A spanning tree exists only is the graph is connected.

Prim's Algorithm

Prim's algorithm uses a greedy approach. The idea is to maintain two sets of nodes: one set contains the nodes already included in the spanning tree, and the other contains the remaining nodes. At each step, we add the node from the remaining set that is connected to the tree by the edge with the smallest weight.
Algo:

1. Start with a random node.
2. Add the smallest weight edge that codes a node in tree to a node outside the tree.
3. Repeat 2 until all nodes are added to the tree.

data class Node(val vertex: Int, val weight: Int, val parent: Int): Comparable<Node> {
    override fun compareTo(other: Node) = this.weight - other.weight
}

fun prims(graph: Graph, weights: List<List<Int>>, start: Int = 0) {
    val pq = PriorityQueue<Node>()
    val visited = BooleanArray(graph.V) { false }
    val path = mutableMapOf<Int, Int>()

    // add a random node
    pq.add(Node(start, 0, -1))

    while(pq.isNotEmpty()) {
        val (node, wt, parent) = pq.poll()

        if(visited[node]) continue
        visited[node] = true

        path[node] = parent
        graph.adjList[node].forEach {
            if(!visited[it]){
                pq.add(Node(it, weights[node][it], node))
            }
        }
    }
}

Time Complexity: O(\((V +E)log V\))
Without heaps O(\(|V|^2\)) good for dense graphs.
With heap O(\(E log V\)) good for sparse graphs.

Kruskal's Algorithm

Kruskal's algorithm also uses the greedy approach. The algorithm starts with V different trees. Then select an edge with minimum weight and add that edge if it doesn't form a cycle. Adding an edge merges two trees into one. At the end, there will be only one tree.

Algo:

1. Sort all edges in non-decreasing order.
2. Initialise MST to an empty set.
3. Pick the smallest edge. Include it in MST if it doesn't form a cycle with the spanning tree.
4. Repeat 3

data class Edge(val src: Int, val dest: Int, val weight: Int)

fun kruskal(graph: Graph) {
    val mst = mutableListOf<Edge>()
    val ds = DisjointSet(graph.V)

    //create edges list from adjacency matrix or list
    val sortedEdges = edges.sortedBy{ it.weight }

    for (edge in sortedEdges) {
        if(ds.find(edge.src) != ds.find(edge.dest)) {
            mst.add(edge)
            ds.union(edge.src, edge.dest)
        }
    }
}

Time Complexity: O(\(E logE\)) dominated by sorting

Eulerian Path

Hierholzer's algorithm:

1. Check if an Eulerian Path exists:
2. All vertices have equal in-degree and out-degree except
3. one node has out-degree = in-degree + 1 (start vertex)
4. one node has in-degree = out-degree + 1 (end vertex)
5. Start at a node with out-degree = in-degree + 1 or any other node with outgoing edge
6. Traverse edges, removing them from the graph as you go.
7. When you can’t go further from the current vertex, backtrack (pop stack) and add vertex to the final path.
8. Because vertices are added when you backtrack, the final sequence will be reversed.

fun eulerianPath(adjList: MutableMap<String, MutableList<String>>) {
    val inDegree = mutableMapOf<String, Int>()
    val outDegree = mutableMapOf<String, Int>()

    adjList.forEach{ u, edges ->
        outDegree[u] = (outDegree[u] ?: 0) + 1
        edges.forEach { v -> 
            inDegree[v] = (inDegree[v] ?: 0) + 1
        }
    }

    var start = adjList.keys.first()
    for(node in adjList.keys + inDegree.keys) {
        if(outDegree[node] == inDegree[node] + 1) {
            start = node
            break
        }
    }

    val stack = ArrayDeque<String>()
    val path = mutableListOf<String>()

    stack.push(start)
    val adjListClone = adjList.mapValues { (_, ls) -> ls.toMutableList() }.toMutableMap()
    while(stack.Empty()) {
        val u = stack.peek()
        if(adjListClone[u]?.isNotEmpty() == true) {
            stack.add(adjListClone[u]!!.removeAt(adjListClone[u]!!.lastIndex))
        } else {
            path.add(stack.removeLast())
        }
    }

    return path.reversed()
}