Sprawdź się
Uzupełnij tabelę będącą macierzą sąsiedztwa grafu, którego macierz incydencji ma następującą postać: A równa się, w macierzy zapisano: Linia 1: zero, zero, jeden, jeden, zero. Linia 2: zero, zero, zero, jeden, jeden. Linia 3: jeden, zero, zero, jeden, jeden. Linia 4: jeden, jeden, jeden, zero, jeden. Linia 5: zero, jeden, jeden, jeden, zero.
ArrayList
, 2. ArrayList
, 3. LinkedList
, 4. LinkedList<> listaDwukierunkowa2 = new LinkedList<>()
Napisz funkcję, która przekształci macierz sąsiedztwa grafu nieskierowanego bez wag w macierz incydencji.
Specyfikacja problemu:
Dane:
macierzSasiedztwa
– macierz liczb całkowitych
Wynik:
macierzIncydencji
– macierz liczb całkowitych
Przykładowe rozwiązanie zadania:
public class Main {
static int n = 6;
static int maxM = 15;
private static int m = 0;
static void przeksztalc(int[][] macierzSasiedztwa, int[][] macierzIncydencji) {
for (int i = 0; i < macierzSasiedztwa.length; i++) {
for (int j = i + 1; j < macierzSasiedztwa[i].length; j++) {
if (macierzSasiedztwa[i][j] == 1) {
macierzIncydencji[i][m] = 1;
macierzIncydencji[j][m] = 1;
m++;
}
}
}
}
static void wypisz(int[][] macierzIncydencji) {
for (int i = 0; i < macierzIncydencji.length; i++) {
for (int j = 0; j < m; j++)
System.out.print(macierzIncydencji[i][j] + " ");
System.out.println();
}
}
public static void main(String[] args) {
int[][] macierzSasiedztwa = {
{0, 1, 1, 1, 1, 0},
{1, 0, 1, 1, 1, 0},
{1, 1, 0, 0, 1, 0},
{1, 1, 0, 0, 1, 0},
{1, 1, 1, 1, 0, 1},
{0, 0, 0, 0, 1, 0}
};
int[][] macierzIncydencji = new int[n][maxM];
przeksztalc(macierzSasiedztwa, macierzIncydencji);
wypisz(macierzIncydencji);
}
}
Napisz funkcję, która przekształci macierz incydencji grafu nieskierowanego bez wag w listę sąsiedztwa.
Specyfikacja problemu:
Dane:
macierzIncydencji
– macierz liczb całkowitych
Wynik:
listaSasiedztwa
– lista liczb całkowitych
Przykładowe rozwiązanie zadania:
import java.util.ArrayList;
import java.util.LinkedList;
public class Main {
static int n = 6;
private static int m = 11;
static void przeksztalc(int[][] macierzIncydencji, ArrayList<LinkedList<Integer>> listaSasiedztwa) {
for (int e = 0; e < m; e++) {
int i = 0;
int j = 0;
while (i < n) {
if (macierzIncydencji[i][e] == 1)
break;
i++;
}
j = i + 1;
while (j < n) {
if (macierzIncydencji[j][e] == 1)
break;
j++;
}
listaSasiedztwa.get(i).add(j);
listaSasiedztwa.get(j).add(i);
}
}
static void wypisz(ArrayList<LinkedList<Integer>> listaSasiedztwa) {
for (int i = 0; i < listaSasiedztwa.size(); i++) {
System.out.print(i + ": ");
for (int j : listaSasiedztwa.get(i) )
System.out.print(j + " ");
System.out.println();
}
}
public static void main(String[] args) {
int[][] macierzIncydencji = {
{1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0},
{1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0},
{0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0},
{0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1},
{0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1}
};
ArrayList<LinkedList<Integer>> listaSasiedztwa = new ArrayList<>(n);
for (int i = 0; i < n; i++)
listaSasiedztwa.add(new LinkedList<>());
przeksztalc(macierzIncydencji, listaSasiedztwa);
wypisz(listaSasiedztwa);
}
}
Macierze sąsiedztwa dobrze sprawdzają się w reprezentacji grafów ważonych. Jeśli wagi krawędzi są różne od 0
, wówczas tam, gdzie normalnie wstawilibyśmy 1
, wpiszemy wagę krawędzi. Gdyby jednak graf zawierał wagę 0
, to za brak połączenia uznajemy pewną liczbę waga
rożną od wszystkich wag w grafie.
Podobnie jak macierz sąsiedztwa, także lista sąsiedztwa może służyć do prezentacji grafów ważonych. W takim wypadku wyrazy na liście sąsiadów danego wierzchołka będą parą uporządkowaną dwóch elementów: indeksu sąsiada oraz wagi krawędzi łączącej sąsiada z wierzchołkiem. Przykładowo: jeśli waga krawędzi ij
wynosi 5
, wówczas na liście listaSasiedztwa[i]
powinna znaleźć się para {j, 5}
. Graf domyślnie jest nieskierowany, więc analogicznie lista listaSasiedztwa[j]
zawiera parę {i, 5}
.
W drugim wierszu w niebieskim kwadracie 1, dalej w tej samej linii w są dwa czarne kwadraty połączone ze sobą. W pierwszym kwadracie jest 0 w drugim w kolorze niebieskim 5. Od tych kwadratów odchodzi strzałka skierowana w prawą stronę do dwóch połączonych czarnych kwadratów. W pierwszym jest 2, a w drugim w kolorze niebieskim 7. Od tych kwadratów odchodzi strzałka w prawą stronę do dwóch połączonych kwadratów. W pierwszym jest 3 a w drugim w niebieskim kolorze 8.
W trzecim wierszu w niebieskim kwadracie 2, dalej w tej samej linii w są dwa czarne kwadraty połączone ze sobą. W pierwszym kwadracie jest 1 w drugim w kolorze niebieskim 7. Od tych kwadratów odchodzi strzałka skierowana w prawą stronę do dwóch połączonych czarnych kwadratów. W pierwszym jest 4, a w drugim w kolorze niebieskim 1.
W czwartym wierszu w niebieskim kwadracie 3, dalej w tej samej linii w są dwa czarne kwadraty połączone ze sobą. W pierwszym kwadracie jest 0 w drugim w kolorze niebieskim 6. Od tych kwadratów odchodzi strzałka skierowana w prawą stronę do dwóch połączonych czarnych kwadratów. W pierwszym jest 1, a w drugim w kolorze niebieskim 8. Od tych kwadratów odchodzi strzałka w prawą stronę do dwóch połączonych kwadratów. W pierwszym jest 4 a w drugim w niebieskim kolorze 3.
W piątym wierszu w niebieskim kwadracie 4, dalej w tej samej linii w są dwa czarne kwadraty połączone ze sobą. W pierwszym kwadracie jest 2 w drugim w kolorze niebieskim 1. Od tych kwadratów odchodzi strzałka skierowana w prawą stronę do dwóch połączonych czarnych kwadratów. W pierwszym jest 3, a w drugim w kolorze niebieskim 3.
![Ilustracja przedstawia kolaż trzech grafik: pierwsza grafika przedstawia macierz sąsiedztwa druga grafika przedstawia rysunek grafu i trzecia grafika przedstawia listę sąsiedztwa. Na pierwszej grafice widoczna jest macierz sąsiedztwa. Tworzy ją tabelka pięć na pięć kratek. Jej kolumny i rzędy są oznaczone cyframi od 0 do 4. W pierwszym rzędzie wpisano 0, na niebiesko 5, dalej 0, dalej na niebiesko 6, dalej 0, w drugim rzędzie na niebiesko 5,dalej 0, na niebiesko 7, dalej na niebiesko 8, dalej zero 0, w trzecim rzędzie 0, na niebiesko 7, dalej 0, dalej 0, na niebiesko 1, w czwartym rzędzie na niebiesko 6, dalej na niebiesko 8, dalej 0,dalej 0, dalej na niebiesko 3, w piątym rzędzie 0, dalej 0, dalej na niebiesko 1, dalej na niebiesko 3, dalej 0. Druga widoczna grafika przedstawia rysunek graf. W niebieskich otoczkach zaznaczone są liczby: 0, 1, 2, 3, 4. Widoczne połączenia między. 0 połączone jest czarną linią obok której jest 5 z 1 i z 3 czarną linią obok której jest 6. 1 połączone jest czarną linią obok której jest 5 z 0 z 2 czarną linią obok której jest 7 i z 3 czarną linią obok której jest 8. 2 połączone jest czarną linią obok której jest 7 z 1 i z 4 czarną linią obok której jest 1. 4 połączone jest czarną linią obok której jest 1 z 2 i z 3 czarną linią obok której jest 3. 3 połączone jest czarną linią obok której jest 3 z 4 z 0 czarną linią obok której jest 6 i z 1 czarną linią obok której jest 8. Trzecia widoczna grafika przedstawia listę sąsiedztwa. Na grafice widoczne jest pięć wierszy. W pierwszym wierszu w niebieskim kwadracie 0, dalej w tej samej linii w są dwa czarne kwadraty połączone ze sobą. W pierwszym kwadracie jest 1 w drugim w kolorze niebieskim 5. Od tych kwadratów odchodzi strzałka skierowana w prawą stronę do dwóch połączonych czarnych kwadratów. W pierwszym jest 3, a w drugim w kolorze niebieskim 6. W drugim wierszu w niebieskim kwadracie 1, dalej w tej samej linii w są dwa czarne kwadraty połączone ze sobą. W pierwszym kwadracie jest 0 w drugim w kolorze niebieskim 5. Od tych kwadratów odchodzi strzałka skierowana w prawą stronę do dwóch połączonych czarnych kwadratów. W pierwszym jest 2, a w drugim w kolorze niebieskim 7. Od tych kwadratów odchodzi strzałka w prawą stronę do dwóch połączonych kwadratów. W pierwszym jest 3 a w drugim w niebieskim kolorze 8. W trzecim wierszu w niebieskim kwadracie 2, dalej w tej samej linii w są dwa czarne kwadraty połączone ze sobą. W pierwszym kwadracie jest 1 w drugim w kolorze niebieskim 7. Od tych kwadratów odchodzi strzałka skierowana w prawą stronę do dwóch połączonych czarnych kwadratów. W pierwszym jest 4, a w drugim w kolorze niebieskim 1. W czwartym wierszu w niebieskim kwadracie 3, dalej w tej samej linii w są dwa czarne kwadraty połączone ze sobą. W pierwszym kwadracie jest 0 w drugim w kolorze niebieskim 6. Od tych kwadratów odchodzi strzałka skierowana w prawą stronę do dwóch połączonych czarnych kwadratów. W pierwszym jest 1, a w drugim w kolorze niebieskim 8. Od tych kwadratów odchodzi strzałka w prawą stronę do dwóch połączonych kwadratów. W pierwszym jest 4 a w drugim w niebieskim kolorze 3. W piątym wierszu w niebieskim kwadracie 4, dalej w tej samej linii w są dwa czarne kwadraty połączone ze sobą. W pierwszym kwadracie jest 2 w drugim w kolorze niebieskim 1. Od tych kwadratów odchodzi strzałka skierowana w prawą stronę do dwóch połączonych czarnych kwadratów. W pierwszym jest 3, a w drugim w kolorze niebieskim 3.](https://static.zpe.gov.pl/portal/f/res-minimized/R1b8UlEnz7IDA/1690815130/1yykvxHmLq5ZkPqizKDHUri9E8Oj30us.png)
Zdefiniowano listę krawędzi w postaci tablic trójek int[n][3]
, gdzie pierwszy i ostatni wyraz w każdej trójce to indeksy sąsiednich wierzchołków, a wyraz środkowy jest wagą krawędzi łączącej te wierzchołki. Twoim zadaniem jest zdefiniowanie następujących funkcji:
Funkcja
static void przeksztalc(int[][] krawedzie, int[][] macierzSasiedztwa)
, która przekształci tablicę trójekkrawedzie
w macierz sąsiedztwamacierzSasiedztwa
w wersji ważonej.Funkcja
static void przeksztalc(int[][] macierzSasiedztwa, ArrayList<LinkedList<Sasiad>> listaSasiedztwa)
, która na podstawie macierzy sąsiedztwamacierzSasiedztwa
wstawi do listy sąsiedztwalistaSasiedztwa
sąsiadówSasiad
każdego wierzchołkai
.
Klasa Sasiad
ma zdefiniowane dwa pola: indeks
oraz waga
, do których dostajemy się za pomocą metod - odpowiednio getIndeks()
i getWaga()
.
Specyfikacja problemu:
Dane:
krawedzie
– macierz liczb całkowitych
Wynik:
macierzSasiedztwa
– macierz liczb całkowitychlistaSasiedztwa
– lista obiektówSasiad
Przykładowe rozwiązanie zadania:
import java.util.ArrayList;
import java.util.LinkedList;
public class Main {
static int n = 6;
static void przeksztalc(int[][] krawedzie, int[][] macierzSasiedztwa) {
for (int i = 0; i < krawedzie.length; i++) {
macierzSasiedztwa[krawedzie[i][0]][krawedzie[i][2]] = krawedzie[i][1];
macierzSasiedztwa[krawedzie[i][2]][krawedzie[i][0]] = krawedzie[i][1];
}
}
static void przeksztalc(int[][] macierzSasiedztwa, ArrayList<LinkedList<Sasiad>> listaSasiedztwa) {
for (int i = 0; i < macierzSasiedztwa.length; i++) {
for (int j = i + 1; j < macierzSasiedztwa[i].length; j++) {
if (macierzSasiedztwa[i][j] != 0) {
listaSasiedztwa.get(i).add(new Sasiad(j, macierzSasiedztwa[i][j]));
listaSasiedztwa.get(j).add(new Sasiad(i, macierzSasiedztwa[i][j]));
}
}
}
}
static void wypisz(int[][] macierzSasiedztwa) {
for (int i = 0; i < macierzSasiedztwa.length; i++) {
for (int j = 0; j < macierzSasiedztwa[i].length; j++)
System.out.print(macierzSasiedztwa[i][j] + " ");
System.out.println();
}
}
static void wypisz(ArrayList<LinkedList<Sasiad>> listaSasiedztwa) {
for (int i = 0; i < listaSasiedztwa.size(); i++) {
System.out.print(i + ": ");
for (Sasiad sasiad : listaSasiedztwa.get(i)) {
System.out.print("{" + sasiad.getIndeks() + ", " + sasiad.getWaga() + "} ");
}
System.out.println();
}
}
public static void main(String[] args) {
int[][] krawedzie = {
{1, 2, 0},
{2, 3, 0},
{3, 6, 0},
{4, 4, 0},
{5, 5, 0},
{2, 1, 1},
{3, 9, 1},
{4, 4, 1},
{5, 0, 1},
{3, 0, 2},
{4, 0, 2},
{5, 7, 2},
{4, 8, 3},
{5, 9, 3},
{5, 1, 4}
};
int[][] macierzSasiedztwa = new int [n][n];
ArrayList<LinkedList<Sasiad>> listaSasiedztwa = new ArrayList<>(n);
for (int i = 0; i < n; i++)
listaSasiedztwa.add(new LinkedList<>());
przeksztalc(krawedzie, macierzSasiedztwa);
wypisz(macierzSasiedztwa);
System.out.println();
przeksztalc(macierzSasiedztwa, listaSasiedztwa);
wypisz(listaSasiedztwa);
}
}
class Sasiad {
private int indeks;
private int waga;
public Sasiad(int indeks, int waga) {
this.indeks = indeks;
this.waga = waga;
}
public int getIndeks() {
return indeks;
}
public int getWaga() {
return waga;
}
}