Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
girlwithoutname
1 / 1 / 0
Регистрация: 19.12.2010
Сообщений: 37
1

Является ли граф связанным

12.11.2011, 23:48. Просмотров 1162. Ответов 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
#include "stdafx.h"
#include <iostream>
#define n 4
using namespace std;
 
int _tmain(int argc, _TCHAR* argv[])
{
    struct graf
    {
        int ver1,ver2;
    };
    graf g[n];
    int A[k];
    for (int i=0;i<n;i++)
    {
        cout<<"vvedite pervuyu vershinu ";
        cin>>g[i].ver1;
        cout<<"vvedite vtoruyu vershinu ";
        cin>>g[i].ver2;
    }
system ("PAUSE");
    return 0;
}
Не могу придумать как записать.
Знаю что нужно хоть бы для одной доказать что из неё можно попасть во все, тогда граф связен.
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.11.2011, 23:48
Ответы с готовыми решениями:

Определить, является ли граф связанным
помогите пожалуйста: определить является ли связанным граф на си

Является ли граф деревом
Суть задачи заключается в том, что нужно проверить граф, является ли он деревом. Граф является...

Является ли граф - деревом?
Доброго времени суток. Есть граф, нужно пробежаться по нему в ширину, и если не встретится циклов,...

Проверить является ли граф циклом
Добрый день, форумчане. Помогите пожалуйста со следующей задачей: Дан ориентированный граф из n...

Определить, является ли граф двудольным
ьсчььсь

2
amor1k
Студент
148 / 148 / 64
Регистрация: 18.01.2011
Сообщений: 469
13.11.2011, 00:24 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
bool Graph::Connect()
{
    int * len_rout = new int[n];
    int * ver = new int[n];
    int * queue = new int[n];
    int * visited = new int[n];
    for(int i = 0; i < n; i++) visited[i] = 0;
    queue[0] = 0;
    visited[0] = 1;
    int r = 0, w = 1;
    len_rout[0] = 0;
    ver[0] = 0;
    while (r < w) { 
        int curr = queue[r++];
        for (int i = 0; i < n; i++) 
        {
            if (!visited[i] && a[curr][i]) {
                visited[i] = 1;
                len_rout[w] = len_rout[r-1] + 1;
                ver[w] = curr;
                queue[w++] = i;
            }
        }
    }
    int i = 0;
    while(visited[i] && i < n) i++;
    delete visited;
    delete queue;
    delete len_rout;
    delete ver;
    if(i < n) return false;
    return true;
}
измените под себя
2
girlwithoutname
1 / 1 / 0
Регистрация: 19.12.2010
Сообщений: 37
13.11.2011, 21:44  [ТС] 3
а можешь рассказать где что? пожалуйста
0
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.11.2011, 21:44

Дан неориентированный граф. Необходимо определить, является ли он деревом
Дан неориентированный граф. Необходимо определить, является ли он деревом. Формат входных данных...

Проверить, является ли ориентированный граф, с заданным количеством узлов и рёбер, деревом
Дан ориентированный граф из n узлов и m рёбер. Проверить, является ли он деревом. Помогите...

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


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

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

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