How to find path between two nodes on a minimum spanning tree-CodePudding

I have minimum spanning tree and I have created list of adjacency. With help of this list of adjacency I run DFS algorithm and it works correctly. Problem is that I want to get path between two nodes. Example Tree:

For example I want to get path from 4 to 6
Current output: 4-3-1-7-2-5-6
Wanted output: 4-3-5-6

Code:

void Graph::DFS(int source, int destination)
{
    Visited[source - 1] = true;

    vector<pair<int,int>> adjList = MSTAdjacencyLists[source - 1]; //first is vertice, second is weight

    cout << source << "-";
   
    for (int i = 0; i < adjList.size(); i  )
    {
        if (adjList[i].first == destination)
        {
            cout << adjList[i].first <<"\nFound!!" << endl;
            break;
        }

        if (Visited[adjList[i].first-1] == false)
        {
            DFS(adjList[i].first, destination);
        }
    }
}

I have read that DFS can be helpful but maybe there are better methods?

CodePudding user response：

Not tested cos no small test availble

bool Graph::DFS(int source, int destination) <<<<====== bool return
{
    Visited[source - 1] = true;

    vector<pair<int,int>> adjList = MSTAdjacencyLists[source - 1]; //first is vertice, second is weight

    
   
    for (int i = 0; i < adjList.size(); i  )
    {
        if (adjList[i].first == destination)
        {
            cout << adjList[i].first <<"\nFound!!" << endl;
            return true;
        }

        if (Visited[adjList[i].first-1] == false)
        {
            if(DFS(adjList[i].first, destination))
            {
                cout << source << "-";
                return true;
            }
        }
    }
    return false;
}

ie DFS indicates whether it found the destination or not, when unwinding the recursion print the path that returned true

Not sure if we need the first 'cout << source' that I moved.

CodePudding user response：

After many hours I managed to find solution. This article was very helpful for me. https://www.geeksforgeeks.org/print-the-path-between-any-two-nodes-of-a-tree-dfs/
Idea of using stack and backtracking is really smart. Code after solution:

void Graph::DFS(int source, int destination, vector<int> stack)
{
    Visited[source - 1] = true;
    stack.push_back(source);
    vector<pair<int,int>> adjList = MSTAdjacencyLists[source - 1];
   
    for (int i = 0; i < adjList.size(); i  )
    {
        if (adjList[i].first == destination)
        {
            stack.push_back(adjList[i].first);
            printPath(stack);
            return;
        }

        if (Visited[adjList[i].first-1] == false)
        {
            DFS(adjList[i].first, destination,stack);
        }
    }

    stack.pop_back();
}