Способи представлення графів
Теорія
"Способи представлення графів.pptx".pptxЗапитання
Яким способом представлення заданого графа краще за все користуватися?
На це запитання можна відповісти тільки стосовно кожного конкретного алгоритму.
Звичайно, що обробляти елементи матриці суміжності нам зрозуміліше і простіше. В ній ми одразу можемо дізнатися, чи є дві задані вершини суміжними, яку «вагу» має ребро, що з'єднує дві задані вершини, тощо.
Однак, наприклад, для неорієнтованих графів, що не мають петель, матриця суміжності містить зайву інформацію, оскільки вона є симетричною.
Якщо ж у якості опису графа обрати список суміжних вершин, то значно покращується компактність представлення інформації, однак при цьому втрачається зручність її обробки.
Саме тому на самому початку ми і наголосили, що спосіб представлення графа у кожному окремому випадку обирається автором алгоритму згідно з умовою задачі та зі сформульованою метою її розв’язання.
Задача
Створіть матрицю суміжності за списком суміжних вершин зваженого графа. Дано число n - кількість вершин та m – кількість ребер. У наступних m рядках дано три числа ai, aj – номера вершин мiж якими є сполучення, та p – "вага" ребер.
n,m=map(int,input().split())
a=[]
for j in range(m):
a=a+[[int(i) for i in input().split()]]
w = [[0]*n for i in range(n)] #створюємо масив, заповнений 0
for i in range(len(a)): #присвоюємо вагу графа елементу з коефіцієнтами номерів вершин
e=a[i][0]
ee=a[i][1]
w[e-1][ee-1]=w[ee-1][e-1]=a[i][2]
for i in range (n): #виводимо матрицю суміжності
print(*w[i])