Ο αλγόριθμος αναζήτησης κατά βάθος (Depth-First Search, DFS) είναι ένας αλγόριθμος που χρησιμοποιείται για να εξερευνήσει όλους τους κόμβους ενός γράφου ή ενός δέντρου, κατευθυνόμενος προς τα κάτω στη δομή τους όσο το δυνατόν βαθύτερα προτού επιστρέψει πίσω και εξετάσει άλλες κατευθύνσεις

νας γράφος στη θεωρία γράφων είναι ένα μαθηματικό μοντέλο που αποτελείται από σύνολο κόμβων και σύνολο ακμών που συνδέουν αυτούς τους κόμβους. Οι κόμβοι αναπαριστούν αντικείμενα ή σημεία, ενώ οι ακμές αναπαριστούν τις σχέσεις ή τις συνδέσεις μεταξύ αυτών των αντικειμένων.

Ο αλγόριθμος αναζήτησης κατά βάθος (DFS) είναι ένας τρόπος να εξερευνήσουμε έναν γράφο ή ένα δέντρο, κινούμενοι κατευθείαν προς τα κάτω στη δομή τους όσο το δυνατόν βαθύτερα προτού επιστρέψουμε πίσω και εξετάσουμε άλλες κατευθύνσεις. Ας εξηγήσουμε αυτόν τον αλγόριθμο λεπτομερέστερα:

Ανάλυση του Αλγορίθμου DFS:
- Ξεκινάμε από έναν αρχικό κόμβο του γράφου ή του δέντρου.
- Επισκεπτόμαστε τον αρχικό κόμβο και τον σημειώνουμε ως επισκεπτόμενο.
- Για κάθε γειτονικό κόμβο του τρέχοντος κόμβου, επιλέγουμε έναν και καλούμε τον εαυτό μας αναδρομικά για να επισκεφτούμε αυτόν τον γειτονικό κόμβο.
- Συνεχίζουμε αυτήν τη διαδικασία μέχρι να μην υπάρχουν άλλοι γειτονικοί κόμβοι να επισκεφτούμε.
- Όταν φτάσουμε σε έναν κόμβο όπου δεν υπάρχουν πλέον γειτονικοί κόμβοι προς αναζήτηση, επιστρέφουμε στον προηγούμενο κόμβο για να συνεχίσουμε την αναζήτηση.

Εφαρμογή σε Γράφους και Δέντρα:

Σε έναν μη κατευθυνόμενο γράφο, ο DFS μπορεί να χρησιμοποιηθεί για να βρει όλους τους κόμβους που είναι προσβάσιμοι από έναν αρχικό κόμβο.
Σε ένα κατευθυνόμενο γράφο, μπορεί να χρησιμοποιηθεί για να βρει όλους τους κόμβους που είναι προσβάσιμοι από έναν αρχικό κόμβο, ακολουθώντας τις κατευθύνσεις των ακμών.
Σε δέντρα, ο DFS εξερευνά όλους τους κόμβους, ξεκινώντας από τη ρίζα και κατευθυνόμενος προς τα παιδικά κόμβους μέχρι να φτάσει σε φύλλα.

Αυτός ο αλγόριθμος είναι χρήσιμος για πολλούς τύπους αναζητήσεων και διαδρομών σε δομές δεδομένων όπως γράφους και δέντρα, καθώς επιτρέπει την αποτελεσματική αναζήτηση και εξερεύνηση των δεδομένων.

Παράδειγμα σε Ψευδογλώσσα: Αναδρομική Υλοποίηση

Διαδικασία DFS(κόμβος, επισκέφθηκε)
    Αρχή
        Αν επισκέφθηκε[κόμβος] = Αληθής Τότε
            Επιστροφή
        Τέλος_Αν

        Εκτύπωσε(κόμβος)
        επισκέφθηκε[κόμβος] ← Αληθής

        Για κάθε γείτονας του κόμβος
            DFS(γείτονας, επισκέφθηκε)
        Τέλος_Για
    Τέλος

Μη Αναδρομική Υλοποίηση (με στοίβα)

Διαδικασία DFS(αρχικός κόμβος)
    Αρχή
        Στοίβα ← νέα κενή στοίβα
        επισκέφθηκε ← πίνακας[Μέγεθος του γραφήματος] με Αρχική Τιμή Ψευδής

        Στοίβα.Σπρώξε(αρχικός κόμβος)

        Ενώ η Στοίβα δεν είναι κενή
            κόμβος ← Στοίβα.Εξαγωγή()

            Αν επισκέφθηκε[κόμβος] = Ψευδής Τότε
                Εκτύπωσε(κόμβος)
                επισκέφθηκε[κόμβος] ← Αληθής

                Για κάθε γείτονας του κόμβος
                    Αν επισκέφθηκε[γείτονας] = Ψευδής Τότε
                        Στοίβα.Σπρώξε(γείτονας)
                    Τέλος_Αν
                Τέλος_Για
            Τέλος_Αν
        Τέλος_Ενώ
    Τέλος

Αναζήτηση-Κατά-Βάθος-Depth-First-Search-σε-Ψευδογλώσσα-και-C Download

Μη-Αναδρομική-Υλοποίηση-με-στοίβα Download

Παράδειγμα σε C#: Αναδρομική Υλοποίηση

using System;
using System.Collections.Generic;

class Graph
{
    private int Vertices;
    private List<int>[] adj;

    public Graph(int vertices)
    {
        Vertices = vertices;
        adj = new List<int>[vertices];
        for (int i = 0; i < vertices; i++)
        {
            adj[i] = new List<int>();
        }
    }

    public void AddEdge(int v, int w)
    {
        adj[v].Add(w);
    }

    public void DFS(int v)
    {
        bool[] visited = new bool[Vertices];
        DFSUtil(v, visited);
    }

    private void DFSUtil(int v, bool[] visited)
    {
        visited[v] = true;
        Console.Write(v + " ");

        foreach (int neighbour in adj[v])
        {
            if (!visited[neighbour])
            {
                DFSUtil(neighbour, visited);
            }
        }
    }

    static void Main()
    {
        Graph g = new Graph(4);

        g.AddEdge(0, 1);
        g.AddEdge(0, 2);
        g.AddEdge(1, 2);
        g.AddEdge(2, 0);
        g.AddEdge(2, 3);
        g.AddEdge(3, 3);

        Console.WriteLine("Following is Depth First Traversal " +
                          "(starting from vertex 2)");

        g.DFS(2);
    }
}

Μη Αναδρομική Υλοποίηση (με στοίβα)

using System;
using System.Collections.Generic;

class Graph
{
    private int Vertices;
    private List<int>[] adj;

    public Graph(int vertices)
    {
        Vertices = vertices;
        adj = new List<int>[vertices];
        for (int i = 0; i < vertices; i++)
        {
            adj[i] = new List<int>();
        }
    }

    public void AddEdge(int v, int w)
    {
        adj[v].Add(w);
    }

    public void DFS(int v)
    {
        bool[] visited = new bool[Vertices];
        Stack<int> stack = new Stack<int>();

        stack.Push(v);

        while (stack.Count != 0)
        {
            v = stack.Pop();

            if (!visited[v])
            {
                Console.Write(v + " ");
                visited[v] = true;
            }

            foreach (int neighbour in adj[v])
            {
                if (!visited[neighbour])
                {
                    stack.Push(neighbour);
                }
            }
        }
    }

    static void Main()
    {
        Graph g = new Graph(4);

        g.AddEdge(0, 1);
        g.AddEdge(0, 2);
        g.AddEdge(1, 2);
        g.AddEdge(2, 0);
        g.AddEdge(2, 3);
        g.AddEdge(3, 3);

        Console.WriteLine("Following is Depth First Traversal " +
                          "(starting from vertex 2)");

        g.DFS(2);
    }
}

C# Learning

Αναζήτηση Κατά Βάθος (Depth-First Search)