x-MU.net форум

Столкнулся с забавным клином:
как представить граф
в языках программирования. имею ввиду, что в виде масисвов или как?
перечитав пару раз я так понимаю, что речь идет о минимум двумерном массиве  m[j], где i  - вершины, j - ребра, а значения члена m[j] - отношение вершин, то есть есть ребро или нет, или же i и j это вершины, а уже значение и есть отношение между ними....

в идеале, пока писал вроде догнал. значения могут быть 0,1,-1(если ребра направлены) или я не прав?
от блин, чё я спал всю дискретную математику  (bug)
короче, те кто в курсе, объясните мне непонятливому, если не сложно.

Какой у тебя граф?
Когда я делал, то я представил его в виде матрицы смежности. Это вроде:
    x1   x2   x3   x4
x1  0       1       1       1
x2 1       0       0       1
x3  1       0       0       1
x4  1       1       1       0


Случай неориентированного графа.
x1..x4 - вершины.
1 - есть ребро.
0 - нет ребра.

Любая вершина инцидентна сама себе. Поэтому ставил 0, дабы не трогать ее в алгоритмах.

Случай с ориентированным я бы представил чуть иначе.
Обычная матрица: из нулей и единиц.

    x1   x2   x3   x4
x1  0     1     1     1
x2  1     0     0     1
x3  0     0     0     1
x4  1     0     1     0

Из x1 идут направленные ребра(далее вектора) к x2,x3,x4
но из x3 к x1 вектора нету. Вот и вся идея. Смотри как расположены нули и единици.

Мне как-то раз это помогло: матрица смежности