Adjacency Matrix Graph

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

class MGraph(num_vert: int, /)

Adjacency matrix graph.

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

The Breadth First Search.

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

The Depth First Search.

floyd_warshall() → tuple[list[list[float]], list[list[float]]]

The Floyd-Warshall algorithm for finding shortest paths.

Time complexity is \(O(\vert V \vert ^3)\).

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

Insert the edge that connect the node v and node w.

prim(start: int = 1, /) → MGraph

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

Time complexity is \(O(\vert V \vert ^2)\).

Floyd-Warshall Algorithm

The adjacency list for graph representation suits most algorithms except the Floyd-Warshall Algorithm. The Floyd-Warshall Algorithm is more efficient in a graph represented by an adjacency matrix.

Prim’s Algorithm

The key to the optimization of the Prim’s algorithm is the implementation of a priority queue, such as the MinHeap in the previous chapter, or the heapq in the python standard library.

The algorithm is more efficient for dense graph. Also, it offers more flexibility when implemented with an adjacency list for graph representation. Combining with the priority queue and adjacency list, its time complexity can be optimized to \(O(\vert E \vert \log \vert V \vert)\).