Minimum Spanning tree MST

 Posted on October 19, 2013  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

MST is used to connect a bunch of points to each other as cheaply as possible. Applications clustering networking Blazingly fast greedy algorithms There are many greedy algorithm, but we will talk about 2: Prim’s algo [1957, also djikstra’ 1959] or Jarnic found it in 25 years earlier. Kruskal’s algo[1956]. Will be using union find data-structure. They are blazingly fast as they are almost close to linear time of number of edges: [Read More]
tree  kodeknight  greedy Algo  minimum-spanning-tree  MST  spanning tree  graph-search 

BFS (Breadth first search) on Graph

 Posted on August 25, 2013  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Algorithm Starting at some arbitrarily chosen vertex s (s stands for start vertex) , we mark v so that we know we’ve visited it, process v, and  then visit i.e. mark the vertex as visited and process all of v’s neighbors.  Now that we’ve visited and processed all of v’s neighbors,  we need to visit and process all of v’s neighbors neighbors Pseudocode BFS(graph G, vertex s) allnodesinitiallyunexploredall nodes initially unexplored \-mark s as explored let Q = queue data structure, initialized with s while (Q not empty) remove the first node of Q, call it v for each edge (v, w): if w is unexplored mark w as explored add w to Q (at the end) We visit each node only once and each edge at most twice (for edge(v, w), we might encounter it when we’re at node v and at node w). [Read More]
Graph  kodeknight  queue  BFS  graph-search  Undirected Graph 

DFS (Depth first search) for graph

 Posted on August 25, 2013  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

What is dfs? This algorithm explores aggressively and backtracks only when necessary. This is similar to how we play a maze game. To code DFS iteratively, we can mimic BFS , but use a Stack instead of a Queue. Another way to code this would be to do it recursively. DFS is very naturally phased as recursive example. We will see both of implementation later. DFS(graph G, vertex s) mark s as explored for every edge (s, v): if v unexplored DFS(G, v) Example : Consider the graph: [Read More]
Graph  kodeknight  time complexity  DFS  graph-search 

Dijkstra's algorithm for equal weight edges using BFS

 Posted on August 25, 2013  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

This is the application of BFS (breadth first search) dist(v) = fewest number of edges on path s to v. Here is the pseudocode: Initialize dist(v) = {0 if v=s, infinity if v != s} foreach vertex v in all vertices { if(v==s) dist(v) = 0; else dist(v) = infinity; } Now apply BFS, and hen considering edge (v, w), if w is unexplored, then set dist(w) = dist(v)+1, keeping rest of the BFS same. [Read More]
Graph  kodeknight  BFS  graph-search 

Strongly Connected Graph

 Posted on August 4, 2013  (Last modified on August 7, 2020)  |  6 minutes  |  Kinshuk Chandra

A strongly connected graph is a graph such that there is a path connecting each vertex in the graph to another vertex in the graph. The strongly connected components (SCCs) of a directed graph G are the equivalence classes of the relation: u~v <-> path u->v AND path v->u. The ~ relation is an equivalence class, that is, ~ is reflexive, symmetric, and transitive. (Reflexive => everybody is related to itself, symmetric => if u is related to v, then v is related to u and Transitive => if u is related to v, v to w then w is related to u ) [Read More]
Graph  kodeknight  connectivity  graph-search 

Topological Sorting

 Posted on August 4, 2013  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

Definition Topological sort: an ordering of the vertices in a directed acyclic graph, such that: If there is a path from u to v, then v appears after u in the ordering. A topological ordering of a directed graph G is a labeling f of G’s nodes (1…n) such that: (1) the f(v)’s are the set {1, 2, … , n} (2) if (u, v) in G, then f(u) < f(v) … the graph should move in forward direction. [Read More]
Graph  tree  kodeknight  sorting  DFS  incomplete  graph-search 

BFS and Undirected Connectivity

 Posted on August 4, 2013  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Let G=(V,E) be an undirected graph (Note - for directed graph, better algorithms are available) Connected Components - the pieces of G, where graphs are connected in equivalence class. Formal definition of max connectivity - Equivalence relation between 2 vertices u and v for every u to v path in G. Equivalence relation between 2 vertices means they have to satisfly 3 conditions of equivalence Reflexive - Everything has to be related to itself Symmetric - If u is related to v, then v is related to u, which is not a problem for undirected graph Transitive - If u and v are related and v and w are related, then u and w are related Application [Read More]
Graph  kodeknight  connectivity  BFS  graph-search 

Dijkstra's Shortest Path Algorithm

 Posted on August 4, 2013  (Last modified on August 7, 2020)  |  6 minutes  |  Kinshuk Chandra

It’s Dijkstra’s algorithm, that lets you find single-source shortest paths. Problem Problem - Single source shortest paths Input - Directed graph G=(V,E) Source vertex s  Output - foreach v∈V, compute L(v)=length of a shortest s-v path in G. Assumptions: There is a path from vertex s to vertex v (otherwise, the path length is infinity) Edge lengths are non-negative (there are other algorithms for this called , but most famous being Bellman ford algorithm which uses dynamic programming) Example of shortest path [Read More]
Graph  kodeknight  shortest-path  time complexity  BFS  incomplete  heap  graph-search 

Graph Search Introduction

 Posted on August 3, 2013  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Graph search algorithms are important but lets have some motivations. Motivation behind graph search Here are few motivations: Minimal Road network - Are there sufficient roads for people to go from one place to another. Imagine, Haridwar is only connected via Delhi and there is a natural calamity, then one way people can reach there for relief etc is via Delhi, resulting in worst disaster management, but suppose it is connected via many places, sending relief will be easier. [Read More]
Graph  kodeknight  BFS  DFS  incomplete  graph-search 

DFS (Depth First Search) on tree or graph

 Posted on January 1, 2012  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Consider this tree (which is a graph without a cycle) : Now DFS means traversing to the depth…and then going up, so here DFS traversal will result in 5 2 -4 3 21 19 25. We can use non recursive as well recursive approach to solve this problem. A depth first search (DFS) through a tree starts at the root and goes straight down a single branch until a leaf is reached. [Read More]
backtracking  Graph  search  tree  kodeknight  sorting  DFS  incomplete  traversal  binary-search-tree  BST  graph-search