Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

Построение контура в графе - C++

31.05.2014, 22:24. Просмотров 335. Ответов 1
Метки нет (Все метки)

Здравствуйте, имею задание:
На плоскости заданы координаты N элементов, являющихся выводами печатной платы. Некоторые элементы связаны между собой. Требуется выбрать начальный элемент для построения контура (пути, не содержащего циклов) максимальной длины. Контур строится по следующему правилу: из всех возможных элементов, связанных с данным, в контур включается ближайший элемент.
Граф представил в виде матрицы смежности, нужна помощь в построении контура. Помогите пожалуйста
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
void ShowGraph ( int **Graph, int countVertices ){
    cout << "\n";
    for ( int i = 0; i < countVertices; i++ ){
        for ( int j = 0; j < countVertices; j++ ){
            cout << Graph[i][j] << " ";
        }
        cout << "\n";
    }
    cout << "\n";
}
 
int AddEdgeOriented ( int **Graph, int countVertices ){
    int x, y;
    cout << "\nEnter coordinates of edge: ";
    cin >> x >> y;
 
    if ( x == y ){
        for ( int i = 0; i < countVertices; i++ ){
            for ( int j = 0; j < countVertices; j++ ){
                Graph[y-1][x-1] = 0;
            }
        }
        return 0;
    }
 
    else{
        for ( int i = 0; i < countVertices; i++ ){
            for ( int j = 0; j < countVertices; j++ ){
                Graph[y-1][x-1] = 1;
            }
        }
        return 1;
    }
}
 
int AddEdgeUnoriented ( int **Graph, int countVertices ){
    int x, y;
    cout << "\nEnter coordinates of edge: ";
    cin >> x >> y;
 
    if ( x == y ){
        for ( int i = 0; i < countVertices; i++ ){
            for ( int j = 0; j < countVertices; j++ ){
                Graph[y-1][x-1] = 0;
                Graph[x-1][y-1] = 0;
            }
        }
        return 0;
    }
 
    else{
        for ( int i = 0; i < countVertices; i++ ){
            for ( int j = 0; j < countVertices; j++ ){
                Graph[y-1][x-1] = 1;
                Graph[x-1][y-1] = 1;
            }
        }
        return 1;
    }
}
 
int main()
{
    int countVertices;
    cout << "Enter number of vertices: "; // Количество вершин
    cin >> countVertices;
 
    int **Graph, i, j;
    Graph = new int *[countVertices];
 
    for ( i = 0; i < countVertices; i++ ){
        Graph[i] = new int [countVertices];
    }
 
    for ( i = 0; i < countVertices; i++ )
        for ( j = 0; j < countVertices; j++ )
            Graph[i][j] = 0;
    ShowGraph (Graph, countVertices);
 
 
 
    int countEdges; // Количество рёбер
    cout << "\nHow many edges you want to add? - ";
    cin >> countEdges;
 
    char flag;
    for ( i = 0; i < countEdges; i++ ){
        cout << "Oriented edge? y / n: ";
        cin >> flag;
        if (flag == 'y')
            AddEdgeOriented (Graph, countVertices);
        else
            AddEdgeUnoriented (Graph, countVertices);
    }
    ShowGraph (Graph, countVertices);
 
/*
    int initialElement; // начальный элемент
    cout << "Enter initial element: ";
    cin >> initialElement;
*/
 
/*
   построение контура
*/
 
    for ( i = 0; i < countVertices; i++ )
            delete [] Graph[i];
    delete [] Graph;
 
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.05.2014, 22:24
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Построение контура в графе (C++):

Поиск отрицательного цикла (контура) в графе - C++
Всем привет! Помоги пожалуйста с программой! :-mass), затем я её модифицирую: for (int i = 0; i &lt; n; ++i) for (int j = 0; j &lt;...

Offset контура в 2D - C++
Привет! Есть контур из отрезков, отрезок образован двумя точками. У точек могут быть любые свойства, пока ещё не придумал, какие нужны,...

Opencv , CvSeq , координаты контура. - C++
Здравствуйте форумчане. Может ктото знает как найти координаты контура (крайние точки ну или центр) в Opencv. Координаты получаю...

Отслеживающий алгоритм нахождения контура изображения - C++
Есть некоторое BMP изображение, фоновым цветом которого является белый цвет. На нём черным цветом изображен некоторый объект, например...

Вычислить период колебаний контура по формуле Томпсона - C++
Друзья , прошу пожалуйста помочь с написанием кода. нужно произвести расчет по данной формуле T=2pi*√LC (формула для расчета периода...

К-ый путь в графе(ДП) - C++
Здраствуйте! Прошу Вас помоч с задачной на ДП, думаю над ней достаточно долго, но ничего в голову путного не приходит. Вот условие: ...

1
Psilon
Master of Orion
Эксперт .NET
5913 / 4810 / 634
Регистрация: 10.07.2011
Сообщений: 14,409
Записей в блоге: 5
Завершенные тесты: 4
31.05.2014, 22:32 #2
11101010, тут на шарпе описание, но не сложнее плюсов ятп.
http://habrahabr.ru/post/66586/
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.05.2014, 22:32
Привет! Вот еще темы с ответами:

Расстояние на графе - C++
Подскажите пожалуйста, с помощью какого алгоритма можно найти расстояние от заданной вершины графа до всех остальных вершин. Спасибо!

Пути на графе - C++
Здравствуйте, помогите пожалуйста придумать алгоритм поиска путей на орентированом графе. Пример: 0 8 7 2 0 0 0 3 0 8 0 8 0 0 0...

Поиск на графе - C++
Доброго времени суток. Мне не совсем понятна реализация в коде поиска на графе в высоту и ширину. Т.к. в книге они описаны не совсем...

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


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

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