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

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

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

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

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

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

Является ли граф связанным - C++
Дан список ребер, можно матрицей смежности. Определить связен ли граф. #include "stdafx.h" #include <iostream> #define n 4 using...

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

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

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

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

Определить, является ли текст является записью четного числа в семеричной системе - 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();
}
0
dxdy
97 / 97 / 5
Регистрация: 14.06.2010
Сообщений: 283
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
Привет! Вот еще темы с ответами:

Определить, является ли значение целочисленной переменной х четным. Если является, то вывести на печать значен - C++
Определить, является ли значение целочисленной переменной х четным. Если является, то вывести на печать значение х, в противном случае...

Определить изоморфен ли граф своему дополнению - C++
Добрый день. Существует ли какой либо критерий для неориентированных графов. В данном случае есть граф и есть его дополнение нужно...

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

Определить степени вершин графа и если граф однородный - вывести степень однородности - C++
Помогите пожалуйста с кодом - на входе у нас есть файл с параметрами графа вида: n m v1 u1 v2 u2 .... vm um Здесь n -...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
08.05.2013, 20:46
Ответ Создать тему
Опции темы

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