π ΠΠ°ΠΊ ΡΡΡΠ°Π½ΠΎΠ²ΠΈΡΡ Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΡ graph Π² Python? π Π¨Π°Π³ Π·Π° ΡΠ°Π³ΠΎΠΌ ΡΡΠΊΠΎΠ²ΠΎΠ΄ΡΡΠ²ΠΎ
ΠΠ°ΠΊ ΡΡΡΠ°Π½ΠΎΠ²ΠΈΡΡ Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΡ graph Π² Python
ΠΠ»Ρ ΡΡΡΠ°Π½ΠΎΠ²ΠΊΠΈ Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΠΈ graph Π² Python, Π²Ρ ΠΌΠΎΠΆΠ΅ΡΠ΅ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ ΠΌΠ΅Π½Π΅Π΄ΠΆΠ΅Ρ ΠΏΠ°ΠΊΠ΅ΡΠΎΠ² pip. ΠΠΎΡ ΠΊΠ°ΠΊ ΡΡΠΎ ΠΌΠΎΠΆΠ½ΠΎ ΡΠ΄Π΅Π»Π°ΡΡ:
pip install graph
ΠΠΎΡΠ»Π΅ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ ΡΡΠΎΠΉ ΠΊΠΎΠΌΠ°Π½Π΄Ρ, Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΠ° graph Π±ΡΠ΄Π΅Ρ ΡΡΡΠ°Π½ΠΎΠ²Π»Π΅Π½Π° Π² Π²Π°ΡΠ΅ΠΉ ΡΡΠ΅Π΄Π΅ Python. Π’Π΅ΠΏΠ΅ΡΡ Π²Ρ ΠΌΠΎΠΆΠ΅ΡΠ΅ ΠΈΠΌΠΏΠΎΡΡΠΈΡΠΎΠ²Π°ΡΡ Π΅Π΅ ΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ Π΄Π»Ρ ΡΠΎΠ·Π΄Π°Π½ΠΈΡ ΠΈ ΠΌΠ°Π½ΠΈΠΏΡΠ»ΡΡΠΈΠΈ Π³ΡΠ°ΡΠ°ΠΌΠΈ.
ΠΠΎΡ ΠΏΡΠΈΠΌΠ΅Ρ ΠΊΠΎΠ΄Π°, ΠΊΠΎΡΠΎΡΡΠΉ Π΄Π΅ΠΌΠΎΠ½ΡΡΡΠΈΡΡΠ΅Ρ ΠΈΠΌΠΏΠΎΡΡΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠ΅ Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΠΈ graph:
import graph
# Π‘ΠΎΠ·Π΄Π°Π½ΠΈΠ΅ Π³ΡΠ°ΡΠ°
g = graph.Graph()
# ΠΠΎΠ±Π°Π²Π»Π΅Π½ΠΈΠ΅ Π²Π΅ΡΡΠΈΠ½
g.add_vertex("A")
g.add_vertex("B")
# ΠΠΎΠ±Π°Π²Π»Π΅Π½ΠΈΠ΅ ΡΠ΅Π±Π΅Ρ
g.add_edge("A", "B")
# ΠΠΎΠ»ΡΡΠ΅Π½ΠΈΠ΅ ΡΠΏΠΈΡΠΊΠ° Π²Π΅ΡΡΠΈΠ½
vertices = g.get_vertices()
print(vertices)
# ΠΠΎΠ»ΡΡΠ΅Π½ΠΈΠ΅ ΡΠΏΠΈΡΠΊΠ° ΡΠ΅Π±Π΅Ρ
edges = g.get_edges()
print(edges)
ΠΠ°Π΄Π΅ΡΡΡ, ΡΡΠΎ ΠΏΠΎΠΌΠΎΠ³Π°Π΅Ρ! ΠΡΠ»ΠΈ Ρ Π²Π°Ρ Π²ΠΎΠ·Π½ΠΈΠΊΠ½ΡΡ Π΅ΡΠ΅ Π²ΠΎΠΏΡΠΎΡΡ, Π½Π΅ ΡΡΠ΅ΡΠ½ΡΠΉΡΠ΅ΡΡ Π·Π°Π΄Π°Π²Π°ΡΡ.
ΠΠ΅ΡΠ°Π»ΡΠ½ΡΠΉ ΠΎΡΠ²Π΅Ρ
ΠΠ°ΠΊ ΡΡΡΠ°Π½ΠΎΠ²ΠΈΡΡ Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΡ graph Π² python
Π£ΡΡΠ°Π½ΠΎΠ²ΠΊΠ° Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΠΈ Graph Π² Python ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ Π²Π°ΠΆΠ½ΡΠΌ ΡΠ°Π³ΠΎΠΌ Π΄Π»Ρ ΡΠ°Π±ΠΎΡΡ Ρ Π³ΡΠ°ΡΠΎΠ²ΡΠΌΠΈ ΡΡΡΡΠΊΡΡΡΠ°ΠΌΠΈ ΠΈ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°ΠΌΠΈ. Π ΡΡΠΎΠΉ ΡΡΠ°ΡΡΠ΅ ΠΌΡ ΡΠ°ΡΡΠΌΠΎΡΡΠΈΠΌ, ΠΊΠ°ΠΊ ΡΡΡΠ°Π½ΠΎΠ²ΠΈΡΡ ΡΡΡ Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΡ ΠΈ Π½Π°ΡΠ°ΡΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ Π΅Π΅ Π² ΡΠ²ΠΎΠΈΡ ΠΏΡΠΎΠ΅ΠΊΡΠ°Ρ .
Π¨Π°Π³ 1: Π£ΡΡΠ°Π½ΠΎΠ²ΠΊΠ° Python
ΠΠ΅ΡΠ΅Π΄ ΡΠ΅ΠΌ ΠΊΠ°ΠΊ Π½Π°ΡΠ°ΡΡ ΡΡΡΠ°Π½Π°Π²Π»ΠΈΠ²Π°ΡΡ Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΡ Graph, ΡΠ±Π΅Π΄ΠΈΡΠ΅ΡΡ, ΡΡΠΎ Ρ Π²Π°Ρ ΡΡΡΠ°Π½ΠΎΠ²Π»Π΅Π½ Python Π½Π° Π²Π°ΡΠ΅ΠΌ ΠΊΠΎΠΌΠΏΡΡΡΠ΅ΡΠ΅. ΠΡ ΠΌΠΎΠΆΠ΅ΡΠ΅ ΡΠΊΠ°ΡΠ°ΡΡ ΠΈ ΡΡΡΠ°Π½ΠΎΠ²ΠΈΡΡ ΠΏΠΎΡΠ»Π΅Π΄Π½ΡΡ Π²Π΅ΡΡΠΈΡ Python Ρ ΠΎΡΠΈΡΠΈΠ°Π»ΡΠ½ΠΎΠ³ΠΎ Π²Π΅Π±-ΡΠ°ΠΉΡΠ° Python.
Π¨Π°Π³ 2: Π£ΡΡΠ°Π½ΠΎΠ²ΠΊΠ° pip
ΠΠ°ΠΊΠ΅ΡΠ½ΡΠΉ ΠΌΠ΅Π½Π΅Π΄ΠΆΠ΅Ρ pip ΠΏΠΎΠΌΠΎΠΆΠ΅Ρ Π½Π°ΠΌ ΡΡΡΠ°Π½ΠΎΠ²ΠΈΡΡ Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΡ Graph. Π£ΠΊΠ°ΠΆΠΈΡΠ΅ Π² ΡΠ΅ΡΠΌΠΈΠ½Π°Π»Π΅ ΡΠ»Π΅Π΄ΡΡΡΡΡ ΠΊΠΎΠΌΠ°Π½Π΄Ρ Π΄Π»Ρ ΡΡΡΠ°Π½ΠΎΠ²ΠΊΠΈ pip, Π΅ΡΠ»ΠΈ Ρ Π²Π°Ρ Π΅ΡΠ΅ Π½Π΅Ρ:
python -m ensurepip --default-pip
ΠΠ²Π΅Π΄ΠΈΡΠ΅ Π²Π°Ρ ΠΏΠ°ΡΠΎΠ»Ρ Π°Π΄ΠΌΠΈΠ½ΠΈΡΡΡΠ°ΡΠΎΡΠ°, Π΅ΡΠ»ΠΈ Π²Π°ΠΌ ΠΏΠΎΡΡΠ΅Π±ΡΠ΅ΡΡΡ ΡΠ°Π·ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ Π΄Π»Ρ ΡΡΡΠ°Π½ΠΎΠ²ΠΊΠΈ ΠΏΠ°ΠΊΠ΅ΡΠ° pip.
Π¨Π°Π³ 3: Π£ΡΡΠ°Π½ΠΎΠ²ΠΊΠ° Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΠΈ Graph
Π’Π΅ΠΏΠ΅ΡΡ Ρ Π½Π°Ρ Π΅ΡΡΡ pip, ΡΠ°ΠΊ ΡΡΠΎ ΠΌΡ ΠΌΠΎΠΆΠ΅ΠΌ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ Π΅Π³ΠΎ Π΄Π»Ρ ΡΡΡΠ°Π½ΠΎΠ²ΠΊΠΈ Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΠΈ Graph. ΠΠΊΡΠΈΠ²ΠΈΡΡΠΉΡΠ΅ ΡΠ²ΠΎΡ ΠΊΠΎΠΌΠ°Π½Π΄Π½ΡΡ ΡΡΡΠΎΠΊΡ ΠΈ Π²Π²Π΅Π΄ΠΈΡΠ΅ ΡΠ»Π΅Π΄ΡΡΡΡΡ ΠΊΠΎΠΌΠ°Π½Π΄Ρ:
pip install graph
ΠΠΎ Π·Π°Π²Π΅ΡΡΠ΅Π½ΠΈΠΈ ΡΡΡΠ°Π½ΠΎΠ²ΠΊΠΈ Π²Ρ Π΄ΠΎΠ»ΠΆΠ½Ρ ΡΠ²ΠΈΠ΄Π΅ΡΡ ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΈΠ΅ ΠΎ ΡΡΠΏΠ΅ΡΠ½ΠΎΠΉ ΡΡΡΠ°Π½ΠΎΠ²ΠΊΠ΅.
Π¨Π°Π³ 4: ΠΠΌΠΏΠΎΡΡ ΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠ΅ Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΠΈ Graph
Π’Π΅ΠΏΠ΅ΡΡ, ΠΊΠΎΠ³Π΄Π° Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΠ° Graph ΡΡΡΠ°Π½ΠΎΠ²Π»Π΅Π½Π°, ΠΌΡ ΠΌΠΎΠΆΠ΅ΠΌ Π½Π°ΡΠ°ΡΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ Π΅Π΅ Π² Π½Π°ΡΠΈΡ ΠΏΡΠΎΠ΅ΠΊΡΠ°Ρ Python. ΠΠ»Ρ Π½Π°ΡΠ°Π»Π°, Π΄Π°Π²Π°ΠΉΡΠ΅ ΠΈΠΌΠΏΠΎΡΡΠΈΡΡΠ΅ΠΌ Π΅Π΅ Π² Π½Π°ΡΠ΅ΠΌ ΠΊΠΎΠ΄Π΅:
import graph
Π’Π΅ΠΏΠ΅ΡΡ Π²Ρ ΠΌΠΎΠΆΠ΅ΡΠ΅ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ ΡΡΠ½ΠΊΡΠΈΠΈ ΠΈ ΠΊΠ»Π°ΡΡΡ ΠΈΠ· Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΠΈ Graph Π² ΡΠ²ΠΎΠ΅ΠΌ ΠΊΠΎΠ΄Π΅. ΠΠ°ΠΏΡΠΈΠΌΠ΅Ρ, Π΄Π°Π²Π°ΠΉΡΠ΅ ΡΠΎΠ·Π΄Π°Π΄ΠΈΠΌ ΠΏΡΠΎΡΡΠΎΠΉ Π³ΡΠ°Ρ:
g = graph.Graph()
ΠΠΎΡΠ»Π΅ ΡΠΎΠ·Π΄Π°Π½ΠΈΡ Π³ΡΠ°ΡΠ°, Π²Ρ ΠΌΠΎΠΆΠ΅ΡΠ΅ Π΄ΠΎΠ±Π°Π²ΠΈΡΡ Π²Π΅ΡΡΠΈΠ½Ρ ΠΈ ΡΠ΅Π±ΡΠ°:
g.add_vertex('A')
g.add_vertex('B')
g.add_vertex('C')
g.add_edge('A', 'B')
g.add_edge('B', 'C')
ΠΡ ΡΠ°ΠΊΠΆΠ΅ ΠΌΠΎΠΆΠ΅ΡΠ΅ Π²ΡΠΏΠΎΠ»Π½ΠΈΡΡ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ Π½Π° Π³ΡΠ°ΡΠ΅, ΡΠ°ΠΊΠΈΠ΅ ΠΊΠ°ΠΊ ΠΏΠΎΠΈΡΠΊ ΠΏΡΡΠΈ ΠΈΠ»ΠΈ Π½Π°Ρ ΠΎΠΆΠ΄Π΅Π½ΠΈΠ΅ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠ΅Π³ΠΎ ΠΏΡΡΠΈ:
path = g.find_path('A', 'C')
shortest_path = g.shortest_path('A', 'C')
ΠΡΠΎ Π»ΠΈΡΡ ΠΏΡΠΈΠΌΠ΅ΡΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΡ Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΠΈ Graph. ΠΡ ΠΌΠΎΠΆΠ΅ΡΠ΅ ΠΈΠ·ΡΡΠΈΡΡ Π΅Π΅ Π΄ΠΎΠΊΡΠΌΠ΅Π½ΡΠ°ΡΠΈΡ ΠΈ Π½Π°ΠΉΡΠΈ Π±ΠΎΠ»ΡΡΠ΅ ΡΡΠ½ΠΊΡΠΈΠΉ ΠΈ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡΠ΅ΠΉ Π΄Π»Ρ ΡΠ²ΠΎΠΈΡ ΠΏΡΠΎΠ΅ΠΊΡΠΎΠ².
ΠΠ°ΠΊΠ»ΡΡΠ΅Π½ΠΈΠ΅
Π£ΡΡΠ°Π½ΠΎΠ²ΠΊΠ° Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΠΈ Graph Π² Python ΠΏΠΎΠ·Π²ΠΎΠ»ΡΠ΅Ρ Π½Π°ΠΌ ΡΠ°Π±ΠΎΡΠ°ΡΡ Ρ Π³ΡΠ°ΡΠΎΠ²ΡΠΌΠΈ ΡΡΡΡΠΊΡΡΡΠ°ΠΌΠΈ ΠΈ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°ΠΌΠΈ. Π ΡΡΠΎΠΉ ΡΡΠ°ΡΡΠ΅ ΠΌΡ ΡΠ°ΡΡΠΌΠΎΡΡΠ΅Π»ΠΈ ΡΠ°Π³ΠΈ ΠΏΠΎ ΡΡΡΠ°Π½ΠΎΠ²ΠΊΠ΅ ΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΡ ΡΡΠΎΠΉ Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΠΈ. Π’Π΅ΠΏΠ΅ΡΡ Ρ Π²Π°Ρ Π΅ΡΡΡ ΠΎΡΠ½ΠΎΠ²Π½ΡΠ΅ Π·Π½Π°Π½ΠΈΡ ΠΎ ΡΠΎΠΌ, ΠΊΠ°ΠΊ Π½Π°ΡΠ°ΡΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΡ Graph Π² ΡΠ²ΠΎΠΈΡ ΠΏΡΠΎΠ΅ΠΊΡΠ°Ρ .
ΠΠ°ΡΠ»Π°ΠΆΠ΄Π°ΠΉΡΠ΅ΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ΠΌ Ρ Π³ΡΠ°ΡΠ°ΠΌΠΈ!