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

Как удалить ребро в графе? - C++

Восстановить пароль Регистрация
 
Clover_n
0 / 0 / 0
Регистрация: 25.12.2013
Сообщений: 30
09.05.2014, 15:47     Как удалить ребро в графе? #1
Имеется граф с N вершинами и заданный списком смежности. Требуется удалить ребро, который соединяет вершины a и b.
Ребро задается отдельной переменной? И как реализовать его удаление?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
_script_
169 / 137 / 34
Регистрация: 01.05.2012
Сообщений: 414
09.05.2014, 15:50     Как удалить ребро в графе? #2
Clover_n, это смотря как храниться граф)
Если парами вершин, то просто удалить одну пару.
Если матрицам, то менять значения определенного элемента.
Clover_n
0 / 0 / 0
Регистрация: 25.12.2013
Сообщений: 30
09.05.2014, 15:54  [ТС]     Как удалить ребро в графе? #3
можете привести пример реализации удаления в обоих случаях?
полностью программу не надо)
пытаюсь разобраться
_script_
169 / 137 / 34
Регистрация: 01.05.2012
Сообщений: 414
09.05.2014, 16:00     Как удалить ребро в графе? #4
Clover_n, лучше ты скажи, как у тебя храниться граф и все.
Clover_n
0 / 0 / 0
Регистрация: 25.12.2013
Сообщений: 30
09.05.2014, 16:12  [ТС]     Как удалить ребро в графе? #5
У меня через массив




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
 
#include <stdio.h>
using namespace std;
 
FILE *f= fopen("f.txt"."r")
FILE *g= fopen("g.txt"."w")
 
int n; // кол-во вершин в графе
int **gr; // ук-ль на матрицу смежности
 
 
void dfs 
{ функция чтобы проверить вершины и удалить ребро, соединяющее их.
....
}
 
 
void main()
{
int u,v, i, j;
fscanf(f, "%d","&n"); // считываем размерность массива
gr=new int *[n];  // выделяем память под кол-во строк в массиве смежности
 
//для каждой i-той строки матрицы, которая соответствует i-той вершине графа
for (i=0, i<n, i++) 
{  gr[i]=new int[n]; //выделяем память под i-тую строку матрицы смежности
    for (j=0, j<n, j++) //вводим эту строку из файла f
        fscanf(f, "%d", &gr[i][j])
}
for (i=0, i<n, i++) //для каждой вершины графа 
    func(i); //вызываем функцию, чтобы проверить вершины и удалить ребро, соединяющее их.
 
fcloseall();
//освобождаем память 
for (i=0, i<n, i++) delete gr[i];
delete gr;
}
_script_
169 / 137 / 34
Регистрация: 01.05.2012
Сообщений: 414
09.05.2014, 16:16     Как удалить ребро в графе? #6
ну для матрицы смежности удалить одно ребро между а и b можно так:
C++
1
2
gr[a][b]--;
gr[b][a]--;
а все ребра между ними
C++
1
2
gr[a][b]=0;
gr[b][a]=0;
Clover_n
0 / 0 / 0
Регистрация: 25.12.2013
Сообщений: 30
09.05.2014, 16:21  [ТС]     Как удалить ребро в графе? #7
перед этим нужно проверить, соединяются ли эти вершины, так?
_script_
169 / 137 / 34
Регистрация: 01.05.2012
Сообщений: 414
09.05.2014, 16:30     Как удалить ребро в графе? #8
Clover_n, если gr[a][b]>0, то есть ребра между a и b.
Clover_n
0 / 0 / 0
Регистрация: 25.12.2013
Сообщений: 30
09.05.2014, 16:39  [ТС]     Как удалить ребро в графе? #9
можно попросить у вас помощи в доработке программы?
пожалуйста)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.05.2014, 16:42     Как удалить ребро в графе?
Еще ссылки по теме:

Рассчитать ребро куба, площадь полной поверхности равна s C++
C++ Как обозначается перенос строки? Как мне удалить пустую строку?
C++ Как найти НЕ Кратчайший путь в графе ?

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

Или воспользуйтесь поиском по форуму:
_script_
09.05.2014, 16:42     Как удалить ребро в графе?
  #10

Не по теме:

Цитата Сообщение от Clover_n Посмотреть сообщение
можно попросить у вас помощи в доработке программы?
Ответил в лс

Yandex
Объявления
09.05.2014, 16:42     Как удалить ребро в графе?
Ответ Создать тему
Опции темы

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