BFS, DFS, macierz sąsiedztwa, lista sąsiedztwa

#include <iostream>
#include <ctime>
#include <stdlib.h>
#include <queue>
using namespace std;

const int N = 5;
int graf[N][N];
int waga[N][N];
int odwiedzony[N]= {0}; //0 nieodwiedzony, 1 odwiedzony
queue<int> Q;


void wpisz()
{
    srand (time(NULL));
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            graf[i][j] = rand() % 2;
}

void losuj_waga()
{
    srand (time(NULL));
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            if(graf[i][j] == 1)
                waga[i][j] = rand()%9 + 1;
}

struct lista{
    lista *next;
    int id;
};

lista **lista_sasiedztwa;
lista *tail = 0;


void tworz_liste()
{
    cout<<endl;
    //tworze tablice list
    lista_sasiedztwa = new lista * [N];
    for(int i = 0; i < N; i++)
        lista_sasiedztwa[i] = NULL;
    lista *p, *q;
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            if(graf[i][j] == 1) //jesli sa polaczone to dodaje na koniec listy o indeksie i
            {
                p = new lista;
                p->id = j;
                if(tail==NULL)
                {
                    lista_sasiedztwa[i] = p;
                    tail = lista_sasiedztwa[i];
                    tail->next = 0;
                }
                else
                {
                    tail->next = p;
                    tail = p;
                    tail->next = 0;
                }
            }
        }
        tail = 0;
    }
    //wypisuje kazda liste
    for(int i = 0; i < N; i++)
    {
        p = lista_sasiedztwa[i];
        cout<<"["<<i<<"] ";
        while(p!=NULL)
        {
            cout << p->id<<" -> ";
            p = p->next;
        }
        cout << endl;
    }
}

void drukuj()
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
            cout<< graf[i][j]<<" ";
        cout<<endl;
    }
    cout<<endl<<endl;
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
            cout<< waga[i][j]<<" ";
        cout<<endl;
    }
}

int dd[N];
int prev[N];
//BFS DLA MACIERZY SASIEDZTWA
void BFS(int s)
{
    cout<<endl;
    for(int i = 0; i < N; i++)
        if(i != s)
        {
            odwiedzony[i] = 0;
            dd[i] = -1;
        }
    cout<<s<<" ";
    odwiedzony[s] = 1;
    dd[s] = 0;
    prev[s] = -1;
    Q.push(s);
    while(!Q.empty())
    {
        int u = Q.front();
        for(int i = 0; i < N; i++)
            if(odwiedzony[i] == 0 && graf[u][i] == 1)
            {
                odwiedzony[i] = 1;
                dd[i] = dd[u] + 1;
                prev[i] = u;
                Q.push(i);
                cout<<i<<" ";
            }
        Q.pop();
    }
    for(int i = 0; i < N; i++)
        odwiedzony[i] = 0;
}

//BFS DLA LIST SASIEDZTWA
void BFS2(int s)
{
    cout<<endl;
    lista *p;
    for(int i = 0; i < N; i++)
        if(i != s)
        {
            odwiedzony[i] = 0;
            dd[i] = -1;
        }
    cout<<s<<" ";
    odwiedzony[s] = 1;
    dd[s] = 0;
    prev[s] = -1;
    Q.push(s);
    while(!Q.empty())
    {
        int u = Q.front();
        p = lista_sasiedztwa[u];
        for(int i = 0; i < N; i++)
        {
            if(p && odwiedzony[p->id]==0)
            {
                odwiedzony[p->id] = 1;
                dd[p->id] = dd[u] + 1;
                prev[p->id] = u;
                Q.push(p->id);
                cout<<p->id<<" ";
                p = p->next;
            }
            else if(p && odwiedzony[p->id] == 1)
                p = p->next;
        }

        Q.pop();
    }
}

int f[N];
int timee = 0;
//DFS DLA MACIERZY SASIEDZTWA
void visit(int u)
{
    odwiedzony[u] = 1;
    dd[u] = timee;
    timee++;
    for(int i = 0; i < N; i++)
        if(odwiedzony[i] == 0 && graf[u][i] == 1)
        {
            cout<<i<<" ";
            odwiedzony[i] = 1;
            prev[i] = u;
            visit(i);
            cout<<endl;
        }
    f[u] = timee;
    timee++;
}

void DFS()
{
    cout<<endl;
    for(int i = 0; i < N; i++)
    {
        odwiedzony[i] = 0;
        prev[i] = -1;
    }
    for(int i = 0; i < N; i++)
        if(odwiedzony[i] == 0)
        {
            cout<<i<<" ";
            visit(i);
        }

}

//DFS DLA LIST SASIEDZTWA
void visit2(int u)
{
    lista *p;
    odwiedzony[u] = 1;
    p = lista_sasiedztwa[u];
    for(int i = 0; i < N; i++)
        if(p && odwiedzony[p->id]==0)
        {
            cout<<p->id<<" ";
            odwiedzony[p->id] = 1;
            visit2(p->id);
            cout<<endl;
        }
        else if(p && odwiedzony[p->id] == 1)
                p = p->next;
}

void DFS2()
{
    cout<<endl;
    for(int i = 0; i < N; i++)
        odwiedzony[i] = 0;
    for(int i = 0; i < N; i++)
        if(odwiedzony[i] == 0)
        {
            cout<<i<<" ";
            visit2(i);
        }

}

int d[N];
void relax(int u, int v)
{
    if(d[v] > d[u] + waga[u][v])
        d[v] = d[u] + waga[u][v];
}

void dijkstra(int s)
{
    for(int i = 0; i < N; i++)
    {
        d[i] = 100000;
        Q.push(i);
    }
    d[s] = 0;
    while(!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        for(int i = 0; i < N; i++)
            if(graf[u][i] == 1)
                relax(u, i);
    }
    for(int i = 0; i < N; i++)
    {
        cout<<"["<<i<<"] "<<d[i]<<endl;
    }
}


//DLA GRAFU NIESKIEROWANEGO WPISYWANIE WYPISYWANIE I ALG PRIMA
int graf2[N][N];
int waga2[N][N];

void wpisz2()
{
    srand (time(NULL));
    for(int i = 0; i < N; i++)
        for(int j = i+1; j < N; j++)
        {
            graf2[i][j] = rand() % 2;
            graf2[j][i] = graf2[i][j];
        }
}

void losuj_waga2()
{
    srand (time(NULL));
    for(int i = 0; i < N; i++)
        for(int j = i+1; j < N; j++)
            if(graf2[i][j] == 1)
            {
                waga2[i][j] = rand()%10 + 1;
                waga2[j][i] = waga2[i][j];
            }

}

void drukuj2()
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
            cout<< graf2[i][j]<<" ";
        cout<<endl;
    }
    cout<<endl<<endl;
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
            cout<< waga2[i][j]<<" ";
        cout<<endl;
    }
}

int key[N];
int pi[N];
bool czy_nalezy[N];

void prim(int r)
{
    for(int i = 0; i < N; i++)
    {
        czy_nalezy[i] = true;
        Q.push(i);
        if(i != r)
            key[i] =  10000;
    }
    key[r] = 0;
    pi[r] = NULL;
    czy_nalezy[r] = false;
    while(!Q.empty())
    {
        int u = Q.front();
        Q.pop();

        for(int v = u+1; v < N; v++)
        {
            if(graf2[u][v] == 1 && czy_nalezy[v] == true && waga2[u][v] < key[v])
            {
                pi[v] = u;
                key[v] = waga2[u][v];
            }
        }
        czy_nalezy[u] = false;
    }
    cout<<endl;
    cout<<"[pi]: ";
    for(int i = 0; i < N; i++)
        cout<<pi[i]<< " ";
    cout<<endl;
    cout<<"[key]: ";
    for(int i = 0; i < N; i++)
        cout<<key[i]<<" ";
}

int main(){
    //wpisz();
    //losuj_waga();
    //drukuj();
    //dijkstra(0);
    //tworz_liste();
    //DFS();
    //DFS2();

    wpisz2();
    losuj_waga2();
    drukuj2();
    prim(0);
    return 0;
}