Depth First Traversal

When a dead end occurs in any iteration, the Depth First Search (DFS) method traverses a network in a depthward motion and uses a stack to remember to acquire the next vertex to start a search.

Depth First Travesal

As in the example given above, DFS algorithm traverses from S to A to D to G to E to B first, then to F and lastly to C. It employs the following rules.

  • Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Push it in a stack.
  • Rule 2 − If no adjacent vertex is found, pop up a vertex from the stack. (It will pop up all the vertices from the stack, which do not have adjacent vertices.)
  • Rule 3 − Repeat Rule 1 and Rule 2 until the stack is empty.
StepTraversalDescription
1Depth First Search Step OneInitialize the stack.
2Depth First Search Step TwoMark S as visited and put it onto the stack. Explore any unvisited adjacent node from S. We have three nodes and we can pick any of them. For this example, we shall take the node in an alphabetical order.
3Depth First Search Step ThreeMark A as visited and put it onto the stack. Explore any unvisited adjacent node from A. Both S and D are adjacent to A but we are concerned for unvisited nodes only.
4Depth First Search Step FourVisit D and mark it as visited and put onto the stack. Here, we have B and C nodes, which are adjacent to D and both are unvisited. However, we shall again choose in an alphabetical order.
5Depth First Search Step FiveWe choose B, mark it as visited and put onto the stack. Here B does not have any unvisited adjacent node. So, we pop B from the stack.
6Depth First Search Step SixWe check the stack top for return to the previous node and check if it has any unvisited nodes. Here, we find D to be on the top of the stack.
7Depth First Search Step SevenOnly unvisited adjacent node is from D is C now. So we visit C, mark it as visited and put it onto the stack.
Because C has no unvisited neighboring nodes, we continue to pop the stack until we discover a node with an unvisited adjacent node. There are none in this situation, therefore we keep popping until the stack is empty.
0

119 thoughts on “Depth First Traversal”

  1. Hey very cool blog!! Man .. Beautiful .. Amazing .. I’ll bookmark your website and take the feeds also…I’m happy to find numerous useful info here in the post, we need work out more techniques in this regard, thanks for sharing. . . . . .

    0
  2. It’s a shame you don’t have a donate button! I’d without a doubt donate to this superb blog! I suppose for now i’ll settle for bookmarking and adding your RSS feed to my Google account. I look forward to fresh updates and will talk about this site with my Facebook group. Talk soon!

    0
  3. I’m still learning from you, but I’m improving myself. I certainly enjoy reading everything that is written on your site.Keep the stories coming. I enjoyed it!

    0
  4. Thanks for another fantastic post. The place else could anyone get that type of info in such a perfect means of writing? I’ve a presentation next week, and I am at the search for such info.

    0
  5. An interesting discussion is worth comment. I think that you should write more on this topic, it might not be a taboo subject but generally people are not enough to speak on such topics. To the next. Cheers

    0
  6. Thanks for sharing superb informations. Your web site is very cool. I am impressed by the details that you have on this website. It reveals how nicely you perceive this subject. Bookmarked this web page, will come back for more articles. You, my friend, ROCK! I found just the info I already searched everywhere and just couldn’t come across. What a great website.

    0
  7. Hiya, I am really glad I have found this information. Nowadays bloggers publish just about gossips and net and this is really irritating. A good blog with interesting content, that is what I need. Thank you for keeping this website, I’ll be visiting it. Do you do newsletters? Can’t find it.

    0
  8. hello!,I like your writing so so much! share we be in contact more about your post on AOL? I need a specialist on this house to resolve my problem. Maybe that is you! Having a look ahead to look you.

    0
  9. With almost everything that appears to be developing within this subject material, many of your points of view happen to be quite radical. Nevertheless, I beg your pardon, because I do not subscribe to your whole plan, all be it exciting none the less. It would seem to us that your comments are generally not completely justified and in simple fact you are your self not really completely certain of the point. In any case I did enjoy reading it.

    0
  10. Admiring the time and energy you put into your blog and detailed information you provide. It’s nice to come across a blog every once in a while that isn’t the same unwanted rehashed information. Wonderful read! I’ve saved your site and I’m adding your RSS feeds to my Google account.
    cloudbet countries

    0
  11. zeolite heavy equipment llc is a trusted provider of heavy equipment, offering a diverse range of machines and devices for various industries. We strive to meet the needs of our customers by providing them with reliable solutions and excellent service. Our company is dedicated to helping our customers succeed in their business ventures.

    0
  12. Its like you read my mind! You seem to know so much about this, like you wrote the book in it or something. I think that you could do with some pics to drive the message home a bit, but other than that, this is excellent blog. An excellent read. I will certainly be back.
    instant payid pokies australia

    0
  13. Aviator Spribe казино играть на доллары
    Between us speaking, I advise to you to try to look in google.com
    Добро пожаловать в захватывающий мир авиаторов! Aviator – это увлекательная игра, которая позволит вам окунуться в атмосферу боевых действий на небе. Необычные графика и захватывающий сюжет сделают ваше путешествие по воздуху неповторимым.

    Откройте для себя новые возможности с игрой Aviator Spribe казино играть прямо сейчас!
    Aviator игра позволит вам почувствовать себя настоящим пилотом. Вам предстоит совершить невероятные маневры, выполнять сложные задания и сражаться с противниками. Улучшайте свой самолет, чтобы быть готовым к любым ситуациям и становиться настоящим мастером.
    Основные особенности Aviator краш игры:
    1. Реалистичная графика и физика – благодаря передовой графике и реалистичной физике вы почувствуете себя настоящим пилотом.
    2. Разнообразные режимы игры и миссии – в Aviator краш игре вы сможете выбрать различные режимы игры, такие как гонки, симулятор полетов и захватывающие воздушные бои. Кроме того, каждая миссия будет предлагать свои собственные вызовы и задачи.
    3. Улучшение и модернизация самолетов – в игре доступны различные модели самолетов, которые можно покупать и улучшать. Вы сможете устанавливать новое оборудование, улучшать двигательность и мощность своего самолета, а также выбирать различные варианты окраски и декорации.
    Aviator краш игра – это возможность испытать себя в роли авиатора и преодолеть все сложности и опасности воздушного пространства. Почувствуйте настоящую свободу и адреналин в Aviator краш игре онлайн!
    Играйте в «Авиатор» в онлайн-казино Pin-Up
    Aviator краш игра онлайн предлагает увлекательную и захватывающую игровую атмосферу, где вы становитесь настоящим авиатором и сражаетесь с самыми опасными искусственными интеллектами.
    В этой игре вы должны показать свое мастерство и смекалку, чтобы преодолеть сложности многочисленных локаций и уровней. Вам предстоит собирать бонусы, уклоняться от препятствий и сражаться с врагами, используя свои навыки пилотирования и стрельбы.
    Каждый уровень игры Aviator краш имеет свою уникальную атмосферу и задачи. Будьте готовы к неожиданностям, так как вас ждут захватывающие повороты сюжета и сложные испытания. Найдите все пути к победе и станьте настоящим героем авиатором!
    Авиатор игра является прекрасным способом провести время и испытать настоящий адреналиновый разряд. Готовы ли вы стать лучшим авиатором? Не упустите свой шанс и начните играть в Aviator краш прямо сейчас!
    Aviator – играй, сражайся, побеждай!
    Aviator Pin Up (Авиатор Пин Ап ) – игра на деньги онлайн Казахстан
    Aviator игра предлагает увлекательное и захватывающее разнообразие врагов и уровней, которые не оставят равнодушными даже самых требовательных геймеров.
    Враги в Aviator краш игре онлайн представлены в самых разных формах и размерах. Здесь вы встретите группы из маленьких и быстрых врагов, а также огромных боссов с мощным вооружением. Разнообразие врагов позволяет игрокам использовать разные тактики и стратегии для победы.
    Кроме того, Aviator игра предлагает разнообразие уровней сложности. Выберите легкий уровень, чтобы насладиться игровым процессом, или вызовите себе настоящий вызов, выбрав экспертный уровень. Независимо от выбранного уровня сложности, вы получите максимум удовольствия от игры и окунетесь в захватывающий мир авиаторов.
    Играйте в Aviator и наслаждайтесь разнообразием врагов и уровней, которые позволят вам почувствовать себя настоящим авиатором.

    0
  14. When I initially commented I clicked the “Notify me when new comments are added” checkbox and now each time a comment is added I get three e-mails with the same comment. Is there any way you can remove people from that service? Bless you!

    0
  15. Ваш надежный партнер Пункт приема Металла в Алматы Наша компания предлагает высококачественные услуги по приему, сортировке и переработке металлических отходов. Мы гарантируем прозрачные условия сотрудничества, конкурентоспособные цены и оперативное обслуживание.

    0

Leave a Comment

Your email address will not be published. Required fields are marked *