Floyd-Warshall algorithm helps in finding the shortest path between all pairs of vertices in a graph.
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.
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.
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.
This problem was asked in February challenge 2014. Around 900 people were able to solve this problem.
It’s not very intuitive for beginners. And also not very straightforward for someone not doing competitive programming.
DFS (Depth-First Search) is an algorithm for traversing a graph. DFS starts from source vertex (graph) or root (in trees) and then visits an unvisited adjacent node v. After that it checks if node v has any adjacent node which is unvisited. If it reaches a leaf node or any node having no unvisited adjacent node. It backtracks and continue traversing other nodes.
BFS (Breadth-First Search) is one of the simplest algorithms for traversing a graph. Prim’s min-spanning-tree and Djikstra’s algorithm use similar ideas as BFS. BFS is also known as Level-order traversal because the algorithm discover all nodes at distance k from root before discovering any nodes at distance k+1.