Матрица смежности для неориентированного графа

Матрица смежности хорошо работает для ориентированного графа, но не так хорошо для неориентированного графа, потому что в матрице есть дубликаты.

То есть при каждой вставке в граф мне приходится дважды обновлять матрицу. Есть ли способ обновить матрицу только один раз? То есть существует ли более эффективная матрица смежности для неориентированных графов.


graph adjacency-matrix
person asndonsadoasndo231213    schedule 04.04.2018    source источник
comment
Одна альтернатива состоит в том, чтобы хранить только ребра {i, j}, такие как i < j, а затем сортировать узлы каждый раз, когда вы обращаетесь к матрице смежности. Но лично я бы предпочел дублировать каждую вставку, чем иметь if/else при каждом доступе.   -  person beaker    schedule 05.04.2018
comment
Да, я думал об этом, и когда я попытался реализовать это, он стал очень глючным.   -  person asndonsadoasndo231213    schedule 05.04.2018

Ответы (1)


arrow_upward
0
arrow_downward

Если есть вес или стоимость, вы можете использовать значение веса/стоимости вместо нулей и единиц.

пример:-

1 2 1 10 5 2 5 10

person adhi .b    schedule 04.04.2018
comment
Я пытаюсь избежать обновления матрицы дважды. - person asndonsadoasndo231213; 04.04.2018
comment
обновление дважды означает присвоение значений, например {2,1} = 5 и {1,2} = 5? - person adhi .b; 04.04.2018
comment
Да, это лишнее и раздражает - person asndonsadoasndo231213; 04.04.2018
comment
даже если диаграмма является направленной, вы также должны использовать {i,j} = значение и {j,i} = значение. То же самое должно быть применено здесь, верно? - person adhi .b; 04.04.2018