IMG474 (2)

ALGORYTMY I STRUKTURY DANYCH - ćwiczenia INFORMATYKA

II rok, studia stacjonarne I stopnia rok ak. 2012/2013 semestr zimowy

Lista 10

Algorytmy grafowe

1.    Dla dwóch grafów - skierowanego i nieskierowanego - utworzyć

a)    macierz sąsiedztwa

b)    macierz incydencji

c)    listy sąsiedztwa

2.    Podać algorytmy przeszukiwania grafu

a)    w głąb - DFS (ang. Depth First Search)

b)    wszerz - BFS. (ang. Breadth First Search)

3.    Dla grafu skierowanego określić stopień wejściowy i wyjściowy każdego wierzchołka.

4.    Znaleźć najkrótszą ścieżkę pomiędzy zadanymi dwoma wierzchołkami w grafie ważonym (Algorytm Dijkstry).

5.    Utworzyć od zadanego wierzchołka drzewo rozpinające grafu

6.    Pokolorować wierzchołki grafu jak najmniejszą ilością kolorów, tak by żadna krawędź nie miała na końcach tego samego koloru.

2012-12-03

T. Wiśniewska