Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.68
жуня
0 / 0 / 0
Регистрация: 06.12.2009
Сообщений: 4
#1

Графы.Матрица смежности.Ребра связности. - C++

13.05.2010, 09:37. Просмотров 3147. Ответов 0
Метки нет (Все метки)

Уважаемые программисты!
Мне нужно найти минимальное количество ребер, удаление которых превратит связный граф в несвязный. После ввода матрицы смежности я определяю компоненты связности. Затем, по минимальному весу выбираю вершину, удаляю строку и столбец с найденным номером, проверяю граф на связность. А что мне делать затем? Как сделать полный перебор с удалением ребер по одному, по два и т.д. Где их запоминать и в какой момент возвращать в матрицу? Запуталась . Помогите, пожалуйста!

Код прилагаю.

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <stdio.h>
#include <conio.h>
 
#define maxn 10     // максимальное число вершин в графе
 
int n;
int count;
int a[maxn][maxn];          // матрица смежности
int str1[maxn][maxn];       
int Mark[maxn];             // метки вершин графа
int s[maxn];                // сумма по столбцам
int str[maxn];
int rvut[maxn];
 
void Component (int x,int count)
// функция прохождения одной компоненты связности
{
    int i,v;
    Mark[x]=count;          // вершина x помечается как пройденная вершина
    for(i=0;i<n;i++)        
    {
       if (a[x][i]==1)      // есть ребро из x в i
          if(Mark[i]==0)    // еще не пройденной вершины
             Component(i,count);
    }
}
 
void STRONGL_Comp2(int n)
// функция поиска не пройденных вершин графа, т.е. новой компоненты связности
{
    int v=0;
    int count=0;
    for(v=0;v<n;v++)        // сначала все вершины графа
    {
        Mark[v]=0;          // помечаем как не пройденные
    } 
 
    count=0;                // номер компоненты связности
 
    for(v=0;v<n;v++)        // выбор очередной не пройденной вершины
        if (Mark[v]==0)
            {
               count=count+1;   // увеличение компонент связности
               Component(v,count);
            }       
}
 
 
 
void main(void)
{
    FILE *p,*f;
    int i,j,k,mm,ii,jj;
    int *min;   // номер минимального элемента в массиве
    int *uk;    // указатель на элемент массива
    int summark,summark2;
    
    p=fopen("matrsmeg.txt","r");
    if(fscanf(p,"%d",&n)!=EOF)
    {
        printf("%d",n);     // ввод числа вершин
        printf("\n");       
        a[0][0]=0;
        for(i=0;i<n;i++)
           for(j=0;j<n;j++)
              fscanf(p,"%d",&a[i][j]);
    }       
    for(i=0;i<n;i++)
       Mark[i]=0;      // помечаем вершины как необработанные
    summark=0;
    summark2=0;
    fclose(p);
    f=fopen("component.txt","w");
    STRONGL_Comp2(n);   // проход графа в глубину, поиск компонент связности
    for(i=0;i<n;i++)
       summark=summark+ Mark[i];      // суммируем компоненты связности после первого прохода
    printf ("Summa komponent posle pervogo prochoda: %d\n",summark  );
    
    for(i=0;i<n;i++)    // очистим массив s
          s[i]=0;
 
    for(j=0;j<n;j++)    // для каждого столбца суммируем элементы
       for(i=0;i<n;i++)
          s[j]=s[j]+a[i][j];
 
    // Поиск минимального элемента в массиве s
    min=s;          // пусть первый элемент минимальный
    uk=s+1;         // p содержит адрес второго элемента
    // сравниваем оставшиеся элементы массива с минимальным
    for(k=1;k<n;k++)
    {
        if (*uk<*min) min=uk;
        uk++;       // к следующему элементу
    }
    printf ("Min element massiva: %d\n",*min);
    printf ("Nomer stolbca c min elementom: %d\n",k-1);
 
    for(i=0;i<n;i++)
       for(j=0;j<n;j++)
        if ((a[i][j]==1)&& (j==k-1 ||i==k-1)) 
        {
            printf ("REBRO: %d%d\n",j,i);
            str[i]=a[i][j]; // запоминаем в массиве str
            a[i][j]=0;    
        }
    
    STRONGL_Comp2(n);   // проход графа в глубину, поиск компонент связности
    summark2=0;
    for(i=0;i<n;i++)
       summark2=summark2+ Mark[i];  // суммируем компоненты связности после второго прохода
    printf ("Summa komponent posle vtorogo prochoda: %d\n",summark2);
    if (summark2>summark)   // количество компонентов связности увеличилось
        printf ("Rebra svyaznosti vychodyat iz vershiny: %d\n",k-1);
    
    for(i=0;i<n;i++)
       for(j=0;j<n;j++)
        if (j==k-1 || i==k-1) 
        {
            a[i][j]=str[i]; // возвращаем из массива str
        }
 
    
 
    for(i=0;i<n;i++)
       fprintf(f,"%d",i);
    fprintf(f,"\n");
    
    fprintf(f,"\n");
    for(i=0;i<n;i++)
       fprintf(f,"%d",Mark[i]);
    fclose(f);
    getch();
}

matrsmeg.txt на входе (5-количество вершин)

5
0 1 1 1 0
1 0 1 0 0
1 1 0 1 0
1 0 1 0 1
0 0 0 1 0

component.txt - на выходе (01234-вершины, 11112-компоненты связности)

01234
11112
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.05.2010, 09:37     Графы.Матрица смежности.Ребра связности.
Посмотрите здесь:

Графы. Гамильтонов Цикл. Матрица смежности - C++
Вот программа, которую я взял с поиска. Программа должна найти Гамильтонов цикл. #include &lt;iostream.h&gt; #include &lt;stdlib.h&gt; const...

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

Графы и компоненты связности в них - C++
Здравствуйте уважаемые программисты вот есть такая задачка Реализовать алгоритм разбиение графа на компоненты сильной связности. В...

Отсортировать ребра по весу (графы) - C++
Тема:Базовые структуры данных Задание:Отсортируйте ребра по весу. Спасибо заранее) Вот ребра:

Ошибка в поиске компоненты сильной связности (графы) - C++
Доброго времени суток. Подскажите пожалуйста, в чем ошибка. С векторами работаю не давно, думаю что не правильно считываю информацию в...

Задача на графы. Удалить ребра так, чтобы степень любой вершины была равна 3 или 0 - C++
Здравствуйте. Условие задачи, собственно, в названии темы. Возникли проблемы с алгоритмом, не говоря уже про код. Ограничений на входной...

Графы, алгоритм Диница (реализовать граф списком смежности) - C++
У меня есть готовая программа по алгоритму Диница, но граф в матричном представлении. Очень нужно чтобы кто-нибудь помог реализовать граф...

Графы через списки смежности: вывести все вершины, не смежные с данной - C++
вывести на экран все вершины не смежные с данной. код работает, но нужно еще вывести на экран:&quot;все смежные&quot;, в случае если все вершины...

Матрица смежности - C++
В галактике «Milky Way» на планете «Snowtlake» есть N городов, некоторые из которых соединены дорогами. Император галактики «Milky Way»...

Матрица смежности - C++
Найти максимальное по числу вершин подмножество попарно несмежных вершин данного графа ( с n&lt;=10 вершинами).

Дана матрица смежности и неориентированный граф. Выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной - C++
народ помогите пожалуйста написать программу на с++ на графы дана матрица смежности и неориентированный граф. выяснить соседствуют ли...

Найти компоненты связности - C++
Задание было найти связные подграфи заданого графа как я понимаю ето тоже самое что найти компоненты связности Нашел алгоритм но...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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