Как разработать процедуры преобразования видов хранения графов с выдачей результатов на дисплей?
У нас есть 3 вида хранения графов: матрица инцидентности, смежности и список. Нужно реализовать переход из любой матрицы в любую (желательно без выделения памяти в случае C++, но разницы на каком языке будет реализована процедура - нет). Проблема заключается именно в принципе перехода от одного к другому :( В примере кода переход от матрицы инцидентности к матрице смежности
#include <iostream>
#define V 4
#define E 4
using namespace std;
int main()
{
int I[V][E] = { {1, 1, 0, 0}, { 1,0,1,0 }, { 0,0,0,1 }, { 0,1,1,0 } };
int count = 0;
for (int j = 1; j <= V; j++)
{
for (int i = 1; i <= V; i++)
{
if (I[i][j] == 1) {
count += 1;
}
}
}
int count2 = count / 2;
int SM[100][100];
for (int i = 1; i <= count2; i++) {
for (int j = 1; j <= count2; j++) {
SM[i][j] = 0;
}
}
for (int v = 1; v <= V; v++)
for (int e1 = 1; e1 <= E - 1; e1++)
if (I[v][e1])
for (int e2 = e1 + 1; e2 <= E; e2++)
if (I[v][e2]) {
SM[e1][e2] = 1;
SM[e2][e1] = 1;
}
//_________________________OUTPUT
cout << "\nSM matrix:\n" << endl;
for (int j = 1; j <= count2; j++)
{
for (int i = 1; i <= count2; i++)
{
cout << " " << SM[i][j];
}
cout << endl;
}
cout << endl;
}
Ответы (1 шт):
Ну так вроде вы понимаете, что нужно делать. Только почему нумерация с единицы?
Для создания матрицы инцидентности I из матрицы смежности A для начала нужно посчитать единички в A и разделить пополам - это будет число рёбер, число столбцов в I. Далее заводите счётчик рёбер CE, обходите половину А выше диагонали, и для A[i][j]==1 ставите единички в паре I[i][CE], I[j][CE++]
Для списка L в A: поставьте единицы в те ячейки i-й строки А, номера которых которых присутствуют в списке смежности для i-го элемента (L[i]).
Для L в I: как и раньше, посчитайте общее количество, пополам, сделайте I. Затем в i-м списке берутся только элементы j, большие, чем i, и ставите единички в паре I[i][CE], I[j][CE++]
A или I в списки вроде нетрудно перевести, да?