0
$\begingroup$

Will u.f and u.d of a vertex in DFS traversal change if we change order of vertices in adjacency list ? I know that u.d won't change but what about u.f? u is a vertex of the graph. u.f, u.d are finish and discovery times of the vertex u respectively in Depth traversal search algorithm.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ For this question the be understandable you'll have to define what $u$ is and what u.f and u.d are. Don't assume that we followed the same class... $\endgroup$ Commented Nov 19, 2021 at 11:23
  • 1
    $\begingroup$ Is the discovery time of a vertex $u$ the same as the time at which the visit starts on $u$? $\endgroup$ Commented Nov 19, 2021 at 11:33
  • $\begingroup$ Yes discovery time is same as the time at which the first visit starts on u. $\endgroup$ Commented Nov 19, 2021 at 11:37

2 Answers 2

Reset to default
1
$\begingroup$

Both the start time and the finish time of a vertex can change when edges are examined in a different order.

Here is an example of a DFS visit starting from vertex $a$. In the figure on the left the edge $(a,b)$ is examined before the edge $(a,c)$. In the figure on the right the order is reversed. Start times are in blue, while finish times are in red.

dfs example

Improve this answer
$\endgroup$
4
  • $\begingroup$ In the left graph you first visited b and then c , and in the right one you visited c and then b (This is what I meant when we change the order of vertices in adjaceny list)but discovery and finish time of a doesn't change. $\endgroup$ Commented Nov 19, 2021 at 11:43
  • $\begingroup$ Here the discovery and finish times of b and c are changed due to the change in adjaceny list of a . But the ques is will there is any change in finish and discovery times of the vertex a if we change the order of the vertices in adjaceny list of a ? $\endgroup$ Commented Nov 19, 2021 at 11:59
  • $\begingroup$ Then the answer is "no". If pick a vertex $u$ and you only change the order in which vertices appear in the adjacency list of $u$ then the times at the visit on $u$ begins and ends won't change. The claim about the beginning time is trivial. To see that the end time is the same notice that, when the visits first encounters $u$, the status of all other vertices is the same (i.e., either fully visited, in the middle of a visit, or unvisited). $\endgroup$ Commented Nov 19, 2021 at 12:06
  • $\begingroup$ Then the portion of the DFS traversal from this moment to the instant in which the visit leaves $u$ will visit exactly the set $S$ of unvisited vertices reachable from $u$. The number $n=|S|$ of these vertices is the same in both cases. Moreover the visit on the vertices in $S$ must finish before the visit of $u$ can finish (and the visit ony other vertex not in $S$ cannot finish before the visit on $u$ finishes). Hence the end time of $u$ will be exactly $2n+1$ more than the starting time for $u$. $\endgroup$ Commented Nov 19, 2021 at 12:06
0
$\begingroup$

I can show the order's visit of vertices, using the algorithm Depth first search.

#include <iostream>
#include <vector>
using namespace std;
const int maximumSize=5;
vector<int> visited(maximumSize, 0);
vector<int> graph[maximumSize];
int vertices, edges, order;
void showContentVector(vector<int> input)
{
    for(int i=0; i<input.size(); ++i)
    {
        cout<<input[i]<<", ";
    }
    return;
}
void createGraph()
{
    cin>>vertices>>edges;
    int vertex0, vertex1;
    for(int i=1; i<=edges; ++i)
    {
        cin>>vertex0>>vertex1;
        graph[vertex0].push_back(vertex1);
        graph[vertex1].push_back(vertex0);
    }
    return;
}
void depthFirstSearch(int current, int previous, vector<int>& orderToDepth, vector<int>& orderFromDepth)
{
    if(visited[current]==1)
    {
        return;
    }
    visited[current]=1;
    ++order;
    orderToDepth[order]=current;
    for(int next : graph[current])
    {
        if(next==previous)
        {
            continue;
        }
        depthFirstSearch(next, current, orderToDepth, orderFromDepth);
    }
    orderFromDepth[order]=current;
    return;
}
int main()
{
    createGraph();
    vector<int> orderOfVisitTo(maximumSize, 0),
    vector<int> orderOfVisitFrom(maximumSize, 0);
    depthFirstSearch(1, 0, orderOfVisitTo, orderOfVisitFrom);
    cout<<"orderOfVisitTo <- ";
    showContentVector(orderOfVisitTo);
    cout<<endl<<"orderOfVisitFrom <- ";
    showContentVector(orderOfVisitFrom);
    return 0;
}

If we have the graph:

  1
 / \
2   3

orderOfVisitTo <- 0, 1, 2, 3, 0, 
orderOfVisitFrom <- 0, 0, 2, 1, 0,

If we have the graph:

  1
 / \
3   2

orderOfVisitTo <- 0, 1, 3, 2, 0, 
orderOfVisitFrom <- 0, 0, 3, 1, 0,
Improve this answer
$\endgroup$