Печать самого длинного пути в неориентированном графике - PullRequest
Новая
       76

Печать самого длинного пути в неориентированном графике

0 голосов
/ 19 февраля 2019

Я использую этот код https://www.geeksforgeeks.org/longest-path-undirected-tree/, чтобы найти самый длинный путь в неориентированном графе.Код использует поиск BFS дважды, чтобы найти самый длинный путь, а затем выводит начало и конец пути и длину.Как я могу сохранить путь в списке и распечатать его?Я сохраняю предшественников в массиве int predecessors[n], но, конечно, это не дает пути.Я знаю, что каким-то образом мне следует изменить pred[V], чтобы он хранил список предшественников, но я не знаю, как это реализовать.Любая помощь приветствуется. 

// C++ program to find longest path of the tree 
#include <bits/stdc++.h> 
using namespace std; 
// This class represents a undirected graph using adjacency list 
class Graph { 
    int V;              // No. of vertices 
    list<int> *adj;     // Pointer to an array containing adjacency lists 

public: 
    Graph(int V);              // Constructor 
    void addEdge(int v, int w);// function to add an edge to graph 
    void longestPathLength();  // prints longest path of the tree 
    pair<int, int> bfs(int u); // function returns maximum distant 
                               // node from u with its distance 
}; 
Graph::Graph(int V) 
{ 
    this->V = V; 
    adj = new list<int>[V]; 
} 
void Graph::addEdge(int v, int w) 
{ 
    adj[v].push_back(w);    // Add w to v’s list. 
    adj[w].push_back(v);    // Since the graph is undirected 
}

// метод возвращает самый дальний узел и его расстояние от узла u 

pair<int, int> Graph::bfs(int u) 
{ 
    //  mark all distance with -1 
    int dis[V]; 
    int pred[V];  \\ I added this to store predecessors
    memset(dis, -1, sizeof(dis)); 
    queue<int> q; 
    q.push(u);

    dis[u] = 0;       //  distance of u from u will be 0 
    pred[u] = {u};  // I added this line

    while (!q.empty()) 
    { 
        int t = q.front();       q.pop(); 
        //  loop for all adjacent nodes of node-t 
        for (auto it = adj[t].begin(); it != adj[t].end(); it++) 
        { 
            int v = *it; 
            cout << "adjacent node:" << v << endl;
            // push node into queue only if it is not visited already 
            if (dis[v] == -1) 
            { 
                q.push(v); 
                // make distance of v, one more than distance of t 
                dis[v] = dis[t] + 1; 
                cout << "parent of adjacent node:" << t << endl;
                pred[v] = t // store the predecessor of v
            } 
        } 
    } 
    int maxDis = 0; 
    int nodeIdx; 
    //  get farthest node distance and its index 
    for (int i = 0; i < V; i++) 
    { 
        if (dis[i] > maxDis) 
        { 
            maxDis = dis[i]; 
            nodeIdx = i; 
        } 
    } 
    return make_pair(nodeIdx, maxDis); 
}

// метод печатает самый длинный путь данного дерева 

void Graph::longestPathLength() 
{ 
    pair<int, int> t1, t2; 

    // first bfs to find one end point of longest path
    t1 = bfs(0); 

    //  second bfs to find actual longest path 
    t2 = bfs(t1.first); 

    cout << "Longest path is from " << t1.first << " to "
         << t2.first << " of length " << t2.second; 
}

// Код драйвера для проверки вышеуказанных методов 

int main() 
{ 
    // Create a graph given in the example 
    Graph g(10); 
    g.addEdge(0, 1); 
    g.addEdge(1, 2); 
    g.addEdge(2, 3); 
    g.addEdge(2, 9); 
    g.addEdge(2, 4); 
    g.addEdge(4, 5); 
    g.addEdge(1, 6); 
    g.addEdge(6, 7); 
    g.addEdge(6, 8); 

    g.longestPathLength(); 
    return 0; 
}

// Результат: 

Longest path is from 5 to 7 of length 5

1 Ответ

0 голосов
/ 19 февраля 2019

V не является константой, поэтому int dis[V]; недопустимо.Это C ++, а не C.

Вам нужно найти способ вернуть pred из bfs().Вы можете:

  • объявить pred в Graph
  • локально в longestPathLength() и изменить bfs(), чтобы принять дополнительный аргумент pred
  • локально в bfs() и вернуть его вместе с pair<int, int>: pair<pair<int, int>, PRED_T> или tuple<int, int, PRED_T>

Imo объявить pred внутри bfs() - лучший способ сделать это.Здесь я использую vector<int> для dis и pred. 

class Graph {
...
    pair<pair<int, int>, vector<int>> bfs(int u);
};

pair<pair<int, int>, vector<int>> Graph::bfs(int u) 
{ 
    //  mark all distance with -1 
    vector<int> dis(V, -1);

    vector<int> pred(V);

    queue<int> q;
    ...
                dis[v] = dis[t] + 1;
                pred[v] = t; // store the predecessor of v
            }
    ...
    return make_pair(make_pair(nodeIdx, maxDis), pred);
}

void Graph::longestPathLength() 
{ 
    pair<int, int> t1, t2;

    // first bfs to find one end point of longest path
    t1 = bfs(0).first;

    //  second bfs to find actual longest path 
    auto res = bfs(t1.first); // or  pair<pair<int, int>, vector<int>> res
    t2 = res.first; 

    cout << "Longest path is from " << t1.first << " to "
         << t2.first << " of length " << t2.second << endl;

    // Backtrack from t2.first to t1.first
    for (int t = t2.first; t != t1.first; t = res.second[t]) // `res.second` is `pred`
        cout << t << " ";
    cout << t1.first << endl;
}
...