О матрице ребра в графе с использованием Stack Overflow
Я путаю, как определить программу, которая найдет матрицу ребер в графе.
Проблема в том, что если ввести значение матрицы смежности, которая дает информацию о соединении вершин в графе, например: есть 3 вершины, то V1 соединен с V2, но не с V3, а затем V2 соединен с V3, это дает:
0 1 0
1 0 1
0 1 0
Теперь, с этой информацией, я хочу сделать программу, которая находит соединение ребра к ребру, например, есть 3 ребра: 1-2 ребра, 2-3 ребра, и его вывод:
0 1
1 0
Я знаю, чтобы сделать первый вывод «Матрица смежности», но второй.
Заранее спасибо.
Решение
Матрица смежности используется для представления графа, что означает, что в нем есть как вершины, так и ребра. Так что, если вход:
0 1 1
1 0 1
1 1 0
Это означает, что ваш график завершен. Если вы читаете это с нанесением чисел на матрицу:
X 1 2 3
1 0 1 1
2 1 0 1
3 1 1 0
Ты это видишь:
V1 подключается к V2 и V3
V2 подключается к V1 и V3
V3 подключается к V1 и V2
Читая строку n, вы видите, какая вершина Vn соединяется с, а читая столбец n, вы можете видеть, какие вершины связаны с Vn.
В вашем примере ваш график не ориентирован, потому что ваша матрица диагональна.
Если ваша цель — найти грани вашего графа, у вас уже есть информация в матрице смежности. Если вы хотите увидеть, какие вершины являются «двойными связями», вам нужно найти, если для вершин Vi и Vj члены M [i] [j] и M [j] [i] вашей матрицы имеют значение 1 (It всегда имеет место в неориентированном графе). Возможный алгоритм для этого — просто двойной цикл в вашем матричном представлении (обычно два вектора / списки / массивы).
Другие решения
Других решений пока нет …