Herzlich Willkommen, lieber Gast!
  Sie befinden sich hier:

  Forum » C / C++ (GNU/Linux, *NIX, *BSD und Co) » Breitensuche mit Queue

Forum | Hilfe | Team | Links | Impressum | > Suche < | Mitglieder | Registrieren | Einloggen
  Quicklinks: MSDN-Online || STL || clib Reference Grundlagen || Literatur || E-Books || Zubehör || > F.A.Q. < || Downloads   

Autor Thread - Seiten: > 1 <
000
06.05.2014, 20:36 Uhr
platins



Hallo ich versuche die Breitensuche mit der Warteschlange zu implementieren. Die Implementierung habe ich durch Pseudocode geschrieben. Ich weiß aber nicht wie ich die Elemente für die Ausgabe einbringe. Bitte euch um Vervollständigung des Quellcodes. Danke im Voraus..

C++:
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <string>

#define N 10
#define WEISS -1
#define GRAU 0
#define SCHWARZ 1

using namespace std;

const int anz = 5;

struct Knoten
{
    int farbe;
    char name;

struct Graph
{
    int adjmatr[N][N];
    Knoten v[N];
    int knotenanz;
};

struct Queue
{
    int q[N];
    int kopf;
    int ende;
    int laenge;
    int anzahl;
};

void enqueue(Queue *qu, int x);
int dequeue(Queue *qu);
void bfs(Graph g, int s);
void ausgabe(Graph g);


void enqueue(Queue *qu, int x)
{
    qu->q[qu->ende] = x;

    if(qu->ende == (qu->laenge)-1)
    {
        qu->ende = 0;
    }

    else
    {
        qu->ende = (qu->ende) + 1;
    }

    qu->anzahl = qu->anzahl + 1;
}

int dequeue(Queue *qu)
{
    int x;

    x = qu->q[qu->kopf];

    if(qu->kopf == (qu->laenge)-1)
    {
        qu->kopf = 0;
    }

    else
    {
        qu->kopf = (qu->kopf) + 1;
    }

    qu->anzahl = qu->anzahl - 1;

    return x;
}

void bfs(Graph g, int s)
{
    Queue q;
    int u;
    int laeufe = 0;

    q.kopf = 0;
    q.ende = 0;
    q.laenge = N;
    q.anzahl = 0;

    for(int z = 0; z < g.knotenanz; z++)
    {
        g.v[z].farbe = WEISS;
    }

    g.v[s].farbe = GRAU; // 0 = grau

    enqueue(&q, s);

    //u = s;

    while(q.anzahl != 0)
    {
        laeufe = laeufe + 1;

        cout << "Lauf " << laeufe << ": ";
        for(int z = q.kopf; z < q.ende; z++)
        {
            cout << g.v[q.q[z]].name;
        }
        cout << endl;

        u = dequeue(&q);

        for(int z = 0; z < g.knotenanz; z++)
        {
            if(g.adjmatr[u][z] == 1)
            {
                if(g.v[z].farbe == WEISS)
                {
                    g.v[z].farbe = GRAU;
                    enqueue(&q, z);
                }
            }
        }

        g.v[u].farbe = SCHWARZ;
    }

    cout << endl;
}


---
Edit: cpp-Tags eingefügt.

Dieser Post wurde am 06.05.2014 um 23:31 Uhr von Hans editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
001
06.05.2014, 23:34 Uhr
Hans
Library Walker
(Operator)


Hi,

Zitat von platins:

Hallo ich versuche die Breitensuche mit der Warteschlange zu implementieren. Die Implementierung habe ich durch Pseudocode geschrieben.


das sieht aber nicht gerade nach Pseudo-code aus, was Du hier eingestellt hast.


Zitat von platins:

Ich weiß aber nicht wie ich die Elemente für die Ausgabe einbringe.


Da wäre die Frage zu klären, was Du genau ausgeben willst. Solange Du das selbst nicht weisst, kann Dir auch keiner einen Tip dazu geben, wie Du es ausgeben könntest.
Im übrigen fehlt in dem Code die main()-Funktion, die mit den gegebenen Funktionen und Daten überhaupt erst mal irgendwas macht. Und schliesslich, da es sich um C++ handelt: die #defines sollte man in C++ durch const int oder einem anderen geeigneten Typ ersetzen, der ebenfalls const ist.


Zitat von platins:

Bitte euch um Vervollständigung des Quellcodes.


darauf kannst Du lange warten! - Siehe hier, warum; - auch wenn es nicht um Hausaufgaben gehen sollte.

Hans
--
Man muss nicht alles wissen, aber man sollte wissen, wo es steht. Zum Beispiel hier: Nachdenkseiten oder Infoportal Globalisierung.

Dieser Post wurde am 06.05.2014 um 23:54 Uhr von Hans editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
Seiten: > 1 <     [ C / C++ (GNU/Linux, *NIX, *BSD und Co) ]  


ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: