2

Подскажите пожалуйста, почему когда я составляю матрицу смежности реберного графа из матрицы инцидентности в ней последняя строка и последний столбец остаются заполненные 0? В чем ошибка? Ввожу ребра 12,23,34,45,15,24 что должно быть

  struct EdgeArray {
    int x=0;
    int y=0;
};
int main()
{
    int Graph[100][100], Vertex, Edge, x, y;
    EdgeArray mass[100];
    int Incidence[100][100];
    cout << "Enter number of vertexes:";
    cin >> Vertex;
    cout << "\nEnter number of edges:";
    cin >> Edge;
    //FILL NULL Adjacency matrix
    for (int i = 0; i < Vertex; i++)
        for (int j = 0; j < Vertex; j++)
        {
            Graph[i][j] = 0;
        }
    //FILL NULL Incidence Matrix
    for (int i = 0; i < Edge; i++)
        for (int j = 0; j < Vertex; j++)
        {
            Incidence[i][j] = 0;
        }
    //INPUT EDGES
    cout << "\nEnter edges:\n " << endl;
    for (int i = 0; i < Edge; i++)
    {
        cout << "e1=";
        cin >> x;
        cout << "e2=";
        cin >> y;
        cout << endl;
        Graph[x][y] = 1;
        Graph[y][x] = 1;

        mass[i].x =x ; // struct massive input data
        mass[i].y =y ;
    }
    //OUTPUT
    cout << "\nAdjacency matrix:\n" << endl;
    for (int i = 0; i < Vertex; i++)
    {
        for (int j = 0; j <Vertex; j++)
        {
            cout <<"  "<< Graph[i][j];
        }
        cout << endl;
    }
    cout << endl;
    //

    for (int i = 0; i < Edge; i++) {
        Incidence[i][mass[i].x] = 1; // incidence matrix
        Incidence[i][mass[i].y] = 1;
 }


    //OUTPUT
    cout << "\nIncidence Matrix:\n" << endl;
    int count = 0;
    for (int j = 0; j < Vertex; j++)
    {
        for (int i = 0; i < Edge; i++)
        {
            cout << "  " << Incidence[i][j];
        }
        cout << endl;
    }
    //
    cout << endl;
    cout << "\nAdjacency matrix of Edge Graph:\n";
    int AR[100][100];
    for (int v = 0;v<Vertex;v++)
    for (x = 0; x <Vertex;x++)
        if (Incidence[v][x])
             for (y =x+1; y <Edge; y++)
                  if (Incidence[v][y]) {
                      AR[x][y] = 1;
                      AR[y][x] = 1;
                  }
    for (int v = 1; v < Edge; v++)
    {
        for (int j = 0; j < Edge; j++)
        {
            cout << "  " << AR[v][j];
        }
        cout << endl;
    }
}

результат

4
  • в циклах условие окончания неверное...
    – Fat-Zer
    27 сен 2020 в 17:00
  • в смысле? можно поподробнее?
    – Igor
    27 сен 2020 в 17:04
  • в Си индексы масивов начинаются от нуля и идут до N-1, так что циклы обычно имеют вид for (x = 0; x <Vertex;x++)... всё остальное — расточительно или чертовски подозрительно... Но это не основная ошибка... по сути у тебя матрица инцидентности транспонированная: по строкам там рёбра, а по столбцам — вершины (Си/C++ это не фортран — тут матрицы традиционно — это массив векторов-строк). при выводе ты это учитываешь, а при работе с ней — нет... ну и цикл ` for (int v = 1;v<=Edge;v++)` судя по именам должен быть по вершинам, а не по рёбрам...
    – Fat-Zer
    28 сен 2020 в 1:25
  • я в упор не понимаю, вроде поменял в проге, а результат тот же
    – Igor
    28 сен 2020 в 5:03

1 ответ 1

0

я решил полностью переписать код:

int main(int argc, char *argv[])
{
    int Vertex, Edge;
    cout << "Vertex: ";
    cin >> Vertex;
    cout << "Edge: ";
    cin >> Edge;
    
    int Graph[Vertex][Vertex];
    int Incidence[Vertex][Edge];
    int AR[Edge][Edge];
    int mass[Edge][2];
    
    for (int i = 0; i < Vertex; i++){
        for (int j = 0; j < Vertex; j++){
            Graph[i][j] = 0;
        }
    }
    
    for (int i = 0; i < Vertex; i++){
        for (int j = 0; j < Edge; j++){
            Incidence[i][j] = 0;
        }
    }
    
    for (int i = 0; i < Edge; i++){
        for (int j = 0; j < Edge; j++){
            AR[i][j] = 0;
        }
    }
    
    int x, y;
    for (int i = 0; i < Edge; i++){
        cout << "e1=";
        cin >> x;
        cout << "e2=";
        cin >> y;
        cout << endl;
        Graph[x - 1][y - 1] = 1;
        Graph[y - 1][x - 1] = 1;
        mass[i][0] = x - 1;
        mass[i][1] = y - 1;
    }
    
    for (int i = 0; i < Edge; i++){
        Incidence[mass[i][0]][i] = 1;
        Incidence[mass[i][1]][i] = 1;
    }
    
    for (int v = 0; v < Vertex; v++){
        for (int e0 = 0; e0 < Edge; e0++){
            if (Incidence[v][e0]){
                for(int e1 = e0 + 1; e1 < Edge; e1++){
                    if (Incidence[v][e1]){
                        AR[e0][e1] = 1;
                        AR[e1][e0] = 1;
                    }
                }
            }
        }
    }
    
    cout << "\nAdjacency matrix:\n" << endl;
    for (int i = 0; i < Vertex; i++){
        for (int j = 0; j < Vertex; j++){
            cout << " " << Graph[i][j];
        }
        cout << endl;
    }
    
    cout << "\nIncidence:\n" << endl;
    for (int i = 0; i < Vertex; i++){
        for (int j = 0; j < Edge; j++){
            cout << " " << Incidence[i][j];
        }
        cout << endl;
    }
    cout << "\nAdjacency matrix of Edge Graph:\n" << endl;
    for (int i = 0; i < Edge; i++){
        for (int j = 0; j < Edge; j++){
            cout << " " << AR[i][j];
        }
        cout << endl;
    }
}

И в самом конце я нашел ошибку в вашем коде, во время создания матрицы инцидентности место

for (int i = 0; i < Edge; i++) {
        Incidence[i][mass[i].x] = 1; // incidence matrix
        Incidence[i][mass[i].y] = 1;
 }

надо было писать

for (int i = 0; i < Edge; i++) {
        Incidence[mass[i].x][i] = 1; // incidence matrix
        Incidence[mass[i].y][i] = 1;
 }

Ваш ответ

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

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