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

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

Войти
Регистрация
Восстановить пароль
 
DarkPreacher
Сообщений: n/a
#1

Графы - C++

17.05.2010, 02:58. Просмотров 813. Ответов 0
Метки нет (Все метки)

Есть задача. "Осуществите для данного графа построение эксцентриситета заданной вершины v по всем вершинам u.Граф не взвешенный и не ориентированный" Т.е. задается вершина и надо найти эксцентриситет от неё до заданных. Пробовал сделать это на основе алгоритма прима, находя сначала максимальные пути до всех вершин. Получилось что-то такое нерабочее:
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
# include <stdio.h>
# include <stdlib.h>
# include <time.h>
# include <conio.h>
 
int k,n,i,j,a[20][20],t,s[20],b[20],f,v[20],d,z,p;
char c[10];
    
void in()
{
     printf("Enter number from 0 to %d\n",n-1);
     scanf("%d %d",&i,&j);
     while(i<0 || j<0 || i>=n || j>=n || i==j) 
        {
               printf("Error. Please try other number.\n"); 
               scanf("%d %d",&i,&j);
        }  
     a[j][i]=a[i][j]=1;
}
 
void out()
{
     for(i=0;i<n;i++)
     {
      for(j=0;j<n;j++)
      printf("%d  ", a[i][j]);
      printf("\n");
     }
}
 
void del()
{
     printf("Enter number from 0 to %d\n",n-1);
     scanf("%d %d",&i,&j);
     while(i<0 || j<0 || i>=n || j>=n || i==j) 
     {
           printf("Error. Please try other number.\n"); 
           scanf("%d %d",&i,&j);
     }  
     a[j][i]=a[i][j]=0;    
}
void go()
{
    s[t] = 1; 
    
    for(i = 0; i < n; i++)
    {
     
     for(k = 0; k < n; k++)
     {     
           if(s[k] != 1)
           {
            for(j = 0; j < n; j++)    
            if (a[j][k] != 0 && b[k] < b[j] + a[j][k]) {b[k] = b[j] + a[j][k]; v[k] = j; j = d;}
           }
     }
     s[d] = 1;
    }
     
}
 
int main()
{
    srand(time(NULL));
    printf("Dimension: "); 
    scanf("%d",&n);
    while(n<=0) {printf("Error. Please try other number."); scanf("%d", &n);}
    int a[n][n];
    for(i=0;i<n;i++){b[i]=0;
            for(j=0;j<n;j++){
                    a[i][j]=0; }}
                    while(1)
                    {
                       printf("\n1. What tops are connected?\n2. Show matrix\n3. ---\n4. Which tops are disconnected? =)\n5. Clear sreen\n6. Exit\n");
                       scanf("%s",c);
                       switch(atoi(c))
                       {
                           case 1: 
                                in();
                                break;
                           
                           case 2: 
                                out();
                                break;
    
                           case 3:
                                for(i=0;i<n;i++) {v[i]=0;b[i]=0;s[i]=0;}
                                printf("From which top start?");
                                scanf("%d",&t);
                                for(i = 0; i < n; i++) v[i] = t;
                                for(i = 0; i < n; i++) b[i] = a[t][i];
                                v[t] = 0;
                                go();
                                printf("\n\n");
                                for(i=0;i<n;i++)
                                  printf("%d\t%d\t\n", b[i], v[i]);
                                getch();
                                break;
                                
                           case 4:
                                del();
                                break;
                                
                           case 5:
                                system("cls");
                                break;
                                     
                           case 6:
                                exit(0);
                                
                           default:
                                printf("Wrong input. Try something other =)\n");
                                
                        }
                    }
    return 0;    
}
Помогите реализовать саму функцию go т.е. само нахождение этих путей. Или подскажите алгоритм нахождения эксцентриситета в графе.

Добавлено через 5 часов 1 минуту
Ни кто не знает даже алгоритм? Хотя бы ссылочку где он написан. Не может быть, чтобы его не было.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.05.2010, 02:58     Графы
Посмотрите здесь:

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

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

Графы на С++ - C++
Помогите плиз! Есть задача: Посвящение в студенты.Есть n студентов.НЕ ВСЕ знают друг друга.Но у каждого есть знакомые..Действует...

Графы - C++
Написать на C++ класс, описывающий граф/орграф. Класс должен поддерживать следующую функциональность: • определение числа вершин; ...

Графы - C++
помогите пожалуйста написать программу удаления вершины: а)с сохранением связей б)без сохранения связей желательно на с билдер

*Графы* - C++
пожалуйсто помоги мне с программой.умоляю!!! вот тема: реализация различных типов графов и операций над ними. зараннее спасибо.

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

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

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

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


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

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

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