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.
Category: 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.
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.
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.
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.
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.
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.
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.
Given a sorted Alien dictionary, find order of characters
In an alien language, surprisingly, they also use English lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.
Topological Sort [Hackerearth]
A Topological sort of a Directed-Acyclic graph G is a linear ordering of all its vertices such that if G contains an edge E (u, v), then u appears before v in the ordering. And if the graph is not acyclic, then no linear ordering is possible.