Алгоритм Как преобразовать список ребер в матрицу смежности в C ++ с количеством ребер, соединенных с вершиной вместо единиц?

Question

Алгоритм Как преобразовать список ребер в матрицу смежности в C ++ с количеством ребер, соединенных с вершиной вместо единиц?

Я изо всех сил пытаюсь преобразовать список ребер в матрицу смежности определенным требуемым способом.

Проблема:

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

вход

4 7
1 2
2 3
3 2
2 4
4 1
4 2
3 2
Где 4 — количество вершин, 7 — количество ребер, и каждая линия представляет ребра.

Выход:

4
0 1 0 1
1 0 3 2
0 3 0 0
1 2 0 0
Где 4 — это число вершин, и каждая строка показывает, сколько раз вершина связана.

В моем коде мне удалось преобразовать только в нормальную матрицу смежности с 1 с, но я не могу понять, могу ли я решить эту задачу только с массивами и как?
Вот мой код:

#include <iostream>

using namespace std;

int main()
{
int adjMatrix[100][100] = { };
int edgeList[100][100];
int row, col;
int N, M;

cin >> N;
cin >> M;

for (int i = 0; i < 100; i++)
{
for (int j = 0; j < 100; j++)
{
adjMatrix[i][j] = 0;
}
}

for (int i = 1; i < 8; i++)
{
for (int j = 1; j <= 2; j++)
{
cin >> row;
cin >> col;
adjMatrix[row][col] = 1;
adjMatrix[col][row] = 1;

}
}

for (int i = 1; i < 8; i++)
{
for (int j = 1; j <= 2; j++)
{
if (adjMatrix[i][j] == adjMatrix[j][i])
{
adjMatrix[i][j]++;
}

}
}
cout << N << endl;

for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
cout << adjMatrix[i][j] << " ";

}
cout << endl;
}
return 0;
}

-2

algorithm c++edges graph-theory matrix

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Проблема: нужно количество соединений, а не просто то, что соединение существует.

Решение: использовать ++

adjMatrix[row][col]++;
adjMatrix[col][row]++;

Стоит отметить, что

Этот цикл

for (int i = 0; i < 100; i++)
{
for (int j = 0; j < 100; j++)
{
adjMatrix[i][j] = 0;
}
}

Становится избыточным

int adjMatrix[100][100] = { };

поскольку = {} default инициализирует массив, устанавливая все элементы в 0.

Кроме того, что если N больше 100, используемого для определения размеров массива? adjMatrix должен быть динамичным. Читайте дальше и используйте std::vector

Следующие условия цикла неверны

    for (int i = 1; i < 8; i++)
{
for (int j = 1; j <= 2; j++)
{
cin >> row;
cin >> col;
adjMatrix[row][col] = 1;
adjMatrix[col][row] = 1;
}
}

14 строк ВСЕГДА будут считываться из файла независимо от размера файла. Внешний цикл всегда будет выполняться 7 раз (1..7), а внутренний цикл — всегда дважды (1..2).

M определяет количество строк в файле. Используйте это, чтобы контролировать свой цикл.

Это фиксированное количество строк особенно плохо, если в файле меньше 14 строк, потому что cin >> не проходят проверку на валидность. Код может загружать матрицу с мусором, и вы никогда не узнаете. Вместо этого используйте что-то вроде

if (cin >> row >> col)
{
do stuff
}
else
{
handle error
}

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

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

for (int i = 1; i < 8; i++)
{
for (int j = 1; j <= 2; j++)
{
if (adjMatrix[i][j] == adjMatrix[j][i])
{
adjMatrix[i][j]++;
}

}
}

1