Форум программистов, компьютерный форум, киберфорум
C (Си)
Войти
Регистрация
Восстановить пароль
 
0 / 0 / 0
Регистрация: 24.11.2018
Сообщений: 8
1

Реализация алгоритма поиска независимых ребер графа

19.12.2020, 13:57. Просмотров 1549. Ответов 0

Задача состоит в том, что бы создать алгоритм поиска независимых ребер, проще говоря, это когда два ребра не соединены одной общей вершиной. На данный момент я думаю, что это можно как-то реализовать при помощи матрицы инцидентности. У меня есть хорошая идея по реализации. Пусть будет матрица инцидентности (столбцы ребра, строки вершины):
Кликните здесь для просмотра всего текста

1 0 0 0 0 0
0 1 1 1 0 0
0 1 0 0 1 0
0 0 1 0 1 1
1 0 0 1 0 1

Это граф к этой матрице:
Кликните здесь для просмотра всего текста
Реализация алгоритма поиска независимых ребер графа

Возьмем первый столбец (ребро), видим, что есть 1 на первой строке и на пятой строке. Сравниваем этот столбец с остальными по такому принципу, что на этих местах (1 и 5 строки) 1 больше не будет. В этом случае получится, что 1 и 2, 1 и 3, 1 и 5 ребра независимы! Так вот, у меня не получается реализовать этот алгоритм, пока у меня есть лишь код с матрицей инцидентности на основе матрицы смежности:
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
printf("\nМатрица инцидентности: \n");
    int r  = 0;
 
    int reb = 0;
    int sch3 = 0;
 
    while (sch3 != n)
        for (int i = 0; i < n; i++)
        {
            for (int j = 0 + sch3; j < n; j++)
                if (graph[i][j] != 0)
                    reb++;
            sch3++;
        }
    /////
 
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (graph[i][j] != 0)
                graph[j][i] = 0;
 
    int** inc;
 
    inc = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++)
    {
        inc[i] = (int*)malloc(reb * sizeof(int));
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < reb; j++)
            inc[i][j] = 0;
 
    int sch4 = reb;
    reb = 0;
    for (int i = 0; i < n; i++)             //создание матрицы инцидентности
    {
        for (int j = 0; j < n; j++)
            if (graph[i][j] != 0)
            {
                inc[i][reb] = 1;                //начало
                inc[j][reb] = 1;                //конец
                reb++;
            }
    }
 
    printf("\n    ");
    for (int i = 0; i < sch4; i++) {
        printf("[%d] ", i + 1);
    }
    for (int i = 0; i < n; i++)
    {
        printf("\n[%d]", i + 1);
 
        for (int j = 0; j < reb; j++)
        {
            if ((i + 1) < 10)
            {
                if (j < 10)
                    printf("%3d ", inc[i][j]);
                else
                    printf(" %3d ", inc[i][j]);
 
            }
 
            else if ((i + 1) < 100)
            {
                if (j == 0)
                    printf(" %d", inc[i][j]);
                else if (j < 10)
                    printf("   %d", inc[i][j]);
                else
                    printf("    %d", inc[i][j]);
 
            }
 
        }
    }
Программа должна выводить все независимые ребра этого графа, помогите пожалуйста.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.12.2020, 13:57
Ответы с готовыми решениями:

программная реализация поиска в глубину с использованием стеком рёбер графа
Постройте программную реализацию поиска в глубину с использованием стеком рёбер графа. Граф...

Реализация ввода весов рёбер у графа
Добрый час, есть проект, который строит графы и находит от одной вершины кратчайшие пути до других....

Реализация ввода весов(значений) рёбер(дуг) у графа
Проект, который строит графы и находит от одной вершины кратчайшие пути до других. Возникла...

Реализация класса GraphCode, хранящий список ребер для графа
Класс GraphCode, хранящий список ребер для графа. Методы: · GraphCode(int mi): построение...

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.12.2020, 13:57

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Построить стягивающее дерево неориентированного графа методом поиска в ширину и вывести список рёбер дерева
1: Построить стягивающее дерево неориентированного графа методом поиска в ширину и вывести список...

Визуализация графа (реализация алгоритма)
Начало темы https://www.cyberforum.ru/cpp-beginners/thread783380.html Нашел описание алгоритма...

Реализация алгоритма обхода графа в ширину
Разработать программу для реализации алгоритма обхода графа в «ширину».Использовать свой...

15. Построить стягивающее дерево неориентированного графа методом поиска в глубину и вывести список рёбер дерева. Граф задан в текстовом файле матрице
Построить стягивающее дерево неориентированного графа методом поиска в глубину и вывести список...

Реализация алгоритма Хакими по поиску абсолютного центра графа
Ищу реализацию алгоритма Хакими по поиску абсолютного центра графа. Теорию знаю, а реализовать в...

Реализация алгоритма построения минимального остовного дерева для графа.
Помогите пожалуйста написать программу по курсовой!!! Тема: Реализация алгоритма построения...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.