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

Двудольный граф - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
timchuchok
15 / 15 / 0
Регистрация: 21.12.2010
Сообщений: 55
03.06.2011, 00:16     Двудольный граф #1
Здравстувйте, нужна помощь, часть задания выполнил, а вот основное - не получается.
Нужно проверить является ли граф двудольным, на форму прчоитал, что делается это так:
Граф двудольный тогда и только тогда когда все циклы четны. Решается за один обход в глубину. На каждом шаге обхода в глубину метим вершину. Допустим мы пошли в первую вершину - добавляем ее в первую группу. То есть ставим метку один. Затем просматриваем все смежные вершины и если не помечена вершина, то метим ее как 2(то есть запихиваем в противоположную группу) и и рекурсивно переходим в нее. Если же она мечена и у нее такая же метка как у нашей - то все граф не двудольный.
Мой код прилагается, функция proc() должна дать ответ, двудольный граф или же нет, как просто обойти граф я знаю, но мне нужно еще и помечать, в какую группу отнести вершину, для этого обьявить структуру из двух полей? ( отмеченаня ли вершина и в какой группе находится)?

class.h
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
typedef unsigned int uint;
const uint INFTY = UINT_MAX;
 
class Gra
{
protected:
    uint n, m; //кількість вершин та ребер
public:
    Gra() : n(0) , m(0) {}
    virtual bool input(char *) = 0;
    virtual void output(char *) = 0;
};
 
typedef struct Node   //для зображення графа структурою суміжності
{
    uint v;
    Node *next;
} *PNode, **PPNode;
 
class Grl : public Gra
{
protected:
    PPNode E;
    bool addArc(uint, uint); //додавання ребра, допоміжна функція
public:
    bool input(char * );
    void output(char * );
    bool proc();
};
class.cpp
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
#include <iostream>
#include <fstream>
#include "class.h"
 
using namespace std;
 
bool Grl::input( char *FN)
{
    uint i,j;
    ifstream f(FN);
    if (!f)
    {
        cout<<"FIle problems\n";
        return false;
    }
    f>>n>>m;
    //ініціалізація графа як порожнього
    E = new PNode[n];
    if(!E)
    {
        cout<<"Free memory problems\n";
        return false;
    }
    for(int cnt = 0; cnt < n; cnt++)
        E[cnt] = NULL;
    //введення ребер
    for(int cnt = 0; cnt < m; cnt++)
    {
        f>>i>>j;
        if(!addArc(i,j)) 
            return false;
    }
    f.close();
    return true;
}
 
bool Grl::addArc( uint i, uint j)
{
    PNode p = new Node;
    if (!p) 
        return false;
    p->v = j;
    p->next = E[i];
    E[i] = p;
    return true;
}
 
void Grl::output(char *FN)
{
    ofstream f(FN);
    f<<n<<' '<<m<<'\n';
    PNode p;
    for(int i = 0; i < n; i++)
    {
        p = E[i]; //початок списку 
        while(p)
        {
            f<<i<<' '<<p->v;
            f<<'\n';
        }
        p = p->next;
    }
    f.close();
 
}
 
bool Grl::proc()
{
 
}
main.cpp
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <fstream>
#include <locale.h>
#include "class.h"
 
using namespace std;
 
int main()
{
    Grl graph;
    setlocale(LC_ALL, "Rus");
    cout<<"Enter filename\n";
    char filename[15];
    cin>>filename;
    if (!graph.input(filename))
    {
        system("pause");
        return 0;
    }
    graph.proc();
    system("pause");
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.06.2011, 00:16     Двудольный граф
Посмотрите здесь:

C++ Граф
Граф C++
C++ Граф
C++ Двудольный граф??
Граф C++
C++ Граф в С
Граф C++
Двудольный граф C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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