Графы, матрица смежности, поиск петель

@Al312 · Регистрация: 01.01.2013

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

Добрый вечер!
Задача: Задан граф в виде количества вершин n≤10 и последовательности ребер (каждое ребро задается парой смежных вершин). Получить матрицу смежности. Напечатать матрицу смежности. Проверить, есть ли в графе петли.

Так вот с выводом матрицы смежности я разобралась, объясните когда и каким образом можно проверить вершины на петли?

Вот код:

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
#include <stdio.h>
#include <conio.h>
#define NMAX 10 /*макс число вершин*/
 
/* Функция ввода графа */
int VvodGraf ( int  ms [NMAX][NMAX] )
/* ms – матрица смежности */
/* Возвращаемое значение – число вершин графа */
{  
    int n;      /* число вершин графа */
    int  i, j;  /* номера вершин */
    
    puts ("Введите число вершин (<=10)");
    scanf ("%d", &n);
    
    /* Обнуление матрицы смежности */
    for  (i=0; i<n; i++)
        for (j=0; j<n; j++)   ms[i][j] = 0;
        
    puts ("Введите последовательность ребер, завершив ввод ");
    puts ("нажатием Ctrl-Z");
    
    while (scanf("%d %d", &i,&j) !=EOF)
         ms[i][j] = ms[j][i] = 1;
    
    /* Проверка содержимого массива*/   
    printf("\nПроверка содержимого массива: \n");
    for  (i=0; i<n; i++)
        for (j=0; j<n; j++)  printf("[%d][%d] = %d\n", i, j, ms[i][j]);
        
    /* Выводим матрицу смежности*/
    printf("\nМатрица смежности:\n");
    printf(" |");
    
    for  (j=0; j<n; j++) printf("%d ", j); /*строим строку*/
    putchar ('\n');
    
    for  (i=0; i<2*n+2; i++) 
        putchar ('-');
        
    for  (i=0; i<n; i++) 
    {
        printf("\n%d|", i); /*строим столбец*/
        for (j=0; j<n; j++)  printf("%d ", ms[i][j]); /*заполняем матрицу*/
    }   
        
    return  n;
}
 
/* Главная функция*/
int main()
{   
    int g[NMAX][ NMAX] ;    /* матрица смежности  */
    int n;                  /* число вершин графа */
    
    n = VvodGraf (g);       /* вызов функции ввода графа */
 
}

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Введите число вершин (<=10)
2
Введите последовательность ребер, завершив ввод
нажатием Ctrl-Z
0 1
0 0
^Z
 
Проверка содержимого массива:
[0][0] = 1  -> тут у нас петля
[0][1] = 1
[1][0] = 1
[1][1] = 0
 
Матрица смежности:
 |0 1
------
0|1 1
1|1 0

@Dimension · 22.05.2016, 19:59

пройтись по диагонали и посмотреть , где есть единички - это петля ,ибо путь идет из вершины в саму себя

@Al312 · 22.05.2016, 22:17 **[ТС]**

ну да, похоже петли только на главной диагонали образуются

Добавлено через 1 час 29 минут
Добавила счетчик:

C++
1
2
3
4
5
6
    /* Ищем петлю*/
    for  (i=0; i<n; i++)
        for (j=0; j<n; j++)  
            if((i == j) && (ms[i][j] == 1)) k++;
                
    printf("\n\nКоличество петель:%d", k);

@avgoor · 22.05.2016, 22:21

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

Добавила счетчик:

C++
1
2
3
4
5
/* Ищем петлю*/
for (i=0; i<n; i++)
    for (j=0; j<n; j++) 
        if((i == j) && (ms[i][j] == 1)) k++;
printf("\n\nКоличество петель:%d", k);

Феерично!

C++
1
2
for(int i=0; i<n; i++)
    if(ms[i][i]==1) k++;

@Al312 · 24.05.2016, 21:07 **[ТС]**

Уважаемый, avgoor, вместо наречий лучше бы прокомментировали свой код.
В особенности этот кусок:

C++
1
if(ms[i][i]==1)

@avgoor · 24.05.2016, 23:08

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

Уважаемый, avgoor, вместо наречий лучше бы прокомментировали свой код.
В особенности этот кусок:

А что там не понятно? Вам не очевидно что если i==j то между ms[i][j] и ms[i][i] нет разницы? Так зачем тогда нужен внутренний цикл?
Допустим n==1000. Тогда в вашем коде if((i == j) && (ms[i][j] == 1)) выполнится 1000000 раз вместо 1000. Зачем?

Новые блоги и статьи Все статьи Все блоги /
Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.

@Dimension Dimension 595 / 463 / 223 Регистрация: 08.04.2014 Сообщений: 1,710
	22.05.2016, 19:59
	Сообщение было отмечено Al312 как решение Решение пройтись по диагонали и посмотреть , где есть единички - это петля ,ибо путь идет из вершины в саму себя 0

Графы, матрица смежности, поиск петель

Решение