Adjacency List Graph

Source code: src/pydsadoc/_graph/adjacency_list.py

class LGraph(num_vert: int, /)

Adjacency list graph.

bfs(start: int, /) → list[int]

The Breadth First Search.

dfs(start: int, /) → list[int]

The Depth First Search.

dijkstra(start: int, /) → list[list[float]]

The Dijkstra’s algorithm for finding the shortest paths.

Combining with the prioprity queue, the time complexity is \(O(\vert E \vert \log \vert V \vert)\).

insert_edge(v: int, w: int, weight: float = 1, /) → None

Insert the edge connect v and w into the graph.

kruskal() → LGraph

The Kruskal’s algorithm that finds a minumum spanning tree.

Time complexity is \(O(\vert E \vert \log \vert E \vert).\)

Dijkstra’s Algorithm

The Dijkstra’s algorithm can be optimized by using MinHeap in the previous chapter, or heapq in the python standard library. The algorithm is more efficient in sparse graph.

Kruskal’s Algorithm

The key to the optimization of the Kruskal’s algorithm is the implementation of the UnionFind in the previous chapter, which applies the path compression and union by rank in it. The algorithm is more efficient in sparse graph, too. The main effect on the time complexity is sorting edges.