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

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

Войти
Регистрация
Восстановить пароль
 
Серёжик
0 / 0 / 0
Регистрация: 02.12.2009
Сообщений: 14
#1

Графы - C++

21.10.2010, 20:24. Просмотров 671. Ответов 1
Метки нет (Все метки)

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

желательно на с билдер
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.10.2010, 20:24
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Графы (C++):

Графы - C++
Всем привет! Пишу в принципе год, но с графами не сталкивался, поэтому нужна помощь. Вообщем вопросы, интересующие меня: что есть граф и с...

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

Графы - C++
Помогите написать программу: Модель работы некоторой системы представлена ориентированным графом, где вершины – это состояния системы,...

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

[C++] графы - C++
Алгоритм фронт фолны в графе Помогите.. Дана матрица Ag (Матрица смежности графа) И координаты начальной вершины i,j и кординаты...

Графы - C++
Написать программу, реализующую алгоритм Беллмана-Форда.

1
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
22.10.2010, 06:37 #2
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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
/////////////////////////////////////////////////////////////////////////////////////
//написать программу удаления вершины <графа>:
//а)с сохранением связей
//б)без сохранения связей
/////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <functional>
#include <iostream>
#include <set>
#include <string>
#include <utility>
/////////////////////////////////////////////////////////////////////////////////////
typedef std::string                      T_vertice;
typedef std::pair<T_vertice, T_vertice>  T_edge;
typedef std::set<T_edge>                 T_edges;
typedef std::set<T_vertice>              T_vertices;
/////////////////////////////////////////////////////////////////////////////////////
void  print(const T_edges&  edges)
{
    for(T_edges::const_iterator  edge_it = edges.begin(); edge_it != edges.end();
        ++edge_it)
    {
        std::cout << "("
                  << edge_it->first
                  << ", "
                  << edge_it->second
                  << ")"
                  << std::endl;
    }
}
/////////////////////////////////////////////////////////////////////////////////////
struct T_contains_vertice : public std::unary_function<T_edge, bool>
{
    T_vertice  vertice_;
    T_contains_vertice(T_vertice  vertice) : vertice_(vertice)
    {}
 
    bool operator() (T_edge  edge)
    {
        return edge.first == vertice_
               || edge.second == vertice_;
    }
};
/////////////////////////////////////////////////////////////////////////////////////
T_edges  remove_vertice_without_connections_preservation
    (
        T_edges    edges, 
        T_vertice  deleted_vertice
    )
{
    //Удаляем все ребра, содержащие удаляемую вершину.
    for(;;)
    {
        T_edges::const_iterator  deleted_edge_it 
            = std::find_if(edges.begin(), edges.end(), 
                           T_contains_vertice(deleted_vertice));
 
        if(deleted_edge_it == edges.end())
        {
            break;
        }
        edges.erase(deleted_edge_it);
    }
    return  edges;
}
/////////////////////////////////////////////////////////////////////////////////////
T_edges  remove_vertice_with_connections_preservation
    (
        T_edges    edges, 
        T_vertice  deleted_vertice
    )
{
    //Создаем множество вершин, соседних с вершиной deleted_vertice.
    T_vertices  adjacent_vertices;
    T_contains_vertice  contains_vertice(deleted_vertice);
    for(T_edges::const_iterator  edge_it = edges.begin(); edge_it != edges.end();
        ++edge_it)
    {
        if(contains_vertice(*edge_it))
        {
            adjacent_vertices
                .insert(edge_it->first == deleted_vertice ? edge_it->second : edge_it->first);   
        }
    }
    //Удаляем из множества ребер все ребра, содержащие удаляемую вершину.
    edges = remove_vertice_without_connections_preservation(edges, deleted_vertice);
    //Добавляем в множество ребер ребра, соединяющие каждую пару вершин из adjacent_vertices.
    for(T_vertices::const_iterator  vert_it_A = adjacent_vertices.begin(); 
        vert_it_A != adjacent_vertices.end(); ++vert_it_A)
    {
        for(T_vertices::const_iterator  vert_it_B = vert_it_A; 
            vert_it_B != adjacent_vertices.end(); ++vert_it_B)
        {
            if(*vert_it_A != *vert_it_B)
            {
                edges.insert(T_edge(*vert_it_A, *vert_it_B));
            }            
        }    
    }
    return  edges;
}
/////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    std::cout << "Введите количество ребер графа: ";
    int n = 0;
    std::cin >> n;
 
    std::cout << "Введите "
              << n 
              <<" ребер графа парами имен вершин:"  
              << std::endl;
    
    T_edges  edges;
    for(int i = 0; i < n; ++i)
    {
        std::cout << std::endl
                  << "Ребро #"
                  << i + 1
                  << ":"
                  << std::endl;
 
        std::cout << "\t-> ";
        T_vertice  a;
        std::cin >> a;
 
        std::cout << "\t-> ";
        T_vertice  b;
        std::cin >> b;
 
        edges.insert(T_edge(a, b));
    }
 
    std::cout << std::endl
              << "Введите имя удаляемой вершины: ";
    T_vertice  deleted_vertice;
    std::cin >> deleted_vertice;
    
    std::cout << "Ребра графа с удаленной вершиной "
              << deleted_vertice
              << " с сохранением связей:"
              << std::endl;
    print(remove_vertice_with_connections_preservation(edges, deleted_vertice));
    std::cout << std::endl
              << std::endl
              << "Ребра графа с удаленной вершиной "
              << deleted_vertice
              << " без сохранения связей:"
              << std::endl;
    print(remove_vertice_without_connections_preservation(edges, deleted_vertice));             
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.10.2010, 06:37
Привет! Вот еще темы с ответами:

Графы - C++
Люди скиньте пожалуйста какую нибудь программку на С++ по графам, или дайте ссылку на темку на форему...

Графы - C++
Прочитал про обход графа в глубину, посмотрел реализацию, и тут вопрос а как можно использовать этот обход в глубину?

Графы - C++
помогите с реализацией алгоритма Дейкстры для нахождения расстояния от узла 1 в каждый узел. матрица весов такая...

Графы - C++
Задан граф матрицей смежности Заданы две вершины, начальная и конечная, требуется найти первую вершину в пути между ними


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

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

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