Graphs Archives - Only Code

Travelling Salesman Problem using Held-Karp Algorithm | Dynamic Programming

The Held-Karp algorithm is an efficient dynamic programming approach for solving the Travelling Salesman Problem (TSP). The algorithm builds up a table to store the optimal cost of visiting subsets of cities.

Algorithms, Dynamic Programming, Graphs

Travelling Salesman Problem using Nearest Neighbour Algorithm

Given a list of cities and the distances between each pair of cities, find the shortest possible route that visits each city exactly once and returns to the origin city.

Algorithms, Graphs, Greedy approach

Why is a Bipartite graph with an odd number of vertices a Non-Hamiltonian graph?

A Hamiltonian cycle, also known as a Hamilton cycle or Hamiltonian circuit, is a cycle in a graph that visits every vertex exactly once, except for the starting vertex.

Graphs

Understanding Prim’s Algorithm for Minimum Spanning Tree in C++

Prim’s Algorithm is a popular greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, weighted graph.

Algorithms, Graphs, Greedy approach

Minimum Spanning Tree (MST) | Kruskal’s Algorithm in C++

Kruskal’s algorithm is one of the popular algorithms used to find an MST in a connected weighted graph. This algorithm is efficient, easy to understand, and guarantees the construction of a minimum-weight spanning tree.

Algorithms, Graphs, Greedy approach

Bellman-Ford Algorithm | Single source shortest path

This algorithm uses Relaxation, to find the shortest path between the source vertex and other vertices. It gradually expands the search space until the shortest path to the destination node is found.

Algorithms, Dynamic Programming, Graphs

Dijkstra’s Algorithm | Single source shortest path

Dijkstra’s algorithm works based on the principle of Greedy-approach, gradually expanding the search space until the shortest path to the destination node is found.

Algorithms, Graphs, Greedy approach

What is a Bipartite Graph?

A Bipartite Graph is a graph whose vertices can be divided into two sets such that no two vertices within the same set are adjacent.

Graphs

Floyd-Warshall Algorithm Implementation | All pairs shortest path

Floyd-Warshall algorithm helps in finding the shortest path between all pairs of vertices in a graph.

Algorithms, Dynamic Programming, Graphs

Directed and Undirected Graphs (Implementation)

A graph consists of two sets, namely V (vertices) and E (Edges). V represents a non-empty sets of vertices present in the graph. While E, represents the set of edges (joining two vertices) in the graph.

Graphs