матрица инцидентности в матрицу смежности реберного графа

Question

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

{1 ,1, 0, 0},{1,0,1,0},{0,0,0,1},{0,1,1,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;
            cout << count2;
        
            cout << "\nMatritsa smejnosti\n";
            int SM[100][100];
            int p1, p2;
        
            for (int i = 1; i <= count2; i++) {
                for (int j = 1; j <= count2; j++) {
                    SM[i][j] = 0;
                }
            }
            cout << "\nCALC\n";
            for ( int i=1 ; i<= count2; i++) {
                for (int j=1; j <= count2; j++) {
        
                    if (I[i][j] == 1) {
        
                        for (int k = j + 1; k <= count2; k++) {
                            if (I[i][k] == 1) {
                                SM[k][j] = 1;
                        SM[j][k] = 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;
        
        
            //end
            _getch();
        }

Answer 1

По размерам исходной матрицы определяем V и E - количество вершин и рёбер (в программе почему-то подразумевается их равенство).

Далее перебираем все единичные пары по строкам (т.е. находим пары ребер, инцидентные данной вершине)

for (v = 1;v<=V;v++)
    for (e1 = 1; e1 <=E-1;e1++)
        if (I[v][e1])
             for (e2 = e1+1; e2 <=E; e2++)
                  if (I[v][e2]) {
                      AR[e1][e2] = 1;
                      AR[e2][e1] = 1;
                  }

Answer 2

Немного опередил MBo :) - пока я все комментарии расписывал. Ну, не пропадать же коду...

Раз у вас С++, лучше использовать векторы.

#include <vector>
#include <iostream>

using namespace std;

vector<vector<int>> rebuild(const vector<vector<int>>& G)
{
    size_t vxs = G[0].size(); // Количество столбцов

    // Здесь по-хорошему нужно убедиться, что
    // в каждой строке одно и то же число столбцов

    vector<vector<int>> R(vxs, vector<int>(vxs,0)); // Результат

    // Проход по строкам
    for(const auto& s: G)
    {
        vector<size_t> ix; // Собираем ненулевые значения
        for(size_t i = 0; i < s.size(); ++i)
            if (s[i]) ix.push_back(i);
        // Если их хотя бы 2...
        if (ix.size() > 1)
        {
            // Каждый с каждым - расставляем единицы
            for(size_t i = 0; i < ix.size()-1; ++i)
                for(size_t j = i+1; j < ix.size(); ++j)
                    R[ix[i]][ix[j]] = R[ix[j]][ix[i]] = 1;
        }
    }
    return R;
}

int main([[maybe_unused]] int argc,
         [[maybe_unused]] const char * argv[])
{
    vector<vector<int>> G = {{1,1,0,0},{1,0,1,1},{0,0,0,1},{0,1,1,0}};

    vector<vector<int>> R = rebuild(G);

    for(size_t i = 0; i < R.size(); ++i)
    {
        for(size_t j = 0; j < R[i].size(); ++j)
            cout << R[i][j] << "  ";
        cout << endl;
    }
}

БЛОГ НА HUSL

матрица инцидентности в матрицу смежности реберного графа

Ответы (2 шт):