Pergunta

I'm working on graphs and traversal techniques. However, i have a question about adjacency list. As you know in adjacency method you declare an array or a list for each vertex which keeps adjacent vertexes. So my question is "does adding order of adjacent vertexes has any effects on depth first search". Let me be more clear. Consider that i have graph this:

0 : 1 -> 2
1 : 0 -> 3
2 : 0 -> 3
3 : 1 -> 2 -> 4
4 : 3 -> 5 -> 6
5 : 4
6 : 4

and consider i made a few changes on it like;

0 : 2 -> 1
1 : 0 -> 3
2 : 3 -> 0
3 : 1 -> 2 -> 4
4 : 6 -> 5 -> 3
5 : 4
6 : 4

so i recognized that in depth first search (for example) the search order changes logically. But is this situation affects the performance of searching or is it same ? I hope i had been clear on my question and also i will appreciate for every answer. ( i use an undirected graph )

Foi útil?

Solução

The time complexity of a depth first search is O(V+E) which is the no. of vertexes plus the no. of egdes so i think no..

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top