Граф. Матрица инцидентности

@Triglav86 · Регистрация: 13.06.2019

Студворк — интернет-сервис помощи студентам

Вопрос:
Каким образом передать данные из файла matrix.txt в функцию обхода в глубину ?

Задание :

Кликните здесь для просмотра всего текста

Используя метод поиска в глубину, в неориентированном графе(рёбра), найти и вывести все вершины, достижимые из заданной. Номер начальной вершины ввести с клавиатуры. Граф задать в текстовом файле матрицей инциденций. Достижимые вершины выводить в порядке их посещения.

Код, граф которого задан массивом( требуется в текстовом файле ):

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
 
using namespace std;
 
const int n = 4; 
const int m = 5; 
 
int iArr[n][m] = 
{ 1, 1, 0, 0, 0,
1, 0, 1, 1, 0,
0, 0, 0, 1, 1,
0, 1, 1, 0, 1 };
 
bool used[n]; 
 
int j, r, i, k = 0;
 
void dfs(int t) { //Обход в глубину графа, представленного матрицей инцидентности
 
    used[t] = true; 
    
    int p;
            
    for (i = k; i < n; i++)
    {
        j = r;
        if ((iArr[i][j] != 0) && (!used[i]))
        {
            used[i] = true;
            p = i;
 
            cout << i << " ";           
 
            for (j = 0; j < m; j++)
            {
                i == p;
                if (iArr[i][j] != 0)
                {
                    r = j;
                
                    for (k = 0; k < n; k++)
                    {
                        j == r;
                
                        if ((iArr[k][j] != 0) && (!used[k]))
                        {                           
                            dfs(i);                         
                        }
                    }
                }
            }
        }
    }
}
 
int main()
{
    for (int i = 0; i < n; i++)
    {
        used[i] = false;
        for (int j = 0; j < m; j++)
            cout << " " << iArr[i][j];
        cout << endl;
    }
 
    int from;
    cout << "From >> "; 
    cin >> from;
    
    cout << "Order: " << endl;
        
    dfs(from);                  
 
    cout << endl;
 
    return 0;
}

Считываем данные из matrix.txt
Так же есть такая часть кода, которую предполагаю лучше засунуть в main и ...

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void graph() {
    ifstream in("matrix.txt");
    int m, n;
    in >> m;
    in >> n;
    // выделяем память под M строк для матрицы инцидентности 
    int **incidenceMatrix = new int*[m];
    for (int row = 0; row < m; row++)
    {
        // для каждой строки выделяем память под N элементов
        incidenceMatrix[row] = new int[n];
        // считываем значения
        for (int column = 0; column < n; column++) {
            in >> incidenceMatrix[row][column];
            cout << incidenceMatrix[row][column] << " ";
        }
        cout << endl;
    }
    in.close();
}

и передать его в .. dfs? Не знаю что дальше делать. Требуется из кода выше, из файла matrix.txt, передать данные в DFS для осуществления поиска в глубину.

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Matrix(int *ptr[], int nRow, int nCol)// Когда параметр массив указатель
{                                       
    for(int i = 0; i < nRow; i++)
    {
        for (int j = 0; j <nCol; j++)
        {
        cout<<ptr[i][j]<<"\t";
        }
        cout<<endl;
    }
    cout<<"\n\n";
}
 
int main () {
int *p[4];
for(int i = 0; i <4; i++)
    p[i]=matrix[i];
       Matrix(p,4,5);
}

@oleg-m1973 · 11.10.2019, 15:09

Сообщение от Triglav86

и передать его в .. dfs? Не знаю что дальше делать. Требуется из кода выше, из файла matrix.txt, передать данные в DFS для осуществления поиска в глубину.

Сделай этот dfs вот таким и передавай incidenceMatrix

C++
1
2
3
void dfs(int **iArr, int m, int n, int t) 
{
..

@Triglav86 · 11.10.2019, 16:36 **[ТС]**

Сообщение от oleg-m1973

Сделай этот dfs вот таким и передавай incidenceMatrix

Спасибо за ответ.

Выскакивает ошибка. Подозреваю что ошибка в том что я не правильно передаю аргументы.( строка 45, 78 )
Не могли бы вы помочь исправить эту ошибку?

Кликните здесь для просмотра всего текста

This application has requested the Runtime to terminate it in an unusual way.
Please contact the application's support team for more information.
terminate called after throwing an instance of 'std::bad_array_new_length'
what(): std::bad_array_new_length

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <vector>
#include <queue> 
using namespace std;
#define u 100
 
const int n = 4; 
const int m = 5; 
 
bool used[n]; 
 
int j, r, i, k = 0;
 
void dfs(int **iArr, int m, int n, int t) { //Обход в глубину графа, представленного матрицей инцидентности
 
    used[t] = true; 
    
    int p;
            
    for (i = k; i < n; i++)
    {
        j = r;
        if ((iArr[i][j] != 0) && (!used[i]))
        {
            used[i] = true;
            p = i;
 
            cout << i << " ";           
 
            for (j = 0; j < m; j++)
            {
                i == p;
                if (iArr[i][j] != 0)
                {
                    r = j;
                
                    for (k = 0; k < n; k++)
                    {
                        j == r;
                
                        if ((iArr[k][j] != 0) && (!used[k]))
                        {                           
                            dfs(iArr,i,j,k);    /*<---------------*/                
                        }
                    }
                }
            }
        }
    }
}
 
int main()
{
    ifstream in("matrix.txt");
    int m, n;
    in >> m;
    in >> n;
    // выделяем память под M строк для матрицы инцидентности 
    int **incidenceMatrix = new int*[m];
    for (int row = 0; row < m; row++)
    {
        // для каждой строки выделяем память под N элементов
        incidenceMatrix[row] = new int[n];
        // считываем значения
        for (int column = 0; column < n; column++) {
            in >> incidenceMatrix[row][column];
            cout << incidenceMatrix[row][column] << " ";
        }
        cout << endl;
    }
    in.close();
    
int *p[4];
for(int i = 0; i <4; i++)
    p[i]=incidenceMatrix[i];
       dfs(p,n,m,0);               /*<---------------*/
 
    cout << endl;
 
    return 0;
}

@oleg-m1973 · 11.10.2019, 16:42

[quote="Triglav86;13893474"]Выскакивает ошибка. Подозреваю что ошибка в том что я не правильно передаю аргументы.( строка 45, 78 )
Скорее всего m и n перепутал dfs(p, m, n, 0);

@Triglav86 · 11.10.2019, 16:49 **[ТС]**

Сообщение от oleg-m1973

Скорее всего m и n перепутал dfs(p, m, n, 0);

Без изменений. Ошибка та же.

@oleg-m1973 · 11.10.2019, 16:54

Сообщение от Triglav86

Без изменений. Ошибка та же.

Сообщение от Triglav86

bool used[n];

Сделай этот массив побольше - bool used[256];

@Triglav86 · 11.10.2019, 16:59 **[ТС]**

Сообщение от oleg-m1973

Сделай этот массив побольше - bool used[256];

Без изменений

У меня подозрение на 45 строку кода dfs(iArr,i,j,k); По разному пробовал менять, ошибка всё равно выскакивает эта.

@oleg-m1973 · 11.10.2019, 17:04

Сообщение от Triglav86

Без изменений

Сообщение от Triglav86

for (i = k; i < n; i++)
* * {
* * * * j = r;
* * * * if ((iArr[i][j] != 0) && (!used[i]))

Что такое здесь *j = r;? Чем у тебя эта r инициализируется?

Это вообще убери

Сообщение от Triglav86

const int n = 4;
const int m = 5;

Сообщение от Triglav86

int j, r, i, k = 0;

@Triglav86 · 12.10.2019, 12:10 **[ТС]**

Без изменений

Может ещё кто помочь разобраться с непонятной о шибкой ?

C++
1
2
3
4
This application has requested the Runtime to terminate it in an unusual way.
Please contact the application's support team for more information.
terminate called after throwing an instance of 'std::bad_array_new_length'
what(): std::bad_array_new_length

Добавлено через 2 часа 17 минут
С этой ошибкой разобрался!

Добавлено через 27 минут
Подскажите пожалуйста как задать ввод первой вершины графа и вывод дальнейших посещенных вершин

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@oleg-m1973 6772 / 4565 / 1844 Регистрация: 07.05.2019 Сообщений: 13,726
	11.10.2019, 16:42
	[quote="Triglav86;13893474"]Выскакивает ошибка. Подозреваю что ошибка в том что я не правильно передаю аргументы.( строка 45, 78 ) Скорее всего m и n перепутал dfs(p, m, n, 0); 1

Граф. Матрица инцидентности

Решение