Sprawdź się
Uzupełnij brakujący kod metody znajdzKrawedz(int wierzcholek1, int wierzcholek2)
w klasie Graf
, która sprawdzi, czy w grafie istnieje krawędź łącząca dane wierzchołki. Działanie programu przetestuj dla podanego w kodzie grafu graf
i trzech par wierzchołków wierzcholek1
i wierzcholek2
:
1, 3
5, 4
2, 4
Specyfikacja:
Dane:
graf
– podany graf; obiekt klasyGraf
wierzcholek1
,wierzcholek2
– wierzchołki grafu; liczby naturalne
Wynik:
Program, na standardowe wyjście, wypisuje indeks krawędzi, jeśli zostanie znaleziona krawędź łącząca dwa wierzchołki, lub -1, jeśli nie ma między nimi połączenia.
import java.util.List;
import java.util.ArrayList;
class Graf{
List<Integer> wierzcholki;
List<List<Integer>> krawedzie;
Graf(){
wierzcholki = new ArrayList<>();
krawedzie = new ArrayList<>();
}
public void dodajWierzcholek(int nowyWierzcholek) {
for (int wierzcholek : this.wierzcholki)
if (wierzcholek == nowyWierzcholek) return;
this.wierzcholki.add(nowyWierzcholek);
}
public void dodajKrawedz(int wierzcholek1, int wierzcholek2) {
for (List<Integer> krawedz : this.krawedzie) {
if (krawedz.get(0) == wierzcholek1 && krawedz.get(1) == wierzcholek2) return;
else if (krawedz.get(1) == wierzcholek1 && krawedz.get(0) == wierzcholek2) return;
}
List<Integer> krawedz = new ArrayList<>();
krawedz.add(wierzcholek1);
krawedz.add(wierzcholek2);
this.krawedzie.add(krawedz);
}
public int znajdzKrawedz(int wierzcholek1, int wierzcholek2){
for (List<Integer> krawedz : this.krawedzie) {
if (krawedz.get(0) == wierzcholek1 && krawedz.get(1) == wierzcholek2) return this.krawedzie.indexOf(krawedz);
else if (krawedz.get(1) == wierzcholek1 && krawedz.get(0) == wierzcholek2) return this.krawedzie.indexOf(krawedz);
}
return -1;
}
}
public class Main {
public static void main(String args[]) {
Graf graf = new Graf();
graf.dodajWierzcholek(1);
graf.dodajWierzcholek(2);
graf.dodajWierzcholek(3);
graf.dodajWierzcholek(4);
graf.dodajWierzcholek(5);
graf.dodajKrawedz(1, 2);
graf.dodajKrawedz(1, 3);
graf.dodajKrawedz(1, 4);
graf.dodajKrawedz(2, 3);
graf.dodajKrawedz(3, 4);
graf.dodajKrawedz(4, 5);
int wierzcholek1 = 1;
int wierzcholek2 = 3;
System.out.println(graf.znajdzKrawedz(wierzcholek1, wierzcholek2)); // 1
wierzcholek1 = 5;
wierzcholek2 = 4;
System.out.println(graf.znajdzKrawedz(wierzcholek1, wierzcholek2)); // 5
wierzcholek1 = 2;
wierzcholek2 = 4;
System.out.println(graf.znajdzKrawedz(wierzcholek1, wierzcholek2)); // -1
}
}
Uzupełnij brakujący kod metody listaSasiadow(int wierzcholek)
w klasie Graf
, która zwróci posortowaną rosnąco listę sąsiadów danego wierzchołka wierzcholek
. Działanie programu przetestuj dla podanego w kodzie grafu graf
i wierzchołka wierzcholek = 1
.
Specyfikacja:
Dane:
graf
– podany graf; obiekt klasyGraf
wierzcholek
– wierzchołek grafu; liczba naturalna
Wynik:
Program, na standardowe wyjście, wypisuje posortowaną rosnąco listę sąsiadów wierzchołka wierzcholek
.
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
class Graf{
List<Integer> wierzcholki;
List<List<Integer>> krawedzie;
Graf(){
wierzcholki = new ArrayList<>();
krawedzie = new ArrayList<>();
}
public void dodajWierzcholek(int nowyWierzcholek) {
for (int wierzcholek : this.wierzcholki)
if (wierzcholek == nowyWierzcholek) return;
this.wierzcholki.add(nowyWierzcholek);
}
public void dodajKrawedz(int wierzcholek1, int wierzcholek2) {
for (List<Integer> krawedz : this.krawedzie) {
if (krawedz.get(0) == wierzcholek1 && krawedz.get(1) == wierzcholek2) return;
else if (krawedz.get(1) == wierzcholek1 && krawedz.get(0) == wierzcholek2) return;
}
List<Integer> krawedz = new ArrayList<>();
krawedz.add(wierzcholek1);
krawedz.add(wierzcholek2);
this.krawedzie.add(krawedz);
}
public List<Integer> listaSasiadow(int wierzcholek){
List<Integer> sasiedzi = new ArrayList<>();
for (List<Integer> krawedz : this.krawedzie) {
if (krawedz.get(0) == wierzcholek)
sasiedzi.add(krawedz.get(1));
if (krawedz.get(1) == wierzcholek)
sasiedzi.add(krawedz.get(0));
}
Collections.sort(sasiedzi);
return sasiedzi;
}
}
public class Main {
public static void main(String args[]) {
Graf graf = new Graf();
graf.dodajWierzcholek(1);
graf.dodajWierzcholek(2);
graf.dodajWierzcholek(3);
graf.dodajWierzcholek(4);
graf.dodajWierzcholek(5);
graf.dodajKrawedz(1, 2);
graf.dodajKrawedz(1, 3);
graf.dodajKrawedz(2, 3);
graf.dodajKrawedz(5, 1);
graf.dodajKrawedz(3, 4);
graf.dodajKrawedz(4, 5);
int wierzcholek = 1;
System.out.println(graf.listaSasiadow(wierzcholek)); // [2, 3, 5]
}
}
Uzupełnij brakujący kod metody wypiszGraf()
w klasie Graf
, która dla każdego wierzchołka grafu wypisze posortowaną rosnąco listę jego sąsiadów. Działanie programu przetestuj dla podanego w kodzie grafu graf
.
Specyfikacja:
Dane:
graf
– podany graf; obiekt klasyGraf
Wynik:
Program, na standardowe wyjście, wypisuje – w kolejnych liniach – posortowane rosnąco listy sąsiadów kolejnych wierzchołków grafu graf
.
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
class Graf{
List<Integer> wierzcholki;
List<List<Integer>> krawedzie;
Graf(){
wierzcholki = new ArrayList<>();
krawedzie = new ArrayList<>();
}
public void dodajWierzcholek(int nowyWierzcholek) {
for (int wierzcholek : this.wierzcholki)
if (wierzcholek == nowyWierzcholek) return;
this.wierzcholki.add(nowyWierzcholek);
}
public void dodajKrawedz(int wierzcholek1, int wierzcholek2) {
for (List<Integer> krawedz : this.krawedzie) {
if (krawedz.get(0) == wierzcholek1 && krawedz.get(1) == wierzcholek2) return;
else if (krawedz.get(1) == wierzcholek1 && krawedz.get(0) == wierzcholek2) return;
}
List<Integer> krawedz = new ArrayList<>();
krawedz.add(wierzcholek1);
krawedz.add(wierzcholek2);
this.krawedzie.add(krawedz);
}
public List<Integer> listaSasiadow(int wierzcholek){
List<Integer> sasiedzi = new ArrayList<>();
for (List<Integer> krawedz : this.krawedzie) {
if (krawedz.get(0) == wierzcholek)
sasiedzi.add(krawedz.get(1));
if (krawedz.get(1) == wierzcholek)
sasiedzi.add(krawedz.get(0));
}
Collections.sort(sasiedzi);
return sasiedzi;
}
public void wypiszGraf(){
for (int wierzcholek : this.wierzcholki)
System.out.println(listaSasiadow(wierzcholek));
}
}
public class Main {
public static void main(String args[]) {
Graf graf = new Graf();
graf.dodajWierzcholek(1);
graf.dodajWierzcholek(2);
graf.dodajWierzcholek(3);
graf.dodajWierzcholek(4);
graf.dodajWierzcholek(5);
graf.dodajWierzcholek(6);
graf.dodajKrawedz(1, 2);
graf.dodajKrawedz(1, 3);
graf.dodajKrawedz(2, 3);
graf.dodajKrawedz(3, 4);
graf.dodajKrawedz(5, 1);
graf.dodajKrawedz(5, 3);
graf.dodajKrawedz(5, 6);
graf.wypiszGraf();
// [2, 3, 5]
// [1, 3]
// [1, 2, 4, 5]
// [3]
// [1, 3, 6]
// [5]
}
}