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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.65
MAKS8780
1 / 1 / 0
Регистрация: 10.07.2010
Сообщений: 3
#1

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

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

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

C++ Граф задан мартрицей весов.Нужно определить ребра с максимальным весом и удалить их
C++ Определить, является ли x четным
C++ Является ли граф связанным
C++ Структуры. Присвоить значение переменной a и всем объектам, с ней связанным
C++ Определить степени вершин графа и если граф однородный - вывести степень однородности
C++ Работа со связанным списком (смена двух чисел местами в списке)
Является ли граф деревом C++
Определить изоморфен ли граф своему дополнению C++
C++ Определить, является ли граф двудольным
C++ Проверить, является ли ориентированный граф, с заданным количеством узлов и рёбер, деревом
Проверить является ли граф циклом C++
Определить, является ли значение целочисленной переменной х четным. Если является, то вывести на печать значен C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Хохол
Эксперт 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     определить является ли связанным граф
Ответ Создать тему
Опции темы

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