Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.67
Sonn ADK
0 / 0 / 2
Регистрация: 23.12.2010
Сообщений: 11
#1

Граф задан своей матрицей смежностей, вывести на экран все связные вершины - C++

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

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

Граф задается своей матрицей смежностей вывести на экране окружения каждой его вершины
Привет, ребят! Прошу Очень помочь! Граф задается своей матрицей смежностей....

Граф задается своей матрицей смежностей; вывести на экран матрицу инцидентности графа.
Пожалуйста помогите с задачкой: Граф задается своей матрицей смежностей;...

Считать граф из файла (граф задан матрицей) представить его в виде списка и записать список заново в файл
помогите очень срочно надо. считать граф из файла (граф задан матрицей)...

Дан ориентированный граф. Найти все сильно связные компоненты графа
Есть вот такой код, очень прошу исправить под задание в теме поста Спасибо...

задан файл неопределённой длины, прочитать все записи, номер которых кратен 5 и вывести их на экран
задан файл неопределённой длины, прочитать все записи, номер которых кратен 5 и...

Вывести на экран вершины орграфа, смежные с данной
Уффф, к завтрашнему дню нужно сдать эти задачи, помогите пожалуйста кто чем...

17
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
23.12.2010, 22:43 #2
Sonn ADK, Уточню только про вывод:
Цитата Сообщение от Sonn ADK Посмотреть сообщение
Вывести на экран все связные вершины...
Можно по-конкретнее?
0
sandye51
программист С++
833 / 592 / 147
Регистрация: 19.12.2010
Сообщений: 2,016
23.12.2010, 22:46 #3
valeriikozlov, имеется ввиду смежные.
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
23.12.2010, 22:49 #4
смежные вершины и связаные вершины это разные вещи. А у Sonn ADK голос пропал? Хотелось бы услышать автора темы.
0
sandye51
программист С++
833 / 592 / 147
Регистрация: 19.12.2010
Сообщений: 2,016
23.12.2010, 22:52 #5
valeriikozlov, термина связные вершины не существует
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
23.12.2010, 22:54 #6
Связность. Две вершины в графе связаны, если существует соединяющая их (простая) цепь.
это взято отсюда:
http://ru.wikipedia.org/wiki/Подграф#.D0.9F
0
Sonn ADK
0 / 0 / 2
Регистрация: 23.12.2010
Сообщений: 11
23.12.2010, 23:08  [ТС] #7
Граф называется связным, если любая пара его вершин соединима. Вот.
Т.е. допустим вот матрица смежностей для графа из 3 точек:
010
101
010
Нулевая вершина соединена с первой, а первая в свою очередь со второй. Надо задать граф. Т.е. задать его матрицу смежностей интерактивно. В этой вот матрице должно выводиться на экран, то что связаны 0 с 1 и 2. Т.е конкретно должно выводиться 0,1,2
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
23.12.2010, 23:19 #8
Давайте теперь я задам вопросы:
1. Нужно вывести все связанные вершины, по группам несвязанными между собой?
2. если какие-либо вершины вообще не связанные ни с какими вершинами их выводить как группу или вообще не выводить?
0
sandye51
программист С++
833 / 592 / 147
Регистрация: 19.12.2010
Сообщений: 2,016
23.12.2010, 23:20 #9
имеется ввиду вывести компоненты связности в виде набора вершин
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 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 / 2
Регистрация: 23.12.2010
Сообщений: 11
23.12.2010, 23:34  [ТС] #11
valeriikozlov, нужно вывести все связные вершины просто в строчку.......если какие-либо вершины вообще не связанные ни с какими вершинами вообще не выводить
0
.4rray
8 / 8 / 2
Регистрация: 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
Эксперт С++
4683 / 2509 / 751
Регистрация: 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 / 2
Регистрация: 23.12.2010
Сообщений: 11
24.12.2010, 00:15  [ТС] #14
вообще не выводим

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

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
#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
Эксперт С++
4683 / 2509 / 751
Регистрация: 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
Sonn ADK
0 / 0 / 2
Регистрация: 23.12.2010
Сообщений: 11
24.12.2010, 00:33  [ТС] #16
valeriikozlov, Выводит вот что.
0
Sonn ADK
0 / 0 / 2
Регистрация: 23.12.2010
Сообщений: 11
24.12.2010, 00:38  [ТС] #17
вот что
0
Миниатюры
Граф задан своей матрицей смежностей, вывести на экран все связные вершины  
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 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();
}
0
24.12.2010, 07:40
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.12.2010, 07:40
Привет! Вот еще темы с решениями:

Вывести на экран вершины орграфа, смежные с данной
Вывести на экран те вершины орграфа, смежные с данной, т.е. вывести &quot;входящие&quot;...

Вывести все вершины двоичного дерева
Двоичное дерево задано в виде: m,g],s,y]] Как с помощью стека вывести это на...

Снова я со своей квадратной матрицей.
Вроде доделал программу, которая проверяет матрицу на латинский и магический...

Вывести на экран координаты элементов матрицы, которые в своей строке наименьшие
Помогите пожалуйста написать программу,которая выводит на экран координаты...


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

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

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