Как прочитать этот ввод графа и поместить в матрицу смежности?

Я запутался и пытаюсь понять, как поместить эти данные графика в матрицу смежности.

Это пример ввода из текстового файла:

0 1,28 3,33
1 2,10 4,44
2 3,50
3 4,30
4

Вот так должна выглядеть матрица

  0   1   2   3   4
0 INF 28  INF 33  INF
1 28  INF 10  INF 44 
2 INF 10  INF 50  INF 
3 33  INF 50  30  INF  
4 INF 44  INF INF INF

Это был бы какой-то многомерный массив, но я не знаю, как перевести ввод в один. Любая помощь будет оценена по достоинству.

Я работаю в питоне.

Спасибо!


python graph matrix adjacency-matrix floyd-warshall
person Brejuro    schedule 18.08.2014    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Это довольно прямолинейно,

для ввода x x1,y1 x2,y2

это означает, что

есть ребро между x и x1 со значением y1 и ребро x и x2 со значением y2.

Чтобы разобрать его, сделайте следующее

1: используйте разделитель пробела для разделения набора данных.
2: первый элемент в результирующем массиве – это ваш узел (x).
3: для i (от 1 до n) разделите запятую(, ), который даст массив из двух элементов, где первый элемент будет узлом (x1), а второй — расстоянием y (1).
4: Чтобы установить значение в матрице для каждой пары, mat[x,x1] =y1

Редактировать Похоже, ваш график является неориентированным графом. Итак, для каждой пары вы должны сделать

мат[x,x1]=y1
мат[x1,x]=y1

person Dude    schedule 18.08.2014