матрица связности в графах

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

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

Зависит от задачи и самого графа. Матрица смежности хороша, если она dense.

Дык это.

Храни в массиве чиселки. m[i,j] == 0 - между вершинами i и j нет связи. 1 - есть от i к j, (1 <<1) - есть от j к i, (1 << 1 | 1) - есть туда-обратно. Размер массива n*n.

если у нас ориентированный граф с n вершин, то для описания связей можно использовать массив n * n, в котором если элемент массива 3 - 4 единица, значит в графе есть связь 3 -> 4, если в массиве элемент 4 - 3 единица, значит есть связь 4 -> 3, если в массиве элемент 3 - 3 единица, значит есть связь 3 <-> 3, теперь неориентированный граф, если в массиве елементы 4 - 3 и 3 - 4 единица, значит есть связь 3 - 4, если в массиве элемент 3 - 4 единица, а 4 - 3 ноль, значит массив испорчен, тоже самое если 3 - 3 единица. В общем для описания связей неориентированного графа нам нужна половина матрицы без основной диагонили, значит нам нужно памяти (n * n / 2 - n / 2). Теперь вопрос, как адресовать связи в таком массиве?

в том-то и дело, что если граф не ориентированный, то памяти надо не n * n, а (n * n / 2 - n / 2), то есть пол матрицы без главной диагонали, собственно вопрос, как в таком массиве адресовать связи (y * n + x) разумеется выход за пределы массива

Сделать одномерный массив и делать доступ к элементу через минимальный параметр? Правда там получится (н*н)/2 + н

А что у тебя проблема с размером данных? Реально сильно много получается?

нет, прсто стало интересно.

Ну тогда нарисуй эту лесенку. Прогрессию видишь? Тоесть если тебе нужно 5,6 то идешь на «строку» 6 и прибавляешь 5 это и будет твой элемент. Надеюсь не нужно объяснять как сумму прогрессии искать?

// пишу с телефона. Не удобнонах

А. Криво прочитал сообщение.

Ну, наша диагональная матрица тогда может быть поделена на квадрат со сторонами {n/2,n/2}, и два равнобедренных треугольника:

        <------ (n) ------->
              n/2      n/2
     {  +------------+-----+
     {  |            |  2 /|
     {  |            |   / |
n/2  {  |      1     |  /  |
     {  |            | /   |
     {  |            |/  3 |
     {  +------------+-----+

Тут тоже всё просто тогда - если надо проверить связь между вершинами i и j, то

• i < n/2, j < n/2 - просто смотрим в элемент m[j*n + i]
• i > n/2, j < n/2 - смотрим в элемент m[j*n + i + n/2]
• i < n/2, j > n/2 - смотрим в элемент m[(n - j)*n + i]
• i > n/2, j > n/2 - по логике выше проверяем точку (n-i, n-j)

Вроде так, может можно изящнее записать, или умнее. Проверь индексы с интервалами

Ну вот, анонимус выше написал про прогрессию, может так действительно будет лучше :)

Ты сложно думаешь слишком. Это в 4 строчки делается без лапши из условий.

В чем тайный смысл писать графы на сях? Инструмент так-то не очень для таких вещей. Взял бы яву или плюсы если совсем плохо.

Пргнал. Там -н. Итого 1-> 0 элементов , длина 0

2-> 1 элемент, длина 1

3-> 2 элемента, длина 3

Итд

Да, действительно. Смещение относительно начала можно считать как сумму элементов убывающей прогрессии (i) + j, где i - максимальный, j - минимальный индексы из проверяемой пары.

В чем тайный смысл залезть в тему про алгоритмы/язык С и искать какой-то тайный смысл?

И где там вообще про си? У тебя ява чешется? Это на сайт к малышевой

Смысл искать тайный смысл в теме про аглоритмы и си в том, чтобы пинком направить ТСа в сторону более подходящих для написания алгоритмов языков, ато он бедненький мучается с сишечкой.

узбагойся, анонимуз

*(3 * n + 4), то получим выход за пределы массива

вот тут про си

дошло, спасибо.

да, просто и со вкусом, жаль, я не догадался

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

А можно еще сделать массив массивов разной длины и сортировать индексы.

да у меня там битовая карта вообще-то :)

напиши простейшую пару функций. row(x,y)==treygolnoe(max(x,y)-1); col(x,y)==min(x,y)-1;

тогда ребро между x,y находится по индексу row(x,y)+col(x,y)

man триугольные числа

циклом ?!

Лунным или женским?

ну выдели n*n памяти, но НЕ инициализируй её всю, а только нужное.

		t1 = row, t2 = col;
		row = min(t1, t2);
		col = max(t1, t2);
		row = ((2 * (n - 1)) + (-1 * (row - 1))) / 2 * row;
		col = col - (row + 1);
		xy = row + col;

вроде работает, не проверял правда

В чем проблема?

def t_idx(i1, i2, N):
    if i1 > i2:
        i1, i2 = i2, i1
    return i1 * N - i1 * (i1 + 1) / 2 - i1 + i2 - 1

чито такое эн?

тут у тя лишнее n (если нет петель то нужно из «большой базы» вычитать в оканцове входное значение (шоб не тратить место на главную диагональ)- ну и контролировать вход (a,a)иначе для 1 будет -1 , а для a>1 чтение (a-1,a-2) что не то что тебе нужно)

row=max(x,y)-1;  
col=mix(x,y)-1;

//т.е plaine_mem[0] это "matrix(1,2)"

triasum=row*(row-1)/2-row;

return plaine_mem[triasim+col];

количество вершин в графе

ну не нужно N от слова вообще

оно нужно только для выделения общего места

при вычислении у тя по сути свёрнутый треугольник от кратчайших (длиной 0 для первой вершины и длиной k-1 для вершины k рёбер между k и вершинами меньшего номера.

вход контролирую, если x == y, то ошибка.

не работает

хм +- там проверить надо.

кинь тесты и ожидаемые результаты.

ну и сырец в студию:

(-1 * (row - 1))

facepalm