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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.68
жуня
0 / 0 / 0
Регистрация: 06.12.2009
Сообщений: 4
13.05.2010, 09:37     Графы.Матрица смежности.Ребра связности. #1
Уважаемые программисты!
Мне нужно найти минимальное количество ребер, удаление которых превратит связный граф в несвязный. После ввода матрицы смежности я определяю компоненты связности. Затем, по минимальному весу выбираю вершину, удаляю строку и столбец с найденным номером, проверяю граф на связность. А что мне делать затем? Как сделать полный перебор с удалением ребер по одному, по два и т.д. Где их запоминать и в какой момент возвращать в матрицу? Запуталась . Помогите, пожалуйста!

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

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++
Матрица смежности C++
C++ Задача на графы. Удалить ребра так, чтобы степень любой вершины была равна 3 или 0
C++ Графы. Гамильтонов Цикл. Матрица смежности
графы через списки смежности C++
C++ Графы и компоненты связности в них
Ошибка в поиске компоненты сильной связности (графы) C++
C++ Матрица смежности графа - поиск в глубину

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

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

Текущее время: 18:46. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru