C# Learning

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

Ας δούμε τα βασικά χαρακτηριστικά και τη λειτουργία του αλγορίθμου BFS:

1. Αρχικός Κόμβος (Πηγή): Ο αλγόριθμος ξεκινάει από έναν αρχικό κόμβο ή κόμβο πηγή.
2. Εξερεύνηση Επίπεδο-Επίπεδο: Αρχίζει να επεκτείνει την αναζήτησή του σε όλους τους γείτονες του αρχικού κόμβου πριν προχωρήσει στους γείτονες των γειτόνων του. Αυτό σημαίνει ότι πρώτα εξετάζει όλους τους κόμβους ενός επιπέδου, και μετά προχωρά στο επόμενο επίπεδο.
3. Ουρά (Queue): Για την υλοποίηση του BFS χρησιμοποιείται μια ουρά (queue). Ο αρχικός κόμβος τοποθετείται στην ουρά, και στη συνέχεια οι γείτονές του προστίθενται στην ουρά. Έτσι, ο αλγόριθμος επεξεργάζεται τους κόμβους σύμφωνα με τη σειρά που εισήχθησαν στην ουρά (FIFO – First In First Out).
4. Σημείο Σταματήματος: Η αναζήτηση συνεχίζει μέχρι να εξεταστούν όλοι οι κόμβοι του γράφου ή δέντρου ή μέχρι να βρεθεί ο στόχος (αν αναζητούμε κάποιο συγκεκριμένο στοιχείο).
5. Εφαρμογές: Ο BFS χρησιμοποιείται για εύρεση συντομότερου μονοπατιού σε ανιοντίνα γραφήματα, για αναζήτηση σε δέντρα, για εύρεση συνδεδεμένων συνιστωσών σε ένα γράφο, κ.λπ.

Αυτός είναι ο βασικός τρόπος λειτουργίας του αλγορίθμου BFS. Χρησιμοποιείται ευρέως για την εξερεύνηση δομών δεδομένων που έχουν δομή “επίπεδο-επίπεδο” όπως γράφους και δέντρα.

Ο αλγόριθμος αναζήτησης κατά πλάτος (Breadth-First Search – BFS) είναι ένας αλγόριθμος που χρησιμοποιείται για να εξερευνήσει όλους τους κόμβους ενός γράφου ή ενός δέντρου, επίπεδο-επίπεδο, ξεκινώντας από έναν αρχικό κόμβο (ή κόμβο πηγή). Ας δούμε τα βήματα και τα βασικά στοιχεία που συνθέτουν το BFS:

1. Ουρά (Queue): Ο κύριος μηχανισμός του BFS είναι η χρήση μιας ουράς (queue). Ο αρχικός κόμβος (ή κόμβος πηγή) τοποθετείται στην ουρά. Στην αρχή, η ουρά είναι άδεια, οπότε προσθέτουμε τον αρχικό κόμβο στην ουρά.

1. Εξερεύνηση Επίπεδο-Επίπεδο: Ο BFS εξερευνά όλους τους γείτονες του τρέχοντος κόμβου πριν προχωρήσει στους γείτονες των γειτόνων του. Αυτό σημαίνει ότι εξετάζει όλους τους κόμβους σε ένα επίπεδο του γράφου προτού προχωρήσει στο επόμενο επίπεδο.

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

1. Σημείο Σταματήματος: Η αναζήτηση συνεχίζεται μέχρι να εξεταστούν όλοι οι κόμβοι του γράφου ή δέντρου, ή μέχρι να βρεθεί ο στόχος αναζήτησης (αν υπάρχει στόχος). Αυτό σημαίνει ότι ο BFS δεν σταματά πριν εξερευνήσει όλους τους πιθανούς κόμβους.

1. Χρονική Πολυπλοκότητα: Η χρονική πολυπλοκότητα του BFS είναι O(V + E), όπου V είναι ο αριθμός των κόμβων και E είναι ο αριθμός των ακμών του γράφου ή του δέντρου.

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

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

Η Breadth-First Search (BFS) ή Αναζήτηση Κατά Πλάτος είναι μια αλγοριθμική τεχνική για την εξερεύνηση ή αναζήτηση σε γραφήματα και δέντρα. Χρησιμοποιείται για να βρείτε την πιο κοντινή ή την πιο σύντομη διαδρομή σε ένα γράφο, να εντοπίσετε επίπεδα κόμβων ή να βρείτε σύνθετα μοτίβα. Εδώ είναι κάποιες περιπτώσεις όπου είναι ιδιαίτερα χρήσιμο να χρησιμοποιήσετε το BFS:

Πότε Χρησιμοποιούμε το BFS:

1. Εύρεση Σύντομης Διαδρομής:
   • Όταν θέλουμε να βρούμε τη συντομότερη διαδρομή από έναν κόμβο σε έναν άλλο σε ένα γράφο με ακμές ίσου βάρους (π.χ., σε ένα δίκτυο δρόμων όπου όλοι οι δρόμοι έχουν την ίδια απόσταση).

1. Εύρεση Επίπεδων Κόμβων:
   • Όταν θέλουμε να βρούμε όλους τους κόμβους που βρίσκονται σε μια συγκεκριμένη απόσταση από τον αρχικό κόμβο. Αυτό είναι χρήσιμο για την ανάλυση κοινωνικών δικτύων ή άλλων δομών με επίπεδα.

1. Εύρεση Όλων των Δρόμων:
   • Όταν χρειάζεται να βρείτε όλους τους δρόμους (διαδρομές) που οδηγούν σε έναν προορισμό ή να εντοπίσετε όλους τους κόμβους που είναι προσβάσιμοι από έναν συγκεκριμένο κόμβο.

1. Αναγνώριση Συνδεδεμένων Συστάδων:
   • Στη χρήση του BFS για την ανάλυση συνδεδεμένων συνόλων σε γραφήματα, το BFS μπορεί να βοηθήσει στην αναγνώριση των συνδεδεμένων συστάδων κόμβων.

1. Εύρεση Κύκλων:
   • Για την ανίχνευση κύκλων σε ακαθόριστους γράφους, το BFS μπορεί να χρησιμοποιηθεί για να βρει αν υπάρχει κύκλος και πόσος είναι ο μικρότερος κύκλος.

1. Εφαρμογές σε Παιχνίδια:
   • Σε παιχνίδια ή προβλήματα σχεδίασης λαβυρίνθου, το BFS μπορεί να χρησιμοποιηθεί για να βρείτε την πιο σύντομη διαδρομή ή να εξερευνήσετε περιοχές του παιχνιδιού.

Πώς Λειτουργεί το BFS:

1. Ξεκινάς από έναν Αρχικό Κόμβο:
   • Το BFS ξεκινά από έναν αρχικό κόμβο και εξερευνά όλα τα γειτονικά του κόμβους πριν προχωρήσει στους επόμενους κόμβους.

1. Χρησιμοποιείς Μια Ουρά:
   • Το BFS χρησιμοποιεί μια δομή δεδομένων τύπου Queue (ουρά) για να κρατήσει τους κόμβους που πρέπει να εξεταστούν. Στη γλώσσα προγραμματισμού C#, μπορείς να χρησιμοποιήσεις την κλάση Queue<T> για αυτόν τον σκοπό.

1. Επισκέπτεσαι Κόμβους Επίπεδα-Επίπεδα:
   • Επισκέπτεσαι πρώτα όλους τους κόμβους στο επίπεδο των γειτόνων του αρχικού κόμβου, έπειτα προχωράς στους γειτονικούς κόμβους των κόμβων του πρώτου επιπέδου, και ούτω καθεξής.

1. Ενημερώνεις τη Στοίβα:
   • Όταν επισκέπτεσαι έναν κόμβο, προσθέτεις όλους τους γειτονικούς του κόμβους στην ουρά, ώστε να εξεταστούν αργότερα.

Παράδειγμα BFS

Ας δούμε ένα απλό παράδειγμα για να κατανοήσεις καλύτερα το BFS:

      A
     /|\
    B C D
   /|   \
  E F    G

• Ξεκινάς από τον κόμβο A.

• Βάζεις τους γειτονικούς κόμβους B, C, και D στην ουρά.

• Επισκέπτεσαι A και προχωράς στους κόμβους της ουράς (δηλαδή, B, C, και D).

• Εξετάζεις B και προσθέτεις τους γειτονικούς του κόμβους E και F στην ουρά.

• Εξετάζεις C (χωρίς πρόσθετους γειτονικούς κόμβους) και προχωράς σε D (με γειτονικό κόμβο G).

• Συνεχίζεις με όλους τους κόμβους στην ουρά μέχρι να εξαντληθούν.

Αυτή είναι η βασική θεωρία πίσω από την αναζήτηση κατά πλάτος (BFS). Αν έχεις οποιαδήποτε ερώτηση ή χρειάζεσαι περισσότερες λεπτομέρειες, είμαι εδώ για να βοηθήσω!

Διαδικασία BFS(αρχικός_κόμβος)    Αρχή        Δημιουργία ουράς Q        Δημιουργία πίνακα επισκέφθηκε με τιμές Ψευδής για όλους τους κόμβους        Επισκέφθηκε[αρχικός_κόμβος] ← Αληθής        Q.Προσθήκη(αρχικός_κόμβος)        Ενώ Q δεν είναι κενή            κόμβος ← Q.Αφαίρεση()            Εκτύπωσε(κόμβος)            Για κάθε γείτονας του κόμβου                Αν επισκέφθηκε[γείτονας] = Ψευδής τότε                    Επισκέφθηκε[γείτονας] ← Αληθής                    Q.Προσθήκη(γείτονας)                Τέλος_αν            Τέλος_για        Τέλος_ενώ    Τέλος

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 BFS(int startVertex)
    {
        bool[] visited = new bool[Vertices];
        Queue<int> queue = new Queue<int>();

        visited[startVertex] = true;
        queue.Enqueue(startVertex);

        while (queue.Count > 0)
        {
            int vertex = queue.Dequeue();
            Console.Write(vertex + " ");

            foreach (int neighbor in adj[vertex])
            {
                if (!visited[neighbor])
                {
                    visited[neighbor] = true;
                    queue.Enqueue(neighbor);
                }
            }
        }
    }

    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 Breadth First Traversal " +
                          "(starting from vertex 2)");

        g.BFS(2);
    }
}