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

определить является ли связанным граф - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.65
MAKS8780
1 / 1 / 0
Регистрация: 10.07.2010
Сообщений: 3
10.07.2010, 17:05     определить является ли связанным граф #1
помогите пожалуйста: определить является ли связанным граф на си
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 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();
}
dxdy
 Аватар для dxdy
97 / 97 / 5
Регистрация: 14.06.2010
Сообщений: 283
10.07.2010, 17:55     определить является ли связанным граф #3
Можно двумя способами проверить, что граф связанный.
1 способ Берем любую вершину и с этой вершины пытаемся обойти всех его сыновей. Все вершины, которые мы будем обходить заносим в стек, затем когда обход будет завершен, мы достаем все точки из стека и считаем их количество, если количество будет равно количеству вершин в графе, то граф считается связанным.
2 способ У нас имеется матрица смежности, по которому строится граф. Пусть матрица смежности имеет N вершин. Не будем забывать, что 1 вершина без путей тоже является связанным графом, поэтому по главной диагонали матрицы смежности ставим 1. Затем данную матрицу будем возводим в N степень, хотя результат может быть уже известен и на шаге меньше, чем N. После возведения матрицы в N степень мы должны получить матрицу, состоящая из одних 1. Ели это условие выполняется, то граф связанный.
Lonter
1 / 1 / 0
Регистрация: 22.04.2013
Сообщений: 45
08.05.2013, 20:46     определить является ли связанным граф #4
объясните откуда берется visited?
Yandex
Объявления
08.05.2013, 20:46     определить является ли связанным граф
Ответ Создать тему
Опции темы

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