Кратко въведение в теорията на графите
Втора част: внедряване на python на пълни графики
В моята предишна статия въведох три основни концепции за графите: върхове, ръбове и тегла. В тази втора част на „Кратко въведение в теорията на графите“ ще покажа реализация на пълни графики от списък с координати на върхове в Python.
Концепция
Пълната графа е конкретен граф, в който всеки връх е свързан с всеки друг връх. Както казах в предишната си статия, графиките често се представят като декартова координатна равнина. При тези условия пълният списък от координати на върховете е достатъчен, за да се създаде пълен неориентиран граф.
Нека видим как да го внедрим в Python от нулата.
Инициализация
Първо, създадох клас на Python, наречен „граф“, инициализиран с четири елемента: върхове, брой върхове, ръбове и брой ръбове.
Vertices е речник със следната структура:
върхове = {върх: (x_координатна_връх, y_координатна_върх), …}
Ключовете на речника са имената на върховете (цяло число, започващо от нула), а стойностите на речника са координатите на върховете в мястото. Този речник се инициализира като празен и ще бъде попълнен със списъка с координати на върховете във функцията „make_graph“ (вижте параграфа Създаване на графика по-долу)
Ръбовете са списък от списъци. Всеки ръбов елемент в Edges има следната структура:
ръб = [върх_x, връх_y, евклидово разстояние между двата върха]
С “n” броят на върховете ще има (n*(n-1))/2 елемента в ръбовете. Ръбовете се инициализират като празен списък и ще бъдат попълнени във функцията „make_edges“ (вижте параграф Създаване на ръбове по-долу).
Оформяне на ръбове
Тъй като всеки връх е свързан с всеки друг връх, направих двоен for цикъл, който и двата преминават през всички върхове с двойното условие, че двата върха не са равни (в пълна графика един връх не може да бъде свързан сам със себе си) и че първият връх е по-нисък от втория (цялата графа е неориентирана, така че ребро [върх_1, връх_2, разстояние] е същият ръб като [връх_2, връх_1, разстояние]).
След това получавам координатите на двата върха и използвайте формулата по-долу, за да изчислите евклидовото разстояние. преобразувано в цяло число за опростяване):
евклидово_разстояние = ( (x2-x1)² + (y2-y1)² )^(1/2)
(x1, y1) и (x2, y2) са координатите на две отделни върхове.
Забележка: в кода по-горе euclidean_distance е преобразувано като цяло число за подобряване на четливостта.
Изработване на графика
Пълен пример
За пълен пример на пълна графика можете да използвате кода по-долу и да играете с vertices_list.
В следващата си статия ще представя визуализация на пълни графики с помощта на хубава библиотека на Python: Plotly.
За мен: френски студент по науки за данните, винаги готов за нови предизвикателства. Чувствайте се свободни да ме добавите в LinkedIn, Twitter или Medium.
