Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

орграф на Borland С++

65K
18 апреля 2011 года
sveta11115
10 / / 18.04.2011
Помогите, пожалуйста, с задачей на C++:
Нужно с использованием рекурсии.

Задан орграф. Известны веса рёбер. Найти путь из i в j с min суммой весов рёбер.
Спасибо.
278
18 апреля 2011 года
Alexander92
1.1K / / 04.08.2008
Алгоритм Дейкстры с обходом графа в глубину. Вернусь домой - напишу, если до меня никто не отпишется.
65K
18 апреля 2011 года
sveta11115
10 / / 18.04.2011
Спасибо, буду ждать.
Алгоритм Дейкстры смотрела, но через рекурсию не нашла.
278
19 апреля 2011 года
Alexander92
1.1K / / 04.08.2008
Для неориентированного графа реализация примерно следующая:

Код:
#include <iostream>
#include <vector>
using namespace std;

#define INFINITY 1000

class CEdge {
public:
    CEdge() : begin(0), end(0), weight(0), used(false) {}
    ~CEdge() {}

    int begin;
    int end;
    int weight;
    bool used;
};

class CVerticle {
public:
    CVerticle() : metrics(0) {edges.resize(0);}
    ~CVerticle() {edges.resize(0);}

    vector<int> edges;
    int metrics;
};

vector<CVerticle> verticles(0);
vector<CEdge> edges(0);

void dfs(int index) {
    int i = 0;
    int next_index = 0;

    for (i = 0; i < verticles[index].edges.size(); i++) {
        next_index = (index == edges[verticles[index].edges].begin) ? edges[verticles[index].edges].end : edges[verticles[index].edges].begin;
        if (edges[verticles[index].edges].used) continue;
        if (verticles[index].metrics + edges[verticles[index].edges].weight < verticles[next_index].metrics)
            verticles[next_index].metrics = verticles[index].metrics + edges[verticles[index].edges].weight;
        edges[verticles[index].edges].used = true;
        dfs(next_index);
    }
}

int main(void) {
    int i = 0;
    int verticlesNum = 0, edgesNum = 0;
    int begin = 0, end = 0;

    cout << "Number of verticles: ";
    cin >> verticlesNum;
    cout << "Number of edges: ";
    cin >> edgesNum;
    verticles.resize(verticlesNum);
    edges.resize(edgesNum);

    cout << "Enter " << edgesNum << " edges in format [begin] [end] [weight]:" << endl;
    for (i = 0; i < edgesNum; i++) {
        cin >> edges.begin;
        cin >> edges.end;
        cin >> edges.weight;
        verticles[edges.begin].edges.push_back(i);
        verticles[edges.end].edges.push_back(i);
    }

    cout << "Enter the first verticle of the path: ";
    cin >> begin;
    cout << "Enter the last verticle of the path: ";
    cin >> end;

    for (i = 0; i < verticles.size(); i++)
        verticles.metrics = (i == begin) ? 0 : INFINITY;

    dfs(begin);
    cout << verticles[end].metrics << endl;

    return 0;
}


Скорее всего, можно еще оптимизировать, но суть описал.

verticles - массив вершин графа, edges - массив ребер, begin - начальная вершина, end - конечная вершина. Чтобы превратить это в орграф, достаточно при переходе от вершины к вершине проверять не только наличие ребра между ними, а и направление перехода.

P.S. Если поймаете ошибку в вычислениях - подправим. Говорю честно, писал сравнительно быстро.
65K
19 апреля 2011 года
sveta11115
10 / / 18.04.2011
спасибо, а для ориентированного?
278
19 апреля 2011 года
Alexander92
1.1K / / 04.08.2008
Писал ведь. :)

[QUOTE=Alexander92]
Чтобы превратить это в орграф, достаточно при переходе от вершины к вершине проверять не только наличие ребра между ними, а и направление перехода.
[/QUOTE]
65K
19 апреля 2011 года
sveta11115
10 / / 18.04.2011
Ой, спасибо,не заметила.
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог