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

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

10.07.2010, 17:05. Просмотров 2586. Ответов 3
Метки нет (Все метки)

помогите пожалуйста: определить является ли связанным граф на си
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.07.2010, 17:05
Ответы с готовыми решениями:

Является ли граф связанным
Дан список ребер, можно матрицей смежности. Определить связен ли граф. ...

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

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

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

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

3
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,292
10.07.2010, 17:10 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
34
35
36
#include <iostream>
#include <conio.h>
 
using namespace std;
 
int n;
int g[1000][1000];
bool visited[1000];
 
void dfs(int v)
{
    if(visited[v])
        return;
    visited[v] = true;
    for(int i = 0; i < n; i++)
        if(g[v][i])
            dfs(i);
}
 
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> g[i][j];
    dfs(0);
    for(int i = 0; i < n; i++)
        if(!visited[i])
        {
            cout << "No";
            getch();
            return 0;
        }
    cout << "Yes";  
    getch();
}
0
dxdy
97 / 97 / 14
Регистрация: 14.06.2010
Сообщений: 284
10.07.2010, 17:55 3
Можно двумя способами проверить, что граф связанный.
1 способ Берем любую вершину и с этой вершины пытаемся обойти всех его сыновей. Все вершины, которые мы будем обходить заносим в стек, затем когда обход будет завершен, мы достаем все точки из стека и считаем их количество, если количество будет равно количеству вершин в графе, то граф считается связанным.
2 способ У нас имеется матрица смежности, по которому строится граф. Пусть матрица смежности имеет N вершин. Не будем забывать, что 1 вершина без путей тоже является связанным графом, поэтому по главной диагонали матрицы смежности ставим 1. Затем данную матрицу будем возводим в N степень, хотя результат может быть уже известен и на шаге меньше, чем N. После возведения матрицы в N степень мы должны получить матрицу, состоящая из одних 1. Ели это условие выполняется, то граф связанный.
0
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
08.05.2013, 20:46 4
объясните откуда берется visited?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.05.2013, 20:46

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

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

Определить, является ли текст является записью четного числа в семеричной системе
В заданный непустой текст входят только цифры и буквы. Определить,...


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

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

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