Graph Created From Scratch

Interface

Composed with Non-empty set of Vertex and the set of the Edge.

class Edge(v: int, w: int, weight: int = 1)

The edge of two given vertices.

__init__(v: int, w: int, weight: int = 1) → None

Initialize an edge of two given vertices.

Parameters:

• v – The vertex \(v\).

• w – The vertex \(w\).

• weight – The weight of two vertices. Optional, defaults to 1 if not provided.

class MGraph(vertex_num: int)

Implement with Adjacency Matrix.

__init__(vertex_num: int) → None

Create and return an empty Graph with given number of the vertices.

Parameters:

vertex_num – The number of the vertices in the graph.

Variables:

• data – The data list of the vertex.

• edge – The weight lists of the edges.

• nv – The number of the vertices.

• ne – The number of the edges.

insert_vertex(vertex) → MGraph

Insert vertex \(v\) into the Graph.

insert_edge(edge: Edge) → None

Insert edge \(e\) into the Graph.

dfs(vertex) → None

The algorithm of Depth First Search, DFS.

bfs(graph, vertex) → None

The algorithm of Breadth First Search, BFS.

shortest_path(vertex, list) → None

Calculate the shortest path from vert \(v\) to the others.

mst() → None

Calculate the MST.

build_graph() → None

Build the graph in an interactive way.

class EdgeNode(vertex: int, weight: int = 1)

The head of the Adjacency List.

__init__(vertex: int, weight: int = 1) → None

class AdjItem

The node of the Adjacency List, or the sentinel node of linked list.

__init__() → None

class LGraph(vertex_num: int)

Implement with Adjacency List.

__init__(vertex_num: int) → None

Create and return an empty Graph with given number of the vertices.

Parameters:

vertex_num – The number of the vertices in the graph.

insert_edge(edge: Edge) → None

Insert edge \(e\) in to the LGraph.

build_graph() → None

Build the graph in an interactive way.