Как изменить алгоритм BFS, чтобы найти путь между 2 вершинами с заданным условием? - PullRequest
Новая
       109

Как изменить алгоритм BFS, чтобы найти путь между 2 вершинами с заданным условием?

0 голосов
/ 26 мая 2019

Я только начал изучать графики и застрял в этой проблеме.Я пытаюсь найти кратчайший путь (минимальное количество ребер) между двумя вершинами графа с условием, что между каждыми 2 промежуточными вершинами пути есть 2 альтернативных пути (не имеет значения длина).

Это мой алгоритм BFS.Цвета означают:

  • белый = еще не достигнут

  • серый = достигнутая вершина останется таким цветом, пока все его соседи не будутбыть достигнутым

  • черный = достигнутые вершины

pi[] содержит родителя текущей вершины 

void bfs(int s)
{
    int i;

    for (i=1; i<=v; i++)
    {
        if (i != s)
        {
            color[i] = WHITE;
            d[i] = INFTY;
            pi[i] = NIL;
        }
    }
    color[s] = GRAY;
    d[s] = 0;
    pi[s] = NIL;
    queueInit(&q);
    queuePush(&q,s);
    while (!queueEmpty(&q))
    {
        int u = queueFront(&q);
        int j;
        for (j=1; j<=adj[u][0]; j++)
        {
            int x = adj[u][j];
            if (color[x] == WHITE)
            {
                color[x] = GRAY;
                d[x] = d[u]+1;
                pi[x] = u;
                queuePush(&q,x);
            }
        }
        queuePop(&q);
        color[u] = BLACK;
    }
}

Пожалуйстапомогите мне изменить алгоритм, чтобы найти кратчайший путь с заданным условием, или хотя бы дайте мне совет!

1 Ответ

1 голос
/ 26 мая 2019

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

Я также не понимаю строку for (j=1; j<=adj[u][0]; j++), которая зацикливается на смежных вершинах.

Реализация алгоритмов BFS из cp-алгоритмы : 

vector<vector<int>> adj;  // adjacency list representation
int n; // number of nodes
int s; // source vertex

queue<int> q;
vector<bool> used(n);
vector<int> d(n), p(n);

q.push(s);
used[s] = true;
p[s] = -1;
while (!q.empty()) {
    int v = q.front();
    q.pop(); // The node should be poped before looping on it's adjacent nodes
    for (int u : adj[v]) {
        if (!used[u]) {
            used[u] = true;
            q.push(u);
            d[u] = d[v] + 1;
            p[u] = v;
        }
    }
}

А затем, скажем, мы хотим напечатать кратчайший путь: 

if (!used[u]) {
    cout << "No path!";
} else {
    vector<int> path;
    for (int v = u; v != -1; v = p[v])
        path.push_back(v);
    reverse(path.begin(), path.end());
    cout << "Path: ";
    for (int v : path)
        cout << v << " ";
}
...