Преобразование одного представления графа в другое

Помогите с алгоритмом, нигде не могу найти! Необходимо преобразовать граф из матрицы инцидентности в список смежности. Если есть алгоритм на С++ - было бы вообще здорово!

0

Список смежности - это пары вершин смежных друг с другом ?
Тогда указанный алгоритм очень простой

0

Матрица инциденций:
Это матрица B[i,j] размера n x m, где n - кол-во вершин, m - кол-во дуг.
пример:
__ a1 a2 a3
x1 1 1 0
x2 -1 0 0
x3 0 -1 0
где x1,x2,x3 - вершины графа, a1,a2,a3 - дуги между вершинами

Итак, элемент
bij = 1, если xi является начальной вершиной дуги aj
bij = -1, если xi конечная вершина дуги aj
bij = 0, если вершина xi не имеет отношения к дуге aj
================================

Матрица смежностей:
Матрица A[i,j] размера n x n, где n - кол-во вершин графа.

пример:
__a1 a2 a3
x1 0 1 1
x2 1 0 0
x3 0 1 0

где элемент
aij = 1, если есть дуга (xi,xj)
aij = 0, если нет дуги.

============================

АЛГОРИТМ:
Пусть дан грфа G(V,E), где |V| = n, |E| = m (мощность, т.е. количество вершин и количество рёбер)
Пусть дана матрица инциденций B размера n x m.
1) Создадим пустую матрицу A размера n x n (матрица смежности), все элементы которой инициализируем 0.
2) Если в матрице B элемент стоящий в i строке и j столбце = 1, то ищем в этом столбце элемент, равный -1. В итоге получаем элемент [i1, j] = 1, элемент [i2, j] = -1, а это значит, что существует дуга (Xi1,Xi2), начало которой в x1, а конец в x2, но т.к. матрица смежностий это не ориентированный грфа, нам не важно какая вершина начальная, а какая конечная.
3)Записываем в матрицу смежности A элементы A[i1, i2] = 1 и A[i2, i1] = 1.
4) Повторяем пункт 2 для следующего столбца, т.е. j+1, пока j < m (где m - количество дуг в матрице инциденций B).
5) PROFIT!

0