algorytm.org

Implementacja w C#

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Przeszukiwanie grafu wszerz (BFS) i w głąb (DFS) - Implementacja w C#
Ocena użytkownikóww: *****  / 7
SłabyŚwietny
Nadesłany przez Mateusz Zaborowski, 03 lutego 2013 05:05
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.

Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.

dfs.cs:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

//Przeszukiwanie grafu w glab
//Autor: Mateusz Zaborowski 
//www.algorytm.org
namespace ConsoleApplication5
{
    class Program
    {
        static List<int> DFS(int[][] tab, int start)
        {
            int wierzcholekStart = start - 1;
            Stack<int> stos = new Stack<int>(); //stos
            List<int> listaWynikow = new List<int>();
            stos.Push(wierzcholekStart);    //dodanie pierwszego wierzcholka
            bool[] odwiedzoneWierzcholki = new bool[tab.Length];

            while (stos.Count!=0)
            {
                int pobranyWierzcholek = stos.Pop();
                if (odwiedzoneWierzcholki[pobranyWierzcholek] == false)
                {
                    odwiedzoneWierzcholki[pobranyWierzcholek]=true;
                    for (int i = (tab[pobranyWierzcholek].Length - 1); i>=0; i--)
                    {
                        if(tab[pobranyWierzcholek][i]!=0)
                        {
                            stos.Push(i);
                        }
                    }
                    listaWynikow.Add(pobranyWierzcholek);
                }
            }
            return listaWynikow;
        }
        static void Main(string[] args)
        {
            //(odczyt z dnia 2013.02.03)Przykład ze strony: http://www.algorytm.org/algorytmy-grafowe/przeszukiwanie-grafu-wszerz-bfs-i-w-glab-dfs.html
            //DFS
            int[][] tab= {new int[] {0, 1, 1, 0, 0, 0},
                          new int[] {0, 0, 0, 1, 1, 0},
                          new int[] {0, 0, 0, 1, 0, 1},
                          new int[] {1, 0, 0, 0, 0, 0},
                          new int[] {0, 0, 0, 1, 0, 0},
                          new int[] {0, 0, 0, 0, 0, 0}};

            List<int> wynik=DFS(tab,1);
            Console.WriteLine("DFS\n");
            foreach (int wypisz in wynik)
            {
                Console.WriteLine((wypisz+1));
            }
            Console.ReadLine();
        }
    }
}
Komentarze
photo
+1 # Michał P 2013-02-22 13:37
To nie jest DFS. W linii 28 iterujesz po kolejnych wierzchołkach i sprawdzasz czy są sąsiadami jeśli tak to wrzucasz na stos jeden za drugim co jest błędne. Po wrzuceniu pierwszego na stos powinieneś od razu zająć się nim a dopiero po powrocie od niego zająć się kolejnymi sąsiadami. Oczywiście podany algorytm przeszuka całe drzewo, ale nie jest to DFS.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # Piotr G 2013-07-03 06:54
Niestety zrobiłeś przeszukiwanie grafu wszerz(BFS) a nie w głąb(DFS). A to jest duża różnica.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-6 # Człowiek 2014-04-23 19:21
Moim zdaniem samo użycie stosu implikuje DFS. Aby był to BFS należało by skorzystać z kolejki.
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz