Cuts of Graphs
Posted on August 22, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
A cut of a graph (V, E) is a partition of a graph into two non-empty sets A and B. Each set contains only the vertices that connect one vertex in the set to another in the set. Meanwhile, there are also edges connecting the vertices from set A to set B and vice versa. For eg.
Similarly we have directed graph. Edges, that cross from A, to B are called are crossing edges.
[Read More]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]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]Minimum Cut Problem
Posted on August 4, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Input - An undirected graph G = (V,E) (note that parallel edges are allowed)
Goal - Tom compute a cut with fewest number of crossing edges (a min cut) The minimum cut problem or min-cut problem is to determine the cut which has the least number of crossing edges.
Please note that to understand mincut, you have to first read what is cut, if you don’t alreadyy know that. So, consider the following graph -
[Read More]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]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]Adjacency list represention of graph in Java
Posted on August 4, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Here is the program for adjacency list representation of graphs using java. If you are new to Graphs please read about graphs here before reading the rest of this post.
Code:
package com.vaani.algo.graph.impl; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; public class GraphUsingAdjList { class Node { int node; List<Integer> adjList; boolean visited; } void insertVertices() throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); System.out.println("Enter number of nodes in a graph: "); int n=(Integer.
[Read More]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]What is a Graph data structure?
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Graphs consist of 2 ingredients :
Vertices (V) , also called nodes and can be pictured as dots Edges (E) , the line connecting the nodes. Types of Graphs
Depending on the edges, there two types of graphs:
Undirected Graphs - A graph that entail edges with ordered pair of vertices, however it does not have direction define. Example of such a graph is the ‘Family tree of the Greek gods’ **Directed Graphs (**aka Arcs) - Directed Graph: A graph that entail edges with ordered pair of vertices and has direction indicated with an arrow.
[Read More]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]