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

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

Войти
Регистрация
Восстановить пароль
 
jhendrix
0 / 0 / 0
Регистрация: 23.02.2010
Сообщений: 184
#1

Генерирование особых графов - C++

03.05.2012, 21:51. Просмотров 736. Ответов 5
Метки нет (Все метки)

кто может привести какой-либо тест(пример в текстовом файле) или алгоритм генерирования тестов для
создания произвольного графа с иерархической структурой ввиде матрицы смежности (желательно чтобы вершин было много) ? (заранее спасибо)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.05.2012, 21:51     Генерирование особых графов
Посмотрите здесь:

Определить k — количество особых элементов массива C++
C++ Генерирование ожерелья
Динамическое генерирование классов C++
Теорие графов. Композиция двух неор. графов. C++
Определить количество «особых» элементов матрицы C++
C++ Найти количество особых элементов в массиве
Нумерация особых строк матрицы C++
Генерирование размещений C++
C++ Rand(), генерирование случайных чисел в заданном интервале
Генерирование точек на поверхностях простых 3D объектов C++
C++ Матрица. Определить количество особых элементов
Определить количество «особых» элементов матрицы C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zitxbit
Master C/C++
 Аватар для zitxbit
87 / 739 / 75
Регистрация: 11.04.2012
Сообщений: 971
03.05.2012, 22:17     Генерирование особых графов #2
C++
1
2
3
4
int X[N][N] = {{0}};
int count = 2 * N;
while (--count >= 0)
     X[rand() % N][rand() % N] = 1;
jhendrix
0 / 0 / 0
Регистрация: 23.02.2010
Сообщений: 184
03.05.2012, 22:24  [ТС]     Генерирование особых графов #3
так это пример произвольного графа, а мне нужен граф со структурой иерархии
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4661 / 2487 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
04.05.2012, 06:40     Генерирование особых графов #4
можно например так:
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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N_max 6 // максимальное количество вершин
#define sh 2 // максимальное количество вершин которые могут подчиняться одной вершине
int main ()
{
    srand( time( NULL ) );
    int a[N_max][N_max]={0}, tmp1, Q[N_max*N_max], i_st=0, i_end=1, mas_kontr[N_max]={0};
    int tmp, i, col=1, j;
    tmp1=rand()%N_max;
    mas_kontr[tmp1]=1; Q[0]=tmp1;
    while(col<N_max)
    {
        tmp=rand()%3;
        if(tmp==0 && i_end-i_st==1)
            tmp=1;
        for(i=0; i<tmp; i++)
        {
            tmp1=N_max;
            while(tmp1==N_max)
            {
                tmp1=rand()%N_max;
                for(; tmp1<N_max; tmp1++)
                    if(mas_kontr[tmp1]==0)
                        break;
            }
            mas_kontr[tmp1]=1; Q[i_end++]=tmp1; a[Q[i_st]][tmp1]=1; col++;
        }
        i_st++;
    }
    printf("Matr smegn:\n");
    for(i=0; i<N_max; i++)
    {
        for(j=0; j<N_max; j++)
            printf("%3d", a[i][j]);
        printf("\n");
    }
    return 0;
}
Добавлено через 11 минут
между 18 и 19 строкой вставьте:
C
1
2
        if(tmp>N_max-col)
            tmp=N_max-col;
jhendrix
0 / 0 / 0
Регистрация: 23.02.2010
Сообщений: 184
04.05.2012, 18:46  [ТС]     Генерирование особых графов #5
можете объяснить идею этого решения ?

Добавлено через 3 часа 55 минут
в вашей проге вы определили переменную sh на строке 5, но нигде не используете эту переменную и еще на строке 15 (может быть я ошибаюсь) вы написали tmp=rand()%3; , а неправильно будет сделать вот так: tmp=rand()%N_max;

(заранее спс)
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4661 / 2487 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
04.05.2012, 21:24     Генерирование особых графов #6
Цитата Сообщение от jhendrix Посмотреть сообщение
в вашей проге вы определили переменную sh на строке 5, но нигде не используете эту переменную и еще на строке 15 (может быть я ошибаюсь) вы написали tmp=rand()%3; , а неправильно будет сделать вот так: tmp=rand()%N_max;

Не по теме:

иногда пальцы, набирающие код, опережают мысли (на самом деле они печатают мысли которые уже устарели)


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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N_max 6 // максимальное количество вершин
#define sh 3 // максимальное количество вершин которые могут подчиняться одной вершине
int main ()
{
    srand( time( NULL ) );
    int a[N_max][N_max]={0}, tmp1, Q[N_max*N_max], i_st=0, i_end=1, mas_kontr[N_max]={0};
    int tmp, i, col=1, j;
    tmp1=rand()%N_max;
    mas_kontr[tmp1]=1; Q[0]=tmp1;
    while(col<N_max)
    {
        tmp=rand()%sh;
        if(tmp==0 && i_end-i_st==1)
            tmp=1;
        if(tmp>N_max-col)
            tmp=N_max-col;
        for(i=0; i<tmp; i++)
        {
            tmp1=N_max;
            while(tmp1==N_max)
            {
                tmp1=rand()%N_max;
                for(; tmp1<N_max; tmp1++)
                    if(mas_kontr[tmp1]==0)
                        break;
            }
            mas_kontr[tmp1]=1; Q[i_end++]=tmp1; a[Q[i_st]][tmp1]=1; col++;
        }
        i_st++;
    }
    printf("Matr smegn:\n");
    for(i=0; i<N_max; i++)
    {
        for(j=0; j<N_max; j++)
            printf("%3d", a[i][j]);
        printf("\n");
    }
    return 0;
}
Цитата Сообщение от jhendrix Посмотреть сообщение
tmp=rand()%N_max;
тоже можно - но на Ваше усмотрение.
Yandex
Объявления
04.05.2012, 21:24     Генерирование особых графов
Ответ Создать тему
Опции темы

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