Использование смежной матрицы для решения графовых задач

Question

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

Например, для моей программы у меня есть обменный курс для двух предметов.

Входные данные для построения направленногографик: 6 рубашек 15 носков Вход для построения ориентированного графа: 2 носка 1 нижнее белье

Направленный график:

рубашки - (6/15) - носки - (2/1)- нижнее белье

Таким образом, край от рубашек до носков - 6, от носков до рубашек - 15, от носков до нижнего белья - 2, от нижнего белья до носков - 1.

Входные данные для сравнения: носкирубашки Решение: 15 носков 6 рубашек

Входные данные для сравнения: нижнее белье рубашки Soltuion: 12 рубашек 15 нижнее белье

Мой вопрос: как мне представить это с помощью матрицы смежности и быть в состоянии получить ее вес?чтобы решить проблему.

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

          shirts   socks  underwear
shirts    [ 0       6     0 ]
socks     [ 15      0     2 ]
underwear [ 0       1     0 ]

Это хорошее начало?Я пытаюсь понять логику перед кодом.

Просто ищите больше информации о том, как сделать это в большем масштабе с большим количеством элементов и отдельными графиками.

Answer 1

Я дам вам основной совет о том, что такое граф смежности. Решение твоей проблемы - твоя домашняя работа, поэтому я не могу это сделать.

Представьте себе следующий график:

    A-----B
   / \   | \
  /   \  |  \
 /     \ |   \
C-------D-----E

Матрица смежности сообщает, к какому узлу графа подключен какой:

    A  B  C  D  E
A [ 0  1  1  1  0 ]
B [ 1  0  0  1  1 ]
C [ 1  0  0  1  0 ]
D [ 1  1  1  0  1 ]
E [ 0  1  0  1  0 ]

Например, запись (D, E) показывает, что D и E связаны, а (A, E) показывает, что A и E нет. Обратите внимание, что эта матрица симметрична, потому что график не ориентирован.

Если матрица имеет следующий вес:

    A--3--B
   / \   | \
  5   3  2  1
 /     \ |   \
C---2---D--7--E

тогда матрица смежности показывает, какие связаны и с каким весом (при условии, что 0 не показывает связь):

    A  B  C  D  E
A [ 0  3  5  3  0 ]
B [ 3  0  0  2  1 ]
C [ 5  0  0  2  0 ]
D [ 3  2  2  0  7 ]
E [ 0  1  0  7  0 ]

В вашем случае ваш граф - это группа узлов, имеющих ребра для группы других узлов. Ваша матрица смежности будет выглядеть очень похоже на то, что вы уже придумали, но значения могут быть неверными. Значения должны быть одинаковыми, отрицательными по отношению друг к другу или 1 по отношению к другому, в зависимости от того, каким будет ваш алгоритм.

Answer 2

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

В нем обсуждается решение проблемы графа Minimum Spanning Tree и какая из структур данных подойдет для решения проблемы. Я не уверен, что вы пытаетесь достичь с помощью вашей проблемы с графами, но это будет отправной точкой в ​​том, как вы представляете графы. Я постараюсь изменить свой ответ, если вы добавите больше информации.