840 / 498 / 325
Регистрация: 29.12.2009
Сообщений: 1,106
1

Лабораторная работа по теории графов. Поиск в глубину. Критика

04.04.2015, 20:08. Показов 1405. Ответов 0
Метки нет (Все метки)

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

Древесные ребра - ребра, которые мы обходим в результате работы алгоритма.
Компонента связности графа

Вот код:
Матрица смежности считывается из файла.
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
#include <boost/numeric/ublas/matrix.hpp>
#include <boost/numeric/ublas/io.hpp>
 
namespace ublas = boost::numeric::ublas;
 
// структура "ребро"
// begin - начальная вершина ребра
// end - конечная вершина ребра
struct edge
{
    int begin;
    int end;
    edge (int _begin, int _end)
    {
        begin = _begin;
        end = _end;
    }
};
 
void DFS (ublas::matrix<int> & matrix_adjacency, 
          std::vector<bool> & visited,
          std::vector<edge> & tree_edges,
          int start)
{
    visited[start] = true;
    for (int i = 0; i < matrix_adjacency.size1(); i++)
    {
        if (!visited[i] && matrix_adjacency(start, i))
        {
            tree_edges.push_back(edge(start + 1, i + 1));
            DFS (matrix_adjacency, visited, tree_edges, i);
        }
    }
}
 
void erase_from_vector (std::vector<int> & all_ver, edge & tree_edge)
{
    auto i1 = find (all_ver.begin(), all_ver.end(), tree_edge.begin - 1);
    if (i1!=all_ver.end())
        all_ver.erase(i1);
    i1 = find (all_ver.begin(), all_ver.end(), tree_edge.end - 1);
    if (i1!=all_ver.end())
        all_ver.erase(i1);
}
 
int main()
{
    ublas::matrix<int> matrix_adjacency;
    std::ifstream file ("file");
    if (file.is_open())
    {
        if (file >> matrix_adjacency)
        {
            int start = 0;
            
            // массив посещенных вершин
            std::vector<bool> visited (matrix_adjacency.size1());
            
            // массив древесных ребер
            std::vector<edge> tree_edges;
            
            // массив всех вершин
            std::vector<int> all_ver (matrix_adjacency.size1());
            for (int i = 0; i < matrix_adjacency.size1(); i++)
                all_ver[i] = i;
                
            // число компонент связности
            int components = 1;
            
            std::cout << "Список древесных ребер\n";
            do
            {
                DFS (matrix_adjacency, visited, tree_edges, start);
                for (int i = 0; i < tree_edges.size(); i++)
                {
                    std::cout << "(" << tree_edges[i].begin << "," << tree_edges[i].end <<")\n";
                    // удаляем из массива ребер пройденные вершины
                    erase_from_vector(all_ver, tree_edges[i]);
                }
                // если прошли все вершины графа, то выходим
                if (all_ver.empty())
                {
                    break;
                }
                else
                {
                    // иначе, остались еще компоненты связности
                    start = all_ver[0];
                    tree_edges.clear();
                    ++components;
                }
            }
            while (true);
          
            std::cout << "Число компонент связности: " << components 
                      << std::endl;
        }
        else
            std::cout << "Возникли ошибки при чтении файла\n";
    }
    return 0;
}
Данный граф представлен на картинке. Черными стрелками показаны древесные ребра

Прошу сказать, что где некорректно реализовано. Где можно было написать более рационально и просто
покритиковать программу
Миниатюры
Лабораторная работа по теории графов. Поиск в глубину. Критика   Лабораторная работа по теории графов. Поиск в глубину. Критика  
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
04.04.2015, 20:08
Ответы с готовыми решениями:

Лаб. работа по теории графов
Суть такая - даны графы (во вложении) Связный граф 1) Найти кратчайший путь из вершины x в...

по теории графов
Помогите пожалуйста

Задачи по теории графов
1. Может ли полный граф иметь 7, 8, 9, или 10 ребер?

Задача по теории графов
Здравствуйте! Не могли бы вы помочь решить одну задачу по теории графов! есть входный файл, в...

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
04.04.2015, 20:08
Помогаю со студенческими работами здесь

задача из теории графов
Объясните как решать следующую задачу: Есть некоторые группы станков : N1 станков 1-ого типа,N2...

Элементы теории графов на С++
Привет всем, вынужден просить помощи в написании программы, по графам :) Собственно вот оно...

Элементы теории графов
Помогите ответить на эти вопросы заранее большое спасибо. (надеюсь на вас просто у меня ещё 2...

Элементы теории графов
Задан неориентированный граф без петель из пяти вершин строками полуматрицы смежности в виде...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru