2

необходимо переделать из матрицы инцидентности в матрицу смежности реберного графа. для не разбирающихся в графах алгоритм в общем-то таков: необходимо в первой матрице в каждой строке найти все элементы со значением 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();
        }

2 ответа 2

5

По размерам исходной матрицы определяем 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;
                  }
5
  • так это если просто матрица смежности графа, а мне нужна матрица смежности реберного графа
    – Igor
    26 сен 2020 в 20:57
  • Угу, понял. Исправляем.
    – MBo
    27 сен 2020 в 5:39
  • все отлично, только почему-то не заполняет элементы в последнем столбце и строчке
    – Igor
    27 сен 2020 в 8:07
  • Может быть, путаница, потому что я использовал в коде вашу нумерацию с единицы, а исходные данные всё-таки с нуля?
    – MBo
    28 сен 2020 в 17:33
  • @MBo у вас код написан правильно, просто у автор не правильно создал матрицу инцидентности
    – Danis
    28 сен 2020 в 19:12
3

Немного опередил 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;
    }
}

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.