Przepisanie algorytmu do cpp

Mam do przepisania ten algorytm z pascala do cpp, Depth First Search Algorithm, Nie wiem co robie źlę, wynik w ogóle się nie pojawia, doradzi ktos?

DFS-Visit(G, u)
 begin
   color(u) := szary;
   for each v ∈ Adj[u] do
     if kolor(v) = biały then DFS-Visit(G, v);
   color(u) := czarny;
 end;

using namespace std;
#include <list>
#include <iostream>

void print(list<int> &lista)
{
  for (auto const &i: lista) {
        cout << i << endl;
    }
}

void DFS_Visit(string *kolor, list<int> Adj, int u)
{
  kolor[u] = "szary";
  for (int i = 0; i < Adj.size(); i++)
  {
    if (kolor[i] == "bialy")
    {
      DFS_Visit(&kolor[i], Adj, u);
    }
  }
    kolor[u] = "czarny";
}

int main()
{

  int n = 8;
  int u = 0;
  list<int> *Adj = new list<int>[n];
  Adj[0].push_back(1);
  Adj[0].push_back(4);
  Adj[1].push_back(0);
  Adj[1].push_back(2);
  Adj[1].push_back(7);
  Adj[2].push_back(1);
  Adj[2].push_back(4);
  Adj[2].push_back(5);
  Adj[3].push_back(4);
  Adj[4].push_back(0);
  Adj[4].push_back(2);
  Adj[4].push_back(3);
  Adj[4].push_back(5);
  Adj[5].push_back(2);
  Adj[5].push_back(4);
  Adj[5].push_back(6);
  Adj[6].push_back(5);
  Adj[6].push_back(7);
  Adj[7].push_back(1);
  Adj[7].push_back(6);
  string *kolor = new string[n];
  for (int i = 0; i < n; i++){kolor[i] = "bialy";}
  DFS_Visit(kolor, *Adj, u);
  print(*Adj);
  delete[] kolor;
  delete[] Adj;
  return 0;
}

Jak to działa z tymi kolorami? W Paskalu przekazujesz do funkcji graf, (co tam stoi za tym G?) a w C++ kolor i listę.

• Do kolorowania nie musisz używać stringów. Polecam enuma.
• list<int> *Adj = new list<int>[n]; Alokowanie tej listy jest bez sensu. Użyj std::vector<std::list<int>>>. A najlepiej użyj std::vector<std::vector<int>>>
• Tu jest błąd : DFS_Visit(&kolor[i], Adj, u);. Powinieneś przekazać cała tablicę, a nie &kolor[i] Zdajesz sobie sprawę, że w ten sposób przekazujesz tablicę przesuniętą o i? Czyli w którymś momencie wyjdziesz poza zakres tablicy.
• I żeby było zabawnie, jest tu ( DFS_Visit(&kolor[i], Adj, u); ) też drugi błąd. Powinieneś przekazać w argumencie element listy Adj[u], czyli wierzchołek docelowy. Ty przekazuje wierzchołek źródłowy. Standardowo w literaturze nazywa się te wierzchołki u i v. Ale w implementacji warto je nazwać np. src i dst. Od razu zauważyłbyś błąd.
• if (kolor[i] == "bialy") Tu też błąd. i nic nie znaczy. powinno być if (kolor[v] == "bialy"), gdzie v jest elementem listy Adj[u]
• void DFS_Visit(string *kolor, list<int> Adj, int u) - Wiesz, że przekazujesz listę przez wartość i robisz jej kopię? Wiesz, że powinieneś przekazać wszystkie listy sąsiedztwa, a nie tylko tą wierzchołka 0?
• Naucz się debugować swój program. Debugger to podstawa.

@Descendant: Kiedyś się bawiłem grafami w C++, obczaj:
https://bitbucket.org/lion137/graphs_c/src/master/

Nie ogarniam kompletnie tej funkcji DFS_Visit..

using namespace std;
#include <list>
#include <iostream>
#include <vector>

void print(vector<std::list<int>> Adj)
{
for (const std::list<int>& lst : Adj) {
   for (int i : lst) { 
      cout << i << '\n';
   }
}
}

void DFS_Visit(string *kolor, vector<std::list<int>> Adj, int u)
{
  kolor[u] = "szary";
  for (int i = 0; i < Adj.size(); i++)
  {
    if (kolor[u] == "bialy")
    {
      DFS_Visit(kolor, Adj, i);
    }
  }
  kolor[u] = "czarny";
}

int main()
{

  int n = 8;
  int u = 0;
  std::vector<std::list<int>> Adj = {
      {1, 4},
      {0, 2, 7},
      {1, 4, 5},
      {4},
      {0, 2, 3, 5},
      {2, 4, 6, 5},
      {7},
      {1, 6},
  };
    string *kolor = new string[n];

  for (int i = 0; i < n; i++)
  {
    kolor[i] = "bialy";
  }
  DFS_Visit(kolor, Adj, u);
  print(Adj);
  delete[] kolor;
  return 0;
}

Nie tylko funkcji, z podstawami c++ też jest problem.

Minimalna ilość kodu do poprawienia tego co masz:

enum class Color : int {White, Gray, Black};

void dfs_visit(vector<Color> &color, vector<vector<int>> &adj, int u)
{
    color[u] = Color::Gray;
    for (int v : adj[u]) {
        if (color[v] == Color::White) {
            dfs_visit(color, adj, v);
        }
    }
    color[u] = Color::Black;
}

Czego nie rozumiesz w algorytmie?

@nalik: A co wtedy z tym zrobić?

   string *kolor = new string[n];

  for (int i = 0; i < n; i++)
  {
    kolor[i] = "bialy";
  }
  DFS_Visit(kolor, Adj, u);

W którym miejscu powinienem wywoływać print(*Adj)? Bo teraz tylko printuje co jest w Adj[0]

using namespace std;
#include <list>
#include <iostream>

void print(list<int> &lista)
{
  for (auto const &i : lista)
  {
    cout << i << endl;
  }
}

void DFS_Visit(string *kolor, list<int> Adj, int u)
{
  kolor[u] = "szary";
  string bialy = "bialy";
  for (int v = 0; v < Adj.size(); v++)
  {
    if (kolor[v] == bialy)
    {
      DFS_Visit(&kolor[v], Adj, v);
    }
  }
  kolor[u] = "czarny";
}

int main()
{

  int n = 8;
  int u = 0;
  list<int> *Adj = new list<int>[n];
  Adj[0].push_back(1);
  Adj[0].push_back(4);
  Adj[1].push_back(0);
  Adj[1].push_back(2);
  Adj[1].push_back(7);
  Adj[2].push_back(1);
  Adj[2].push_back(4);
  Adj[2].push_back(5);
  Adj[3].push_back(4);
  Adj[4].push_back(0);
  Adj[4].push_back(2);
  Adj[4].push_back(3);
  Adj[4].push_back(5);
  Adj[5].push_back(2);
  Adj[5].push_back(4);
  Adj[5].push_back(6);
  Adj[6].push_back(5);
  Adj[6].push_back(7);
  Adj[7].push_back(1);
  Adj[7].push_back(6);
  string *kolor = new string[n];
  for (int i = 0; i < n; i++)
  {
    kolor[i] = "bialy";
  }
  DFS_Visit(kolor, *Adj, u);
  print(*Adj);

  delete[] kolor;
  delete[] Adj;
  return 0;
}

Descendant napisał(a):

W którym miejscu powinienem wywoływać print(*Adj)? Bo teraz tylko printuje co jest w Adj[0]

Wg mnie w dowolnym miejscu, tam gdzie chcesz to zrobić.
Jak chcesz wydrukować całą tablicę to bez dwóch pętli ani rusz.

@Descendant: Rozumiesz istotę przeszukiwania grafu? Najbardziej ogólnie, przeszukajmy graf używając abstrakcyjnej struktury, bag - dodajemy do niej elementy i w dowolny sposób wyciągamy, daje to nam AFS - Arbitrary First Search:

def AFS(G, s):
    bag.add(v)
    while bag is not empty:
        v = bag.pop()  # nie ma znaczenia w jaki sposób dostajemy element
        if v is unmarked:
            mark(v)
            for w in adj(v):
                bag.add(w)

Teraz, jeśli bag = LIFO # lifo stack, last in first out, mamy DFS, skoro większośc języków ma wbudowany stos- rekurencja + przejście na obiektowość:

def dfs(G, v):  # recursive
    if G.is_marked(v) is False:
        G.mark(v)
        for w in G.adj_list(v):
            dfs(G, w)

Żródło:

https://github.com/lion137/Python-Graph