Data Structures Package for the Advanced Data Structures learning unit.
It contains python implementations of Advanced Data Structures, Search Algorithms, Binary Trees and Graphs.
- Graph
- Binary Tree
- Havel-Hakimi
- Dijkstra
- Floyd-Warshall
- Prim
- Kruskal
- Hopcroft-Tarjan
- Depth-first search
- Preorder
- Inorder
- Postorder
- Breadth-first search
Havel-Hakimi algorithm is a way to determine if a given degree sequence can be represented by a simple graph. It works by removing the largest degree vertex and subtracting one from the next largest degree until either all degrees are 0 or an invalid sequence is found.
Dijkstra's algorithm is a shortest path algorithm that calculates the shortest path from a single source node to all other nodes in a weighted graph. It works by maintaining a priority queue of vertices and updating the minimum distance to each vertex based on the edges and weights in the graph.
The Floyd-Warshall algorithm is a dynamic programming algorithm that calculates the shortest path between all pairs of vertices in a weighted graph. It works by storing the minimum distance between each pair of vertices and updating this distance based on intermediate vertices.
Prim's algorithm is a greedy algorithm that finds the minimum spanning tree of a weighted undirected graph. It works by starting with a single vertex and iteratively adding the shortest edge that connects to a new vertex until all vertices are included in the tree.
Kruskal's algorithm is a greedy algorithm that finds the minimum spanning tree of a weighted undirected graph. It works by sorting the edges by weight and iteratively adding the next shortest edge that does not create a cycle until all vertices are included in the tree.
Tarjan's strongly connected components algorithm is an algorithm in graph theory for finding the strongly connected components (SCCs) of a directed graph.