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

Графы - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.67
Sonn ADK
0 / 0 / 0
Регистрация: 23.12.2010
Сообщений: 11
23.12.2010, 22:11     Графы #1
Граф задан своей матрицей смежностей. Вывести на экран все связные вершины...очень скоро нужно...извините за срочность
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.12.2010, 22:11     Графы
Посмотрите здесь:

Графы C++
C++ Графы
C++ [C++] графы
C++ Графы
Графы C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
23.12.2010, 22:43     Графы #2
Sonn ADK, Уточню только про вывод:
Цитата Сообщение от Sonn ADK Посмотреть сообщение
Вывести на экран все связные вершины...
Можно по-конкретнее?
sandye51
программист С++
 Аватар для sandye51
677 / 579 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
23.12.2010, 22:46     Графы #3
valeriikozlov, имеется ввиду смежные.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
23.12.2010, 22:49     Графы #4
смежные вершины и связаные вершины это разные вещи. А у Sonn ADK голос пропал? Хотелось бы услышать автора темы.
sandye51
программист С++
 Аватар для sandye51
677 / 579 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
23.12.2010, 22:52     Графы #5
valeriikozlov, термина связные вершины не существует
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
23.12.2010, 22:54     Графы #6
Связность. Две вершины в графе связаны, если существует соединяющая их (простая) цепь.
это взято отсюда:
http://ru.wikipedia.org/wiki/Подграф#.D0.9F
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
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
23.12.2010, 23:19     Графы #8
Давайте теперь я задам вопросы:
1. Нужно вывести все связанные вершины, по группам несвязанными между собой?
2. если какие-либо вершины вообще не связанные ни с какими вершинами их выводить как группу или вообще не выводить?
sandye51
программист С++
 Аватар для sandye51
677 / 579 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
23.12.2010, 23:20     Графы #9
имеется ввиду вывести компоненты связности в виде набора вершин
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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 выводим как отдельные группы или вообще не выводим?
Sonn ADK
0 / 0 / 0
Регистрация: 23.12.2010
Сообщений: 11
23.12.2010, 23:34  [ТС]     Графы #11
valeriikozlov, нужно вывести все связные вершины просто в строчку.......если какие-либо вершины вообще не связанные ни с какими вершинами вообще не выводить
.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);
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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;
        }
}
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 не выводим вообще?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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();
}
Sonn ADK
0 / 0 / 0
Регистрация: 23.12.2010
Сообщений: 11
24.12.2010, 00:33  [ТС]     Графы #16
valeriikozlov, Выводит вот что.
Sonn ADK
0 / 0 / 0
Регистрация: 23.12.2010
Сообщений: 11
24.12.2010, 00:38  [ТС]     Графы #17
вот что
Миниатюры
Графы  
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.12.2010, 07:40     Графы
Еще ссылки по теме:

Графы C++
Графы C++
C++ Графы

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
24.12.2010, 07:40     Графы #18
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)
        {
           cout<<i<<" "<<endl;
           break;
        }
}
cout<<endl; getch();
}
Yandex
Объявления
24.12.2010, 07:40     Графы
Ответ Создать тему
Опции темы

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