graph algorithm

graph algorithm

Graph Representation: Adjacency Matrix and Adjacency List

A Graph is represented in two major data structures namely Adjacency Matrix and Adjacency List. This forms the basis of every graph algorithm. In this article, we have explored the two graph data structures in depth and explain when to use one of them

graph colouring

Overview of Graph Colouring Algorithms

In this introductory article on Graph Colouring, we explore topics such as vertex colouring, edge colouring, face colouring, chromatic number, k colouring, loop, edge, chromatic polynomial, total colouring and various algorithmic techniques for graph colouring.

graph colouring

Wigderson Graph Colouring Algorithm

Wigderson Algorithm is a graph colouring algorithm to color any n-vertex 3-colorable graph with O(√n) colors, and more generally to color any k-colorable graph. In this article, we have explored this wonderful graph colouring article in depth.

graph colouring

Welsh-Powell Algorithm

Pseudocode Implementations Complexity Applications Reading time: 20 minutes | Coding time: 9 minutes In graph theory, Welsh Powell is used to implement graph labeling; it is an assignment of labels traditionally called "colors&

graph algorithm

Edmonds Karp Algorithm for maximum flow

Edmonds–Karp algorithm is an optimized implementation of the Ford–Fulkerson method for computing the maximum flow in a flow network in O(V E^2) time instead of O(E |max_flow|) in case of Ford-Fulkerson algorithm.

graph algorithm

Dinic's algorithm for Maximum flow in a graph

Dinic's algorithm or Dinitz's algorithm is a strongly polynomial algorithm for computing the maximum flow in a flow network. The basic principle is that a Maximum flow = minimum cut and Breadth First Search is used as a sub-routine.

graph algorithm

Ford Fulkerson Algorithm for Maximum flow in a graph

Ford–Fulkerson algorithm is a greedy algorithm that computes the maximum flow in a flow network. The main idea is to find valid flow paths until there is none left, and add them up. It uses Depth First Search as a sub-routine.

graph algorithm

Boruvka Minimum Spanning Tree

Borůvka's algorithm is an algorithm for finding a minimum spanning tree in a graph for which all edge weights are distinct, or a minimum spanning forest in the case of a graph that is not connected.

graph algorithm

Prim Minimum Spanning Tree Algorithm

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. It finds a subset of the edges that forms a tree that includes every vertex,

graph algorithm

Kruskal Minimum Spanning Tree Algorithm

Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step

graph algorithm

What is a Minimum Spanning Tree?

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted directed or undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

graph algorithm

Shortest Path Faster Algorithm: Finding shortest path from a node

The Shortest Path Faster Algorithm (SPFA) is an improvement of the Bellman–Ford algorithm which computes single-source shortest paths in a weighted directed graph. The algorithm is believed to work well on random sparse graphs. SPFA Fanding Dung.

graph algorithm

Bellman-Ford Algorithm: Finding shortest path from a node

Bellman-Ford Algorithm is an algorithm for single source shortest path where edges can be negative (but if there is a cycle with negative weight, then this problem will be NP). The credit of Bellman-Ford Algorithm goes to Alfonso Shimbel, Richard Bellman, Lester Ford and Edward F. Moore.

graph algorithm

Floyd-Warshall Algorithm: Shortest path between all pair of nodes

Floyd-Warshall Algorithm is an algorithm based on dynamic programming technique to compute the shortest path between all pair of nodes in a graph. The credit of Floyd-Warshall Algorithm goes to Robert Floyd, Bernard Roy and Stephen Warshall.

graph algorithm

Dijkstra's algorithm: Finding shortest path between all nodes

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph. Dijkstra's algorithm is applicable for: Both directed and undirected graphs, All edges must have nonnegative weights, Graph must be connected

graph algorithm

Breadth First Search

Breadth-first search (BFS) algorithm is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores along adjacent nodes and proceeds recursively.

graph algorithm

Fleury’s Algorithm: Finding Eulerian tours in a graph

Fleury's algorithm is a simple algorithm for finding Eulerian paths or tours. It proceeds by repeatedly removing edges from the graph in such way, that the graph remains Eulerian.

graph algorithm

What is a Euler or Eulerian tour?

An Euler tour or Eulerian tour in an undirected graph is a tour/ path that traverses each edge of the graph exactly once. Graphs that have an Euler tour are called Eulerian graphs.

graph algorithm

Find articulation points or cut vertices in a graph

Find articulation point or cut vertices in a graph. A vertex in an undirected connected graph is an articulation point or cut vertex if and only if removing it, and the edges connected to it, splits the graph into multiple components. Hint: Apply Depth First Search on a graph.

graph algorithm

Find cut edges in a graph

Find cut edges in a graph in linear time complexity using Depth First Search. A cut edge e = uv is an edge whose removal disconnects u from v. There are two key observations to solve this problem.

graph algorithm

Depth First Search

Depth-first search (DFS) algorithm is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.