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

Графы - C++

Восстановить пароль Регистрация
 
Серёжик
0 / 0 / 0
Регистрация: 02.12.2009
Сообщений: 14
21.10.2010, 20:24     Графы #1
помогите пожалуйста написать программу удаления вершины:
а)с сохранением связей
б)без сохранения связей

желательно на с билдер
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.10.2010, 20:24     Графы
Посмотрите здесь:

Графы C++
C++ Графы
C++ Графы
C++ [C++] графы
C++ Графы
Графы C++
Графы C++
графы C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mr.X
Эксперт С++
 Аватар для Mr.X
2803 / 1579 / 247
Регистрация: 03.05.2010
Сообщений: 3,673
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));             
}
Yandex
Объявления
22.10.2010, 06:37     Графы
Ответ Создать тему
Опции темы

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