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

Является ли граф - деревом?

08.11.2017, 13:21. Просмотров 1116. Ответов 12
Метки нет (Все метки)

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

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <windows.h>
 
using namespace std;
const int n=4;
int i, j;
//матрица смежности графа
int GM[n][n] =
{
    {0, 1, 1, 0},
    {0, 0, 1, 1},
    {1, 0, 0, 1},
    {0, 1, 0, 0}
};
//поиск в ширину
void BFS(bool *visited, int unit)
{
    int *queue=new int[n];
    int count, head;
    for (i=0; i<n; i++) queue[i]=0;
    count=0;
    head=0;
    queue[count++]=unit;
    visited[unit]=true;
    while (head<count)
    {
        unit=queue[head++];
        cout<<unit+1<<" ";
        for (i=0; i<n; i++)
            if (GM[unit][i] && !visited[i])
            {
                queue[count++]=i;
                visited[i]=true;
            }
    }
    delete []queue;
}
//главная функция
int main()
{
    setlocale(LC_ALL, "Rus");
    int start;
    cout<<"Стартовая вершина >> ";
    cin>>start;
    bool *visited=new bool[n];
    cout<<"Матрица смежности графа: "<<endl;
    for (i=0; i<n; i++)
    {
        visited[i]=false;
        for (j=0; j<n; j++)
            cout<<" "<<GM[i][j];
        cout<<endl;
    }
    cout<<"Порядок обхода: ";
    BFS(visited, start-1);
    delete []visited;
    system("pause");
}
Добавлено через 22 часа 52 минуты
Все еще не решил, все еще нужна ваша помощь
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.11.2017, 13:21
Ответы с готовыми решениями:

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

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

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

Определить, является ли дерево AVL деревом
int s, kol, sr, a; void avl(PNode ptr) { int h1 = 0, h2 = 0, i = 0; if...

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

12
Kuzia domovenok
2421 / 2151 / 525
Регистрация: 25.03.2012
Сообщений: 7,756
Записей в блоге: 1
08.11.2017, 15:33 2
попробуй ради эксперимента действовать аналогично обходу, но проверять ещё и
C++
1
2
3
4
5
6
7
8
9
10
11
12
if (GM[unit][i])
{
            if (!visited[i])
            {
                queue[count++]=i;
                visited[i]=true;
            }
            else{
                 if (!GM[i][unit])
                     is_tree=false;//!!!!!
            }
}
0
Shadow0671
1 / 1 / 1
Регистрация: 07.05.2016
Сообщений: 71
08.11.2017, 18:12  [ТС] 3
То есть, если мы посещали уже эту вершину, то мы зашли в цикл и это не дерево?

Добавлено через 15 минут
Сделал так
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <windows.h>
 
using namespace std;
const int n=4;
int i, j;
//матрица смежности графа
int GM[n][n] =
{
    {0, 1, 1, 0},
    {1, 0, 0, 1},
    {1, 0, 0, 0},
    {0, 1, 0, 0}
};
 
bool is_tree;
 
//поиск в ширину
void BFS(bool *visited, int unit)
{
    int *queue=new int[n];
    int count, head;
    for (i=0; i<n; i++) queue[i]=0;
    count=0;
    head=0;
    queue[count++]=unit;
    visited[unit]=true;
    while (head<count)
    {
        unit=queue[head++];
        cout<<unit+1<<" ";
        for (i=0; i<n; i++)
        {
            if (GM[unit][i] && !visited[i])
            {
                queue[count++]=i;
                visited[i]=true;
            }
 
            if (GM[unit][i])
            {
                if (!visited[i])
                {
                    queue[count++]=i;
                    visited[i]=true;
                }
                else
                {
                    if (!GM[i][unit])
                        is_tree=false;//!!!!!
                }
            }
        }
 
    }
    delete []queue;
}
//главная функция
int main()
{
    setlocale(LC_ALL, "Rus");
    int start;
    cout<<"Стартовая вершина >> ";
    cin>>start;
    bool *visited=new bool[n];
    cout<<"Матрица смежности графа: "<<endl;
    for (i=0; i<n; i++)
    {
        visited[i]=false;
        for (j=0; j<n; j++)
            cout<<" "<<GM[i][j];
        cout<<endl;
    }
 
 
    cout<<"Порядок обхода: ";
    BFS(visited, start-1);
    cout << endl;
    cout << "Что получилось: " << is_tree << endl;
    delete []visited;
    system("pause");
}
Не знаю правильно ли понял, но какое бы дерево я не подставлял, все равно говорит что "0" - не дерево
0
Kuzia domovenok
2421 / 2151 / 525
Регистрация: 25.03.2012
Сообщений: 7,756
Записей в блоге: 1
08.11.2017, 18:25 4
Цитата Сообщение от Shadow0671 Посмотреть сообщение
Не знаю правильно ли понял, но какое бы дерево я не подставлял, все равно говорит что "0" - не дерево

Не по теме:

потому что программист из тебя плохой. Ты не профессионал. Всё-таки алгоритмы на графах предполагают, что автор хотя бы полгода потратил на самостоятельное программирование всяких простых алгоритмов, которые бы научили его понятию "логический флаг", "переменные надо инициализировать", "а почему именно при этом условии в if..." "А что именно именяет проверка if(GM[unit][i])"и.т.д.


Зла не хватает, блин, признавайся, ты не сам писал эту программу! И вообще ты не программист! Я когда отвечал, думал, что разговариваю с создателем программы.
0
Shadow0671
1 / 1 / 1
Регистрация: 07.05.2016
Сообщений: 71
08.11.2017, 18:33  [ТС] 5
Я и не говорил что программа моя
0
Kuzia domovenok
2421 / 2151 / 525
Регистрация: 25.03.2012
Сообщений: 7,756
Записей в блоге: 1
08.11.2017, 18:34 6
Shadow0671, вор!
0
Shadow0671
1 / 1 / 1
Регистрация: 07.05.2016
Сообщений: 71
08.11.2017, 18:39  [ТС] 7
Это костыль!!! Примеров поиска в ширину много в сети. Я попросил помощи (вы то и помогли), спасибо вам за это. Но зачем разводить такой кипишь??? Не легче показать как это делается? Будет полезно мне и всем последующим кто обратиться на форум с таким же вопросом.
0
Kuzia domovenok
2421 / 2151 / 525
Регистрация: 25.03.2012
Сообщений: 7,756
Записей в блоге: 1
08.11.2017, 19:01 8
Лучший ответ Сообщение было отмечено Shadow0671 как решение

Решение

Перерд тем как копировать что-то куда-то нужно осознавать, зачем ты копируешь:
Вглядись внимательно в этот код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
if (GM[unit][i] && !visited[i])
            {
                queue[count++]=i;
                visited[i]=true;
            }
 
            if (GM[unit][i])
            {
                if (!visited[i])
                {
                    queue[count++]=i;
                    visited[i]=true;
                }
                else
                {
                    if (!GM[i][unit])
                        is_tree=false;//!!!!!
                }
            }
Если бы ты сам написал первую строчку, у тебя бы сразу возникла мысль "а чего это вдруг в седьмой строке то же самое повторяется"? Но нет, для тебя хоть первая строчка, хоть последняя - всё китайская грамота!

А ведь посмотреть на эту строчку стоило. Потому что мой код делает точно то же самое, а значит не дополняет этот блок if, а полностью заменяет его! Заменяет значит следует сделать так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
        for (i=0; i<n; i++)
        {
            if (GM[unit][i])
            {
                if (!visited[i])
                {
                    queue[count++]=i;
                    visited[i]=true;
                }
                else
                {
                    if (!GM[i][unit])
                        is_tree=false;//!!!!!
                }
            }
        }
Пробуй это, и я надеюсь, ты добавишь в нужное место кода строку is_tree=true

Добавлено через 15 минут
Вот полный код и извини за то, что ёрничаю и чешу тем самым своё ЧСВ. Но блина... чтобы даже просто скопипастить что-то в скопипащеный же ранее код, в нём же разбираться тоже надо!
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <windows.h>
 
using namespace std;
const int n = 4;
int i, j;
//матрица смежности графа
int GM[n][n] =
{
    { 0, 1, 1, 0 },
    { 1, 0, 0, 1 },
    { 1, 0, 0, 0 },
    { 0, 1, 0, 0 }
};
 
bool is_tree;
 
//поиск в ширину
void BFS()
{
    int *queue = new int[n];
    bool *visited = new bool[n];
 
    int count, head;
    for (i = 0; i<n; i++) queue[i] = 0;
    count = 0;
    head = 0;
    queue[count++] = 0;
    visited[0] = true;
    is_tree = true;
    while (head<count)
    {
        int unit = queue[head++];
        cout << unit + 1 << " ";
        for (i = 0; i<n; i++)
        {
 
            if (GM[unit][i])
            {
                if (!visited[i])
                {
                    queue[count++] = i;
                    visited[i] = true;
                }
                else
                {
                    if (!GM[i][unit])
                        is_tree = false;//!!!!!
                }
            }
        }
 
    }
    delete[]queue;
    delete[]visited;
}
//главная функция
int main()
{
    setlocale(LC_ALL, "Rus");
    cout << "Матрица смежности графа: " << endl;
    for (i = 0; i<n; i++)
    {
        for (j = 0; j<n; j++)
            cout << " " << GM[i][j];
        cout << endl;
    }
    cout << "Порядок обхода: ";
    BFS();
    cout << endl;
    cout << "Что получилось: " << (is_tree?"дерево":"не дерево") << endl;
    system("pause");
}
1
ARTER616
0 / 0 / 3
Регистрация: 14.01.2017
Сообщений: 269
19.01.2018, 22:37 9
Kuzia domovenok, А как сделать ввод N и самого массива? Мне пишет, что cin не подходит...

Добавлено через 15 минут
Kuzia domovenok, хотя бы скажите, что гуглить, потому что по моим запросам выдается чуть меньше чем ничего
0
Fulcrum_013
1477 / 1117 / 129
Регистрация: 14.12.2014
Сообщений: 9,493
Завершенные тесты: 3
19.01.2018, 22:41 10
Подсчитайте связность и цикломатическое число. Дерево есть связный граф с цикломатическим числом 0. Т.е. не нужно никуда бегать. Нужно только знать количество вершин и ребер.
0
ARTER616
0 / 0 / 3
Регистрация: 14.01.2017
Сообщений: 269
19.01.2018, 22:50 11
Fulcrum_013, ... может лучше подскажете, как тот код переделать?
0
Fulcrum_013
1477 / 1117 / 129
Регистрация: 14.12.2014
Сообщений: 9,493
Завершенные тесты: 3
19.01.2018, 22:56 12
Лучший ответ Сообщение было отмечено Новичок как решение

Решение

ARTER616, https://studopedia.ru/6_162325_tsikl...a-derevya.html
Количество ребер минус количество вершин плюс один.
Считаешь. Если не 0 то это может быть всем чем угодно кроме дерева. Если 0 то проверяешь связность если она заранее неизвестна. Если связный то таки дерево.
1
igorrr37
1907 / 1512 / 766
Регистрация: 21.12.2010
Сообщений: 2,554
Записей в блоге: 10
20.01.2018, 10:13 13
проверка на количество рёбер и компонент связности
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
 
const int n = 4;
//матрица смежности графа
int grf[n][n] =
{
    { 0, 1, 1, 0 },
    { 1, 0, 0, 1 },
    { 1, 0, 0, 0 },
    { 0, 1, 0, 0 }
};
 
//поиск в ширину
bool bfs()
{
    std::queue<int> que;
    std::vector<bool> vec(n);
    for (auto& val : vec)
    {
        val = false;
    }
    int cur = 2;
    que.push(cur);
    vec[cur] = true;
    while(!que.empty())
    {
        cur = que.front();
        que.pop();
        for (int j = 0; j < n; ++j)
        {
            if (1 == grf[cur][j] && vec.at(j) != true)
            {
                vec.at(j) = true;
                que.push(j);
            }
        }
    }
    bool ret = true;
    for (int i = 0; i < vec.size(); ++i)
    {
        if (vec[i] != true)
        {
            std::cout << "bfs() : несколько компонент связности\n";
            ret = false;
            break;
        }
    }
    return ret;
}
 
// число рёбер равно число вершин минус один
bool edges()
{
    int edges = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (grf[i][j] == 1)
            {
                ++edges;
            }
        }
    }
    edges /= 2;
    return (edges == n - 1);
}
 
int main()
{
    setlocale(LC_ALL, "Rus");
    cout << "Матрица смежности графа: " << endl;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
            cout << " " << grf[i][j];
        cout << endl;
    }
    cout << endl;
    bool b = bfs();
    bool e = edges();
    cout << "bfs(): " << std::boolalpha << b << endl;
    cout << "edges(): " << std::boolalpha << e << endl;
    cout << "\nИтог: " << (b && e ? "дерево" : "не дерево") << endl;
    //system("pause");
}
0
20.01.2018, 10:13
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.01.2018, 10:13

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

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

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


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

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

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