zad4

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

//B)
// WESJA WSZERZ
// NA MACIERZY SASIEDZTWA

//| 1 0 0 3 0 0 7 |
//| 0 0 2 0 4 0 1 |
//| 0 2 0 4 1 2 3 |
//| 3 0 4 0 5 3 3 |
//| 0 4 1 5 0 1 2 |
//| 0 0 2 3 1 0 2 |
//| 7 1 3 3 2 2 0 |

//Narysuj graf G(w B wartości oznaczają wagi a nie liczbę krawędzi).
//Napisz metodę przechodzenia grafu w WsZERZ i zastosuj dla grafu G

class Program
{
static void BFS(int[,] G, int v)
{
Queue kolejka = new Queue();
bool[] odwiedzony = new bool[G.GetLength(0)];
kolejka.Enqueue(v);
while (kolejka.Count > 0)
{
v = kolejka.Dequeue();
if (!odwiedzony[v])
{
Console.WriteLine(v);
odwiedzony[v] = true;
// do kolejki mogą być włożone powtórnie te które już są
for (int i = 0; i < G.GetLength(0); i++)
{
if (G[v, i] != 0 && !odwiedzony[i])
{
kolejka.Enqueue(i);
}
}
}
}
}

// TERAZ TYLKO RAZ JEST WKLADANY DO KOLEJKI
//
// gdyby tak zrobic dla DFS i wkładać na stos tylko niewłożone
// to wynik byłby inny a dla kolejki wynik jest taki sam jak wyżej

static void BFS1(int[,] G, int v)
{
Queue kolejka = new Queue();
bool[] wlozony = new bool[G.GetLength(0)];
kolejka.Enqueue(v);
wlozony[v] = true;

while (kolejka.Count > 0)
{
v = kolejka.Dequeue();
Console.WriteLine(v);

for (int i = 0; i < G.GetLength(0); i++)
{
// jak włożony to drugi raz nie włożymy
if (G[v, i] != 0 && !wlozony[i])
{
kolejka.Enqueue(i);
wlozony[i] = true;
}
}
}
}

static void Main(string[] args)
{
int[,] G =
{
{ 1, 0, 0, 3, 0, 0, 7 },
{ 0, 0, 2, 0, 4, 0, 1 },
{ 0, 2, 0, 4, 1, 2, 3 },
{ 3, 0, 4, 0, 5, 3, 3 },
{ 0, 4, 1, 5, 0, 1, 2 },
{ 0, 0, 2, 3, 1, 0, 2 },
{ 7, 1, 3, 3, 2, 2, 0 }
};
BFS(G, 4);
Console.WriteLine();
BFS1(G, 4);
Console.WriteLine();

Console.ReadKey();

}
}