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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.67
Sonn ADK
0 / 0 / 0
Регистрация: 23.12.2010
Сообщений: 11
#1

Графы - C++

23.12.2010, 22:11. Просмотров 2121. Ответов 17
Метки нет (Все метки)

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

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

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

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

Графы - C++
1) Построить граф, используя язык С++ (или Си), согласно данной схеме на рис.1. 2) По запросу пользователя должны удаляться: • все...

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
23.12.2010, 22:43 #2
Sonn ADK, Уточню только про вывод:
Цитата Сообщение от Sonn ADK Посмотреть сообщение
Вывести на экран все связные вершины...
Можно по-конкретнее?
0
sandye51
программист С++
684 / 586 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
23.12.2010, 22:46 #3
valeriikozlov, имеется ввиду смежные.
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
23.12.2010, 22:49 #4
смежные вершины и связаные вершины это разные вещи. А у Sonn ADK голос пропал? Хотелось бы услышать автора темы.
0
sandye51
программист С++
684 / 586 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
23.12.2010, 22:52 #5
valeriikozlov, термина связные вершины не существует
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
23.12.2010, 22:54 #6
Связность. Две вершины в графе связаны, если существует соединяющая их (простая) цепь.
это взято отсюда:
http://ru.wikipedia.org/wiki/Подграф#.D0.9F
0
Sonn ADK
0 / 0 / 0
Регистрация: 23.12.2010
Сообщений: 11
23.12.2010, 23:08  [ТС] #7
Граф называется связным, если любая пара его вершин соединима. Вот.
Т.е. допустим вот матрица смежностей для графа из 3 точек:
010
101
010
Нулевая вершина соединена с первой, а первая в свою очередь со второй. Надо задать граф. Т.е. задать его матрицу смежностей интерактивно. В этой вот матрице должно выводиться на экран, то что связаны 0 с 1 и 2. Т.е конкретно должно выводиться 0,1,2
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
23.12.2010, 23:19 #8
Давайте теперь я задам вопросы:
1. Нужно вывести все связанные вершины, по группам несвязанными между собой?
2. если какие-либо вершины вообще не связанные ни с какими вершинами их выводить как группу или вообще не выводить?
0
sandye51
программист С++
684 / 586 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
23.12.2010, 23:20 #9
имеется ввиду вывести компоненты связности в виде набора вершин
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
23.12.2010, 23:32 #10
Sonn ADK, Может не все понятно что я хотел спросить? Вот смотрите: есть граф из 8 вершин.
Вершина 1 связана с вершиной 2.
Вершина 2 связана с вершиной 3.
Вершина 6 связана с вершиной 7.
Вершина 7 связана с вершиной 8.
и больше связей нет.
Выводим получается так:
группа 1: 1,2,3
группа 2: 6,7,8
А вершины 4 и 5 выводим как отдельные группы или вообще не выводим?
0
Sonn ADK
0 / 0 / 0
Регистрация: 23.12.2010
Сообщений: 11
23.12.2010, 23:34  [ТС] #11
valeriikozlov, нужно вывести все связные вершины просто в строчку.......если какие-либо вершины вообще не связанные ни с какими вершинами вообще не выводить
0
.4rray
8 / 8 / 0
Регистрация: 15.12.2010
Сообщений: 41
23.12.2010, 23:40 #12
Что-то вроде?:
C++
1
2
3
4
5
int table[n][n];          //Туда записали таблицу смежности.
 
for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
        if(table[i][j] == 1) printf("%d связана с %d\n",i,j);
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
23.12.2010, 23:43 #13
Sonn ADK, даже на группы не делить не связанные между собой? странно, но ладно, тогда так:
если задана матрица смежности a[n][n]
C++
1
2
3
4
5
6
7
8
9
for(int i=0; i<n; i++)
{
    for(int j=0; j<n; j++)
        if(a[i][j]==1)
        {
           std::cout<<i<<" "<<std::endl;
           break;
        }
}
0
Sonn ADK
0 / 0 / 0
Регистрация: 23.12.2010
Сообщений: 11
24.12.2010, 00:15  [ТС] #14
вообще не выводим

Добавлено через 20 минут
У меня есть программа, которая выводит окружение вершин графа.....вот мне там функцию, где находится окружение вершины надо переделать, в функцию, чтобы выводил связные вершиы графа
вот эта программа, с окружениями вершины...

#include <iostream>
#include <conio.h>

int*get_matrix( int N)
{int*Ar2=new int[N*N];
for(int Row=0;Row<N;Row++)
for(int Col=0;Col<N;Col++)
{cout<<"M["<<Row<<"]["<<Col<<"]=";
cin>>Ar2[Row*N+Col];}
return Ar2;}


void out_matrix(int*Ar2,int N)
{ for(int Row=0;Row<N;Row++)
{for(int Col=0;Col<N;Col++)
cout<<Ar2[Row*N+Col]<<" ";
cout<<'\n';}
}

void out_okr(int*Ar2,int N)
{
for(int Row=0;Row<N;Row++)
{
cout<<endl<<"Vershina "<<Row<<" v okrugenii : ";
for(int Col=0;Col<N;Col++)
if(Ar2[Row*N+Col]!=0)
cout<<" "<<Col;
}
cout<<endl; getch();
}

int main() {
int N, *Ar;
cout<<"N= ";
cin>>N;
Ar=get_matrix(N);
out_matrix(Ar, N);
out_okr(Ar, N);

return 0; getch();
}

Добавлено через 8 минут
valeriikozlov, Вершина 1 связана с вершиной 2.
Вершина 2 связана с вершиной 3.
Вершина 6 связана с вершиной 7.
Вершина 7 связана с вершиной 8.
и больше связей нет.
Выводим получается так:
группа 1: 1,2,3
группа 2: 6,7,8

А так Вы все правильно поняли
А вершины 4 и 5 не выводим вообще?
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
24.12.2010, 00:21 #15
C++
1
2
3
4
5
6
7
8
9
10
11
void out_okr(int*Ar2,int N)
{
for(int Row=0;Row<N;Row++)
{
cout<<endl<<"Vershina "<<Row<<" v okrugenii : ";
for(int Col=0;Col<N;Col++)
if(Ar2[Row*N+Col]!=0)
cout<<" "<<Col; 
}
cout<<endl; getch();
}
замените на:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
void out_okr(int*Ar2,int N)
{
for(int i=0; i<N; i++)
{
    for(int j=0; j<N; j++)
        if(Ar2[i*N+j]==1)
        {
           std::cout<<i<<" "<<std::endl;
           break;
        }
}
cout<<endl; getch();
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.12.2010, 00:21
Привет! Вот еще темы с ответами:

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

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

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

Графы - C++
Дано прямоугольное клеточное поле; как создать матрицу смежности для графа ферзей?


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
24.12.2010, 00:21
Ответ Создать тему
Опции темы

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