Skip to content

Latest commit

 

History

History
159 lines (120 loc) · 5.08 KB

2.5 - Other Graph Algorithms.md

File metadata and controls

159 lines (120 loc) · 5.08 KB

Other Graph Algorithms

Prim's Algorithm (Adapted from Wikipedia, GIF)

  • Finds a minimum spanning tree for a weighted, undirected graph.
    • A minimum spanning tree is a subset of the edges that forms a tree, which contains every vertex, where the total weight of all the edges in the tree is minimized.
  1. Create a set mstSet that keeps track of the vertices already included in the MST.
  2. Initialize key values for all the vertices in the graph as infinite, except for the starting node, which is assigned a value of 0 and is the root node for the MST.
  3. While mstSet does not include all the vertices:
    1. Pick a vertex u, which is not in mstSet and has the minimum key value.
    2. Add u to mstSet.
    3. Update the key values of all adjacent vertices to u. For every adjacent vertex v, update the key value (and parent node) if the weight of the edge u, v is less than the previous key value of v.
int[] primMST(int graph[][]) {
    int V = graph.length;
    int[] parent = new int[V];  // stores constructed MST
    int[] key = new int[V];  // key values
    boolean[] mstSet = new boolean[V];  // keeps track of which vertex is in MST

    for (int i = 0; i < V; i++) key[i] = Integer.MAX_VALUE;

    key[0] = 0;
    parent[0] = -1;  // root of tree
    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet);  // pick the minimum key vertex not in mstSet
        mstSet[u] = true;

        for (int v = 0; v < V; v++) {
            if (graph[u][v] != 0 && mstSet[v] == false && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }

    return parent;
}

Time Complexity

  • Adjacency Matrix Implementation: O(|V|^2)
  • Binary Heap & Adjacency List Implementation: O(|E| log |V|)

Kruskal's Algorithm (Adapted from Wikipedia, GIF)

  • Finds a minimum spanning tree for a weighted, undirected graph.
  1. Create a graph F (a set of trees), where each vertex of the input graph is a separate tree.
  2. Create a set S containing all the edges of the graph.
  3. While S is not empty and F is not yet spanning:
    1. Remove an edge with minimum weight from S.
    2. If the removed edge connects two different trees, then add it to the forest F, combining two trees into a single tree.

Time Complexity

O(|E| log |E|) = O(|E| log |V|^2) = O(|E| * 2 log |V|) = O(|E| log |V|)

Topological Sort

  • A topological sort of a directed acyclic graph's (DAG) nodes is a linear ordering such that for every edge (u, v), u comes before v in the ordering.
    • A DAG has at least one vertex with in-degree 0 and one vertex with out-degree 0.
class Node {
    int index;
    int val;
    Node[] neighbors;
}

Kahn's Algorithm

  1. Compute the in-degree for each vertex present in the DAG and initialize the count of visited nodes to 0.
  2. Pick all the vertices with in-degree 0 and enqueue them.
  3. Remove a vertex from the queue and repeat the following till the queue is empty:
    1. Increment the count of visited nodes by 1.
    2. Decrease in-degree by 1 for all its neighboring nodes.
    3. If the in-degree of a neighboring node is reduced to 0, enqueue it.
  4. If the count of visited nodes is not equal to the number of nodes in the graph, a topological sort does not exist.
void topologicalSort(Node[] graph) {
    int V = graph.length;

    int[] indegree = new int[V];
    for (Node node : graph) {
        for (Node neighbor : node.neighbors) indegree[neighbor.index]++;
    }

    Queue<Integer> queue = new LinkedList<>();
    for (Node node : graph) {
        if (indegree[node.index] == 0) queue.add(node.index);
    }

    int c = 0;
    ArrayList<Integer> topOrder = new ArrayList<>();
    while (!queue.isEmpty()) {
        int u = queue.poll();
        topOrder.add(u);

        for (Node neighbor : graph[u].neighbors) {
            indegree[neighbor.index]--;
            if (indegree[neighbor.index] == 0) queue.add(neighbor.index);
        }

        c++;
    }

    if (c != v) {
        System.out.println("A cycle exists. Topological sort not possible.");
        return;
    }

    for (int i : topOrder) System.out.print(graph[i].val + " ");
}

Time Complexity

O(|V| + |E|)

DFS-like Implementation

void topologicalSort(Node[] graph) {
    Stack<Integer> stack = new Stack<>();
    int V = graph.length;
    boolean[] visited = new boolean[V];

    for (int i = 0; i < V; i++)
        if (visited[i] == false)
            topologicalSortUtil(i, visited, stack, graph);

    while (!stack.isEmpty()) System.out.print(stack.pop() + " ");
}

void topologicalSortUtil(int index, boolean visited[], Stack stack, Node[] graph) {
    visited[index] = true;

    for (Node neighbor : graph[index].neighbors) {
        if (!visited[neighbor.index]) topologicalSortUtil(neighbor.index, visited, stack, graph);
    }

    stack.push(graph[index].val);
}

Time Complexity

O(|V| + |E|)