graphsp

graphsp

プロジェクトの説明

このプロジェクトはGraph Data Structureに関連するアルゴリズムを実装します。

以下は、このライブラリが実装するアルゴリズムのリストです。

• 幅の最初の検索
• 深さの最初の検索
• Dijkstra（シングルソース最短パス）
• フロイドウォーシャル（すべてのペア最短パス）

インストール

pip install graphsp

使用法

from graphsp import Graph

グラフオブジェクトの初期化

 graph = graphsp.Graph(n, graph_type)

• n =ノードの総数
• graph_type = directed / undirected [in string]

グラフの初期化と入力

 graph = graphsp.Graph(5, "undirected")

graph.bulk_link([(0, 4, 5), (0, 1, 1), (1, 4, 3),
                 (1, 3, 1), (1, 2, 15), (2, 3, 2), (3, 4, 3)])

print(graph.detect_cycle())

異なるアルゴリズムを使用します

 dfs = DFS(n, graph)
print(dfs.dfs(start_node))

bfs = BFS(n, graph)
print(bfs.bfs(start_node))

dj = Dijkstra(n, graph)
print(dj.dijkstra(start_node))

bf = BellmanFord(n, graph)
print(bf.bellman_ford(start_node))

fw = FloydWarshall(n, graph)
print(fw.floyd_warshall())

ts = TopoSorting(n, graph)
print(ts.topo_sorting())

pr = Prim(n, graph)
print(pr.prim())

ks = Kruskal(n, graph)
print(ks.kruskal())

kr = Kosaraju(n, graph)
print(kr.kosaraju())

• n =ノードの総数
• start_node =希望の開始ノードの番号
• グラフ=グラフクラスのオブジェクト

GitHubリポジトリ

https://github.com/jainam2385/graphsp

ライセンス

©2022 Jainam Shah
このリポジトリは、MITライセンスの下でライセンスされています。詳細については、ライセンスを参照してください。