connectivity

Why do you need to have 3 states (“Visited, &… Anonymous - Aug 4, 2016Why do you need to have 3 states (“Visited, “Unvisited”, and “Visiting”)? It seems like we do the same thing - adding the node to the queue - if it’s unvisited, but there is no functional distinction between visited and visiting (in either state we skip it - we won’t enqueue it and we won’t check against it). [Read More]

Problem : Given a Directed Graph and two vertices in it, check whether there is a path from the first given vertex to second. Solution We have already seen solution to connectivity in undirected graph via bfs. Now lets see it on directed graph. BFS to check the connectivity public enum State { Unvisited, Visited, Visiting; } public static boolean search(Graph g, Node start, Node end) { LinkedList<Node> q = new LinkedList<Node>(); // operates as Stack for (Node u : g. [Read More]

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]

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]