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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Переведите программу на C++ из паскаля http://www.cyberforum.ru/cpp-beginners/thread129020.html
Вот на Паскале: program two; uses crt; type nameStr=string; link=^instrymenti; instrymenti = record name:namestr; marka :namestr;
C++ вещественные массивы 1. По заданным вещественным массивам A, B и С вычислить (minAi)/maxAi + (maxCi)/min(Ci) + max(B+C)I / min(B+C)i. 2. Даны массивы A , B. Выбрать из них положительные элементы и записать соответственно в массивы A и B , где k<6, n<8; из отрицательных элементов сформировать массивы A2 ,B2 . Напечатать суммы и произведения элементов для каждого. Заранее благодарен за любую помощь) http://www.cyberforum.ru/cpp-beginners/thread128983.html
C++ Помогите с сортировкой диагонали массива по убыванию
сортировка диагонали массива по убыванию не получается, помогите с кодом запутался в указателях и выделении памяти и принципе обработки массива
Удалить из строки все символы встречающиеся более одного раза C++
ввести символьную строку удалить из строки все символы встречающиеся более одного раза #include <string.h> #include <conio.h> #include <iostream> using namespace std; int main() { char *pStr;
C++ Ошибка в коде) http://www.cyberforum.ru/cpp-beginners/thread128972.html
Всем привет! Дана целочисленная матрица размера 5*4. Сформировать одномерные массивы, состоящие из количества положительных и суммы отрицательных элементов каждой строки матрицы Где то ошибка....... Заранее благодярю! /****************************************************************** Дана целочисленная матрица размера 5?4. Сформировать одномерные
C++ Выделение памяти под новый объект Люди, посоветуйте, пожайлуста, как в уже созданный массив из N объектов добавить ещё один объект? Преподаватель сказал, что просто надо выделить память под этот объект. Я поняла, что надо снова выделить память на N+1 объект; скопировать существующие N объектов + 1 новый; освободить старую память........................................Только не понимаю, как программно скопировать в выделенную... подробнее

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

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

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
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 05:52. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru