W12 grafy 1

W12 grafy 1, bioinformatyka, Semestr 2, metody programowania
[ Pobierz całość w formacie PDF ]
IIUJ Metody Programowania
strona: 1
Wykład 12.
Wprowadzenie do algorytmów na grafach
Grafy to struktury danych podobne do drzew, ale w grafach nie wyróżnia się
korzenia. Grafy często reprezentują różne problemy spotykane w rzeczywistości.
Przykładowo węzły w grafie mogą reprezentują miasta na mapie, a krawędzie –
połączenia lotnicze między miastami. Graf nie odzwierciedla geograficznego układu
widocznych na mapie elementów. Przedstawia jedynie związki między wierzchołkami,
czyli to, z którymi wierzchołkami jest połączona dana krawędź.
Innym przykładem może być graf reprezentujący poszczególne zadania -
składowe pewnego projektu, natomiast skierowane krawędzie określają kolejność
wykonywania zadań.
Definicja
Grafem zorientowanym (skierowanym lub digrafem) nazywany strukturę zawierającą
G = (V, E), przy czym:
V - skończony niepusty zbiór wierzchołków,
E

V

V - zbiór krawędzi, krawędzie są
parami wierzchołków.
W grafie skierowanym, jeśli
(i, j)
jest krawędzią to
j
jest
następnikiem
i
,
i
jest
poprzednikiem
j
, przy czym
i
może być równe
j
– wtedy istnieje pętla od danego
wierzchołka do niego samego.
Poniższy rysunek przedstawia graf skierowany G = (V, E )
1
2
3
4
 IIUJ Metody Programowania
strona: 2
V= {1, 2, 3, 4} E = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 2), (3, 4), (4, 3)}
Definicja
Grafem niezorientowanym (nieskierowanym) nazywamy strukturę : G = (V, E),
przy czym:
V - skończony niepusty zbiór wierzchołków
E

2
V
– zbiór krawędzi,

e

E : | e | = 2,
krawędzie są dwuelementowymi
podzbiorami
.
W grafie niezorientowanym, jeśli
(i, j)
jest krawędzią to
j
jest
sąsiadem
i
,
i
jest
sąsiadem j
.
W grafie niezorientowanym nie mogą występować pętle, każda krawędź zawiera
dokładnie dwa różne wierzchołki
.
Typowe oznaczenie: |V|= n, |E| = m.
Liczba krawędzi:

w grafie zorientowanym: 0

m

n * n

w grafie niezorientowanym: 0

m

n * (n-1)/2
Reprezentacja komputerowa grafów
Utożsamiamy zbiór wierzchołków V = {1, ... ,n}
1. Tablica (macierz) sąsiedztwa
, jej wielkość nie zależy od liczby krawędzi
w grafie:
1

(i, j)

E
adjMat[i, j] =
0

(i, j)

E
Dla grafu niezorientowanego jest symetryczna, z zerami na przekątnej.
Fakt:
Rozmiar pamięci potrzebnej dla tablicy sąsiedztwa wynosi

(n
2
).
2.
Listy sąsiedztwa (listy przylegania),
kolejność na listach dowolna:
 IIUJ Metody Programowania
strona: 3
Tablica L[n] nagłówków list (częste oznaczenie: Adj[n] – "adjacency")
L[
i
] - jest nagłówkiem listy zawierającej wszystkie
j
, takie że
(i, j)
jest krawędzią.
Dla grafu niezorientowanego każda krawędź (i, j) reprezentowana jest w liście L[i]
oraz w liście L[j].
Fakt:
Rozmiar pamięci potrzebnej dla list sąsiedztwa wynosi

(n + m).
Terminologia

Stopień wierzchołka: liczba jego następników (sąsiadów)

Ścieżka od wierzchołka
u
do wierzchołka
w
: ciąg wierzchołków
v
0
, v
1
, ..., v
k
taki, że
(v
i
, v
i+1
)

E, i=0,...,k-1,
v
0
, = u
,
v
k
= w
(inaczej: wierzchołek w jest osiągalny z
wierzchołka u)

Ścieżka prosta (elementarna): wierzchołki na ścieżce nie powtarzają się (być może za
wyjątkiem v
0
= v
k
)

W grafie
zorientowanym
ścieżka
v
0
, v
1
, ..., v
k
tworzy cykl, jeśli v
0
= v
k
oraz zawiera co
najmniej jedną krawędź. Cykl nazywamy prostym, jeśli dodatkowo
v
1
, ..., v
k
są różne.

W grafie
niezorientowanym
ścieżka
v
0
, v
1
, ..., v
k
tworzy cykl, jeśli v
0
= v
k
oraz
v
1
, ..., v
k
są różne i k

2 (
zawiera co najmniej trzy wierzchołki)
.
 IIUJ Metody Programowania
strona: 4

Długość ścieżki: liczba krawędzi na ścieżce (tutaj: k)

Odległość od wierzchołka
v
do wierzchołka
u
- długość najkrótszej ścieżki od
u
do
v
(przyjmujemy

jeśli
v
nie jest osiągalny z
u
)

Podgraf grafu G=(V, E) :
graf H=(V', E') taki, że V'

V, E'

E

Podgraf
indukowany
grafu G=(V, E) :
graf H=(V', E') taki, że V'

V, E' = {(u, v)

E: u, v

V' }
Definicje – dla grafu
niezorientowanego
G=(V, E)
:

G jest
spójny
: każdy wierzchołek jest osiągalny z każdego wierzchołka

Spójna składowa
grafu G : maksymalny podgraf indukowany H taki, że H jest
spójny

G jest drzewem: gdy G jest spójny i nie zawiera cykli (często z wyróżnionym
wierzchołkiem zwanym korzeniem)

Drzewo rozpinające
dla spójnego niezorientowanego grafu G=(V,E):
drzewo T=(V', E') takie, że V'=V, E'

E ,
czyli podgraf bez cykli, łączący wszystkie wierzchołki
Definicje - dla grafu zorientowanego
:

G jest
silnie spójny
: gdy każdy wierzchołek jest osiągalny z każdego wierzchołka

Silnie spójna składowa
grafu G: maksymalny podgraf indukowany H taki, że H jest
silnie spójny
 IIUJ Metody Programowania
strona: 5
Reprezentacja grafu w Javie
W większości zastosowań praktycznych wierzchołek reprezentuje pewien obiekt
odpowiedniej klasy. W wierzchołkach przechowujemy zwykle
label
(etykietę) typu
znakowego oraz informację reprezentowaną przez zmienną
wasVisited
(był
odwiedzony) typu logicznego.
Zatem klasa wierzchołek ma postać:
class Vertex {
public char label; // etykieta , np.’A’
public boolean wasVisited; // czy był odwiedzony
public Vertex(char lab) // konstruktor
{
label = lab;
wasVisited = false; // nie był odwiedzony
}
} // end class Vertex
Obiekty klasy
Vertex
mogą być umieszczane w tablicy i mogą być wywoływane
przy użyciu numeru indeksu. W przykładowym programie użyjemy tablicy o nazwie
vertexList
.
Wierzchołki można również przechowywać jako listę lub inną strukturę, przy
czym typ struktury
nie jest powiązany
z systemem łączenia wierzchołków za pomocą
krawędzi.
Do zapamiętania krawędzi grafu można użyć macierze sąsiedztwa lub listy
sąsiedztwa w reprezentacji wiązanej.
Poniżej podano definicję klasy graph, w której do zapamiętania krawędzi użyto
macierzy sąsiedztwa –
adjMat
[ ] [ ].
class Graph{
private int MAX_VERTS = 20;
private Vertex vertexList[]; // lista wierzchołków
private int adjMat[ ][ ]; // macierz sąsiedztwa
private int nVerts; // bieżąca liczba wierzchołków
// -------------------------------------------------------------------------------------------------
public Graph() { // konstruktor
vertexList = new Vertex[MAX_VERTS]; // tablica wierzchołków
adjMat = new int[MAX_VERTS][MAX_VERTS]; // macierz sąsiedztwa
nVerts = 0; // liczba węzłów
for(int j=0; j < MAX_VERTS; j++) // zerowanie macierzy sąsiedztwa
for(int k=0; k<MAX_VERTS; k++)
adjMat[ j ][ k ] = 0;
} // end constructor
  [ Pobierz całość w formacie PDF ]
  • zanotowane.pl
  • doc.pisz.pl
  • pdf.pisz.pl
  • diabelki.xlx.pl
  • Podobne
    Powered by wordpress | Theme: simpletex | © Spojrzeliśmy na siebie szukając słów, które nie istniały.