AISD wer. 2 str. 52
Cyfrowe drzewa dostępu (ang. Radix Search Tries) są modyfikacją cyfrowych drzew
przeszukiwań taką, że dane są zapamiętywane tylko w liściach, zaś rozgałęzienia
następują w węzłach pośrednich na podstawie badania kolejnych cyfr klucza.
Przykład. Binarne drzewo dostępu dla kluczy
16, 54, 14, 63 62 48 21 53
010000, 110110, 001110, 111111, 111110, 110000, 010101, 110101
root
0xxxxx
1xxxxx
[14]
01xxxx
11xxxx
010xxx
110xxx
111xxx
[16] [21]
[48] 1101xx
1111xx
[53] [54]
11111x
[62] [63]
Zupełne drzewo dostępu (ang. Complete (or Pure) Radix Search Trie) różni się tym od
postaci standardowej, że wszystkie liście rezydują na najgłębszym możliwym poziomie
węzła. W takim drzewie wszystkie cyfry są badane na ścieżce dostępu do informacji i dlatego
klucz nie musi być zapamiętywany w liściu drzewa.
root
* *
* * *
* * * *
* * * * * *
* * * * * * *
[] [] [] [] [] [] [] []
14 16 21 48 53 54 62 63
Własność. Kształt (balans) cyfrowego drzewa przeszukiwań jest wrażliwy na cyfrowy rozkład
kluczy.
Klucze, które nie są równomiernie rozłożone (cyfrowo) są nazywane kluczami numerycznie
odchylonymi (ang. biased). Takie klucze powodują grupowanie (ang. cluster) danych w
cyfrowym drzewie przeszukiwań.
AISD wer. 2 str. 53
Własność. Kształt (balans) cyfrowego drzewa dostępu (ang. trie) zawierającego n kluczy
jest niezależny od kolejności wstawiania tych kluczy. Unikatowe (jednoznaczne) drzewo
istnieje dla danego zbioru kluczy.
Własność. Poszukiwanie lub wstawienie węzla do M-arnego cyfrowego drzewa dostępu
wymaga średnio około log
M
(N) porównań a w najgorszym przypadku b porownań w drzewie
utworzonym z N losowych b-cyfrowych kluczy.
Cyfrowe drzewo dostępu może być kosztowne z punktu widzenia zasobu pamięci. Liczba
węzłów wewnętrznych może być znacznie większa od liczby liści. Jesli wzrasta liczba M, to
skraca się ścieżka do liści, ale z drugiej strony wzrasta liczba nieużywanych wskazań na
węzły potomne (dzieci).
Własność. Binarne drzewo dostępu utworzone z N losowych b-bitowych kluczy liczy średnio
około N/ln(2) = 1.44*N.
Własność. Dla M-arnego drzewa dostępu utworzonego z N losowych kluczy, liczba
używanych powiązań wynosi około M*N/ln(M).
Podsumowując można stwierdzić, że drzewa przeszkiwań oparte o porównania (całych
wartości kluczy) są silnie zależne od kolejności wprowadzania, wyważenie cyfrowych drzew
przeszukiwań w niewielkim stopniu zależy od tej kolejności, zaś drzewa dostępu są w pełni
niezależne od kolejności wprowaczania danych.
Hybrydowe drzewa dostępu znajdują zastosowanie w praktycznych rozwiązaniach
pozwalając na wyważenie szybkości przetwarzania i zajętości pamięci.
Zwiększenie stopnia drzewa dostępu zwiększa szybkość przetwarzania ponieważ do
pojedynczego porównania brana jest większa liczba bitów (i skraca się ścieżka dostępu). Ma
to sens w "górnej" części drzewa, gdzie zazwyczaj wszystkie rozgałęzienia są wykorzystane.
Gorzej jest w dolnej części drzewa, gdzie wiele wskazań na dzieci jest puste. W rozwiązaniu
hybrydowym dopuszcza się stosowanie niższego stopnia węzłów w tym obszarze drzewa.
Innym hybrydowym rozwiązaniem jest stosowanie porcji (ang. bucket) w liściach drzewa
dostępu, co umożliwia wprowadzanie wielu danych z tym samym kluczem.
Własność. Binarne drzewo dostępu dzieli zbiór danych w taki sam sposób jak algorytm
sortowania według cyfr (ang. Radix Exchange Sort).
Słowniki są często implementowane jako cyfrowe drzewa dostępu. Na przykład w języku
angielskim stopień takiego drzewa (M) wynosi 26. Istotną zaletą takiego rozwiązania jest
efektywne przetwarzanie procesu wyszukiwania i dopasowywania przedrostków, co jest
ważną cechą wyszukiwania słów oraz sprawdzania ich pisowni.
Często słowniki sa realizowane hybrydowo z binarnymu drzewami przeszukiwań (BST)
bliżej liści.
AISD wer. 2 str. 54
Przykład.
*
a f u
* * *
t o s
* * *
r
*
g k m t
* * * *
e h i
* * *
f
*
y
*
Drzewa B (ang. B-Trees)
Drzewa B służą do przechowywania uporządkowanych danych w pamięci zewnętrznej (na
dyskach).
Własności drzewa B rzędu N:
-
Należy utrzymywać minimalną wysokość drzewa B.
-
Drzewo B musi być wyważone.
-
Wszystkie liście drzewa B pozostają na tym samym poziomie.
-
Nie istnieją puste poddrzewa powyżej poziomu liści.
-
Korzeń może nie mieć dzieci, jeśli drzewo B zawiera tylko jeden węzeł.
-
Każdy z węzłów zawiera co najmniej N kluczy i co najwyżej 2N kluczy. Węzeł
jest pełny jeśli zawiera 2N kluczy. Korzeń może zawierać tylko 1 klucz dla
dowolnego N
-
Drzewo B jest budowane przez wstawianie klucza do liścia. Drzewo wzrasta
"wszerz" i "wzwyż" na skutek podziału węzłów pełnych.
-
W trakcie wprowadzania nowego elementu danych do drzewa B zachowywany
jest odpowiedni porządek. Klucz wprowadzanej danej jest porównywany z
kluczem (kluczami) w korzeniu i po kolei z kluczami węzłów pośrednich, aż
trafia do odpowiedniego liścia (węzła X). Jeśli X jest pełen, to następuje jego
podział na dwa i klucz ze środkowej pozycji jest wstawiany do rodzica węzła X,
co również może spowodować podział. W ten sposób podziały mogą propagpwać
aż do korzenia. Jeśli natomiast węzeł X nie jest pełny, to nowa dana jest
umieszczana tak aby zachować porządek w węźle. Po wstawieniu węzła drzewo
musi zachowywać własności drzewa B.
-
Po usunięciu klucza drzewo musi zachowywać własności drzewa B.
AISD wer. 2 str. 55
Przykład budowy drzewa B rzędu 2
Wstawiamy element 33
33
0 0
Wstawiamy elementy 60, 5 15
5 15 33 60
0 0 0 0 0
Wstawiamy element 25
15
* *
5 25 33 60 (nie jest B)
0 0 0 0 0 0
25
* *
5 15 33 60
0 0 0 0 0 0
Wstawiamy element 12
25
* *
5 12 15 33 60
0 0 0 0 0 0 0
Wstawiamy element 45
25
* *
5 12 15 33 45 60
0 0 0 0 0 0 0 0
Wstawiamy element 70
25
* *
5 12 15 33 45 60 70
0 0 0 0 0 0 0 0 0
Wstawiamy element 35
25 45
* * *
5 12 15 33 35 60 70
0 0 0 0 0 0 0 0 0 0
Wstawiamy element 7
25 45
* * *
5 7 12 15 33 35 60 70
0 0 0 0 0 0 0 0 0 0 0
W drzewie B nie można umieszczać duplikatów kluczy.
Częstość podziału węzłów można zmniejszyć przez zwiększenie stopnia drzewa B.
AISD wer. 2 str. 56
Usuwanie klucza z drzewa B
1.
Usuwanie klucza z korzenia, który ma więcej niż 1 klucz i jest liściem.
2.
Usuwanie klucza z korzenia, który ma więcej niż 1 klucz i nie jest liściem.
Zastąpienie usuniętego klucza najmniejszym kluczem prawego poddrzewa
usuwanego klucza.
Zastąpienie usuniętego klucza największym kluczem lewego poddrzewa
usuwanego klucza.
Połączenie lewego i prawgo poddrzewa jeśli mają po N kluczy.
3.
Usuwanie klucza z korzenia, który ma 1 klucz i nie jest liściem. (jak 2.)
4.
Usuwanie klucza z korzenia, który ma 1 klucz i jest liściem.
5.
Usuwanie klucza z liścia, który ma co najmniej (N+1) kluczy.
6.
Usuwanie klucza z liścia, który ma N kluczy.
Weź klucz od lewego sąsiada, jeśli ma on co najmniej (N+1) kluczy.
Weź klucz od prawego sąsiada, jeśli ma on co najmniej (N+1) kluczy.
Lewy sąsiad ma dokładnie N kluczy. Połącz węzeł bieżący (z którego usuwamy
klucz) z lewym sąsiadem.
Prawy sąsiad ma dokładnie N kluczy. Połącz węzeł bieżący (z którego usuwamy
klucz) z prawym sąsiadem.
Przykład.
25 45
* * *
5 7 12 15 33 35 60 70
0 0 0 0 0 0 0 0 0 0 0
Usuwamy węzeł 7
25 45
* * *
5 12 15 33 35 60 70
0 0 0 0 0 0 0 0 0 0
Usuwamy węzeł 25
15 45
* * *
5 12 33 35 60 70
0 0 0 0 0 0 0 0 0
Usuwamy węzeł 33
45
* *
5 12 15 35 60 70
0 0 0 0 0 0 0 0
Usuwamy węzeł 45
35
* *
5 12 15 60 70
0 0 0 0 0 0 0
AISD wer. 2 str. 57
Usuwamy węzeł 12
35
* *
5 15 60 70
0 0 0 0 0 0
Usuwamy węzeł 15
5 35 60 70
0 0 0 0 0
Drzewa BB (ang. Binary B-Trees)
Drzewo BB (drzewo 2-3) jest drzewem B rzędu 1. Węzeł drzewa zawiera jeden klucz (K)
oraz 3 wiązania: lewe, prawe i poziome. Jeżeli wiązanie lewe nie jest puste, to klucze tego
poddrzewa są mniejsze niż klucz K. Dla wiązań prawego i poziomego wskazywane przez nie
poddrzewa mają klucze większe.
1.
Dla żadnego węzła w drzewie nie mogą równocześnie występować wiązania
poziome i prawe.
2.
Poziome połączenia nie występują jedno po drugim, tzn. jeśli węzeł X ma
poziome połączenie, to korzeń poddrzewa wskazanego przez nie musi mieć
poziome połączenie "puste".
3.
Wysokości wszystkich następników (poddrzew) dla każdego węzła w drzewie są
takie same; przy liczeniu wysokości drzewa połączenia poziome jej nie
zwiększają.
Wstawianie do drzew BB wykonuje się tak jak do drzew B, a równoważenie wykonywane
jest według 5 schematów.
Schematy równoważenia drzewa BB.
A B C A B
a B A c d a b C
1
b c a b c d
3 5
B
A B
A C
a b c
a b c d
B 4
A C
A c 2
a B d
a b
b c
AISD wer. 2 str. 58
Przykład. Wstawianie kluczy do drzewa BB. Klucze: A, Z, Y, X, B
1. A
2. A Z
3. A Z 4 Y
Y A Z
4. Y
A X Z
5. Y Y B Y
A X Z 4 B Z 2 A X Z
B A X
Grafy
Definicja. Grafem G nazywamy parę zbioru węzłów V, oraz zbioru krawędzi E, takich że dla
skończonego n
G = {V, E}, gdzie
V = {V
1
, V
2
, ..., V
n
}
E = {E
ij
= (V
i
, V
j
), 1 <= i <= n, 1 <= j <= n }
Krawędź, (albo łuk) określa połączenie między dwoma węzłami. Krawędź nieskierowana
jest definiowana przez parę węzłów np. (A, B). Krawędź skierowana jest określona przez
uporządkowaną parę węzłów <A, B>, gdzie A jest początkiem, a B końcem krawędzi.
Graf skierowany (ang. directed graph - digraph) składa się z węzłów i krawędzi
skierowanych.
Dwa węzły są sąsiednie, jeśli występuje między nimi krawędź. Cyklem (lub pętlą) w grafie
nazywamy taką ścieżkę w grafie, której początek i koniec są w tym samym węźle. Graf jest
acykliczny, jeśli nie ma w nim cykli. Krawędź tworzy cykl, jeśli łączy ze sobą ten sam węzeł.
Stopniem węzła w grafie (deg(A)) nazywamy liczbę krawędzi wychodzących z tego węzła.
Krawędź będąca pętlą dodaje 2 do stopnia węzła. W grafie skierowanym stopniem
wejściowym węzła (ang. in-degree) (deg(A)) nazywamy liczbę krawędzi zakończonych w tym
węźle. Stopień wyjściowy (ang. out-degree) (deg
+
(A)) to liczba krawędzi rozpoczynających
się w danym węźle. Węzeł A jest odizolowany (niepołączony) jeśli deg(A)=0. Graf jest
połączony (ang. connected), jeśli nie zawiera węzłów odizolowanych. Z krawędzią może być
związana wartość zwana wagą (np. koszt, odległość).
Ścieżka z węzła A do węzła B w grafie skierowanym (nieskierowanym) to sekwencja
krawędzi skierowanych (nieskierowanych) oznaczonych przez p(A, B). Ścieżka ma długość
m, jeśli w jej skład wchodzi m krawędzi (m+1 węzłów)
AISD wer. 2 str. 59
V
0
=A, V
1
, V
2
, ... V
m
=B
Najkrótszą ścieżką w grafie ważonym jest ścieżka z minimalną sumą wag krawędzi.
Graf można przeglądać według dwóch metod:
- przeglądanie w głąb (ang. depth-first traversal DFS)
- przeglądanie wszerz (ang. breadth-first traversal BFS)
Przeglądanie grafu nie jest jednoznaczne. Może być rozpoczynane od dowolnego
węzła. Zastosowania: sprawdzanie połaczenia, wyznaczanie najkrótszej (wagowo) ścieżki.
Aby uniknąć wielokrotnego uwzględniania tego samego węzła, do którego można
dotrzeć z różnych stron stosuje się wskaźnik (ang. flag) informujący, czy dany węzeł był już
wizytowany.
Przeglądanie w głąb zwane jest również przeglądaniem z powrotami (ang.
backtracking) i polega na posuwaniu się jak najdalej od bieżącego węzła, powrocie i
analizowaniu kolejnych możliwości.
Rekursywny algorytm DFS ma następującą postać:
// Wskaźniki wizytacji mają wartość FALSE dla wszystkich
// węzłów w grafie
Depth_First_Search (VERTEX A)
{
Visit A;
Set_ON_Visit_Flag (A); // to TRUE
For all adjecent vertices A
i
(i = 1, ..., p) of A
if (A
i
has not been previously visited)
Depth_First_Search (A
i
);
}
Przykład.
Węzeł
Sąsiedzi
A B C D
A
B, H
B
A, C, G, F, H
C
B, D, F
H G F E
D
C, E, F
E
D, F
F
B, C, D, E, G
G
B, F, H
H
A, B, G
Przeglądanie wszerz (BFS) polega na przeglądaniu danego węzła i wszystkich jego sąsiadów,
a potem po kolei sąsiadów sąsiadów, itd.
AISD wer. 2 str. 60
Algorytm BFS
1. Odwiedź węzeł startowy A.
2. Wstaw węzeł A do kolejki.
3. Dopóki kolejka nie jest pusta wykonuj kroki 3.1 - 3.2
3.1. Weź węzeł X z kolejki
3.2. Dla wszystkich sąsiadów X
i
(X-a) wykonuj
3.2.1
Jeśli X
i
, był odwiedzony zakończ jego przetwarzanie.
3.2.2
Odwiedź węzeł X
i
.
3.2.2
Wstaw do kolejki węzeł X
i
.
Definicja. Graf w ujęciu ATD jest strukturą danych, która zawiera skończony zbiór węzłów i
skończony zbiór krawędzi oraz operacje pozwalające na definiowanie, manipulowanie oraz
abstrahowanie pojęć węzłów i krawędzi.
Przykładowe metody klasy reprezentującej graf
Twórz i inicjalizuj obiekt grafu.
Usuń obiekt grafu.
Sprawdź, czy zbiór węzłów jest pusty.
Sprawdź, czy zbiór krawędzi jest pusty.
Sprawdź, czy dwa węzły są sąsiednie.
Buduj graf z danego zbioru węzłów i krawędzi.
Dodaj węzeł do grafu.
Szukaj węzła przechowującego zadany klucz.
Usuń węzeł przechowujący zadany klucz.
Modyfikuj informację w węźle o zadanym kluczu.
Dodaj krawędź do grafu.
Szukaj krawędź identyfikowaną przez zadany klucz.
Usuń krawędź identyfikowaną przez zadany klucz.
Przejdź graf metodą w głąb.
Przejdź graf metodą wszerz.
Drukuj obiekt grafu.
Określ atrybuty grafu.
Znajdź (oblicz) najkrótszą ścieżkę w grafie.
Implementacja grafu przy pomocy macierzy powiązań (sąsiedztwa).
Dla grafu bez wagi
1, jeśli A
i
jest sąsiednie z A
j
Adj_Mat[i][j] =
0, jeśli A
i
nie jest sąsiednie z A
j
AISD wer. 2 str. 61
Dla grafu z wagami
w
ij
, jeśli A
i
jest sąsiednie z A
j
Adj_Mat[i][j] =
0, jeśli A
i
nie jest sąsiednie z A
j
Dla grafu nieskierowango macierz powiązań jest symetryczna
Adj_Mat[i][j] = Adj_Mat[j][i]
Do oznaczenia braku sąsiedztwa zamiast 0 stosuje się czasami oznaczenie nieskończoności.
Algorytm Dijkstry wyznaczania najkrótszej ścieżki w grafie.
1.
Dany jest graf ważony G ze zbiorem n węzłów:
A = A
0
, A
1
, A
2
, ... , A
n-1
= Q,
krawędzi (A
i
, A
j
) (lub <A
i
, A
j
>) i wag w
ij
2.
Zbiór roboczy węzłów S jest początkowo pusty. Każdemu węzłowi jest
przypisywana etykieta L, która ma następujące znaczenie: L(A
k
) oznacza wagę
najkrótszej ścieżki od węzła początkowego A do węzła A
k
. L(A)=0 i dla
wszystkich węzłów L(A
i
)=nieskończoność (np. 99999999)
3.
(Iteracja) Dopóki węzeł docelowy Q nie jest w zbiorze S wykonuj kroki 3.1 - 3.5.
3.1.
Wybierz najbliższy węzeł A
k
, taki że nie należy do S i L(A
k
) jest najmniejsze
spośród wszystkich węzłów nie należących do S.
3.2.
Dodaj A
k
do zbioru S
3.3.
Jeśli A
k
=Q, zwróć L(A
k
) i zakończ
3.4.
Dla wszystkich sąsiadów A
j
węzła A
k
, które nie są w S modyfikuj ich etykietę L
przez minimum z L(A
j
) i z L(A
k
)+w
kj
3.5.
Wróć do początku kroku 3.
4.
L(Q) jest wagą najkrótszej ścieżki od A do Q. Droga taka została znaleziona.
class Graph {
public:
virtual int build_graph(void) = 0;
virtual int is_graph_empty(void) = 0;
virtual void find_shortest_path(void) = 0;
virtual int get_min(void) = 0;
virtual void show_paths(KEY_TYPE src_vrtx, KEY_TYPE dst_vrtx) = 0;
virtual int check_graph(void) = 0;
virtual void print_graph(void) = 0;
};
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <stdlib.h>
typedef int KEY_TYPE;
AISD wer. 2 str. 62
#include "bc_graph.h" // For base class "Graph"
typedef int WEIGHT; // weight = arc length
const int HUGE_WEIGHT = 999999999;
// NOTFOUND is a phase of a vertex in the graph
// where the vertex has not been found yet via
// the relax() function
const int NOTFOUND = 0;
// FOUND is a phase of a vertex in the graph where
// the vertex has been found but the shortest
// path not yet determined
const int FOUND = 1;
// TAKEN is a phase of a vertex in the graph where
// the vertex's shortest path has been found.
const int TAKEN = 2;
#define ERROR1 "ERROR, TOO MANY VERTICES FOR THIS CONFIG"
#define ERROR2 "ERROR, NEGATIVE LENGTHS"
#define ERROR3 "ERROR, INVALID SOURCE VERTEX"
#define ERROR4 "ERROR, INVALID DESTINATION VERTEX"
class Weighted_DiGraph : private Graph {
private:
int MAX_VERTEX;
// adjacency matrix of the directed graph
// int WT_ADJACENCY_MATRIX[MAX_VERTEX +1][MAX_VERTEX +1];
WEIGHT *WT_ADJACENCY_MATRIX;
// VERTEX structure of a vertex which contains
// the vertexs' phase and shortest path.
struct VERTEX {
int shortestpath;
char phase;
};
VERTEX *VERTICES;
int NUM_OF_VERTICES;
// For store & retrieve A[i][j]
WEIGHT &adj_matrix (int i, int j)
{ return WT_ADJACENCY_MATRIX [i* (MAX_VERTEX + 1) + j]; }
void relax(int);
void init_digraph(void);
void init_digraph_vertices(void);
int check_digraph(void);
int create_directed_graph(void);
void Dijkstra_shortest_path(void);
public:
Weighted_DiGraph(int max_vrtx);
~Weighted_DiGraph();
void intro (void);
int build_graph(void) {return create_directed_graph();}
int is_graph_empty(void) { return 0;}
void find_shortest_path(void) {Dijkstra_shortest_path();}
int get_min(void);
void show_paths(KEY_TYPE src_vrtx, KEY_TYPE dst_vrtx);
void show_paths();
int check_graph(void) { return check_digraph();}
void print_graph(void) {printf("\nNot implemented\n");}
};
Weighted_DiGraph::Weighted_DiGraph (int max_vrtx)
AISD wer. 2 str. 63
{
MAX_VERTEX = max_vrtx;
WT_ADJACENCY_MATRIX = new WEIGHT [(MAX_VERTEX + 1) * (MAX_VERTEX + 1)];
VERTICES = new VERTEX [MAX_VERTEX + 1];
}
Weighted_DiGraph::~Weighted_DiGraph () // Destructor
{
delete [] WT_ADJACENCY_MATRIX;
delete [] VERTICES;
}
int Weighted_DiGraph::create_directed_graph (void)
{
char answer[4];
WEIGHT new_wt;
printf (" Enter number of vertices in graph ==> ");
scanf ("%d", &NUM_OF_VERTICES);
if (NUM_OF_VERTICES > MAX_VERTEX) {
printf("%s \n", ERROR1);
return (0);
}
if (NUM_OF_VERTICES < 1) // invalid input
return (0);
init_digraph();
printf("\n");
for (int i = 1; i <= NUM_OF_VERTICES; i++) {
for (int j = 1; j <= NUM_OF_VERTICES; j++) {
printf("%s %d to vertex %d (Y/N) ==> ",
" Is there a path from vertex",i,j);
scanf("%s", answer);
if ((answer[0] == 'y') || (answer[0] == 'Y')) {
printf(" Enter path length ==> ");
scanf("%d", &new_wt);
adj_matrix(i, j) = new_wt;
}
}
}
return (1);
}
void Weighted_DiGraph::Dijkstra_shortest_path(void)
{
int source, // source vertex
destination, // destination vertex
min; // index of vertex with shortest path
// error = 1 if there is a negative path weight or
// impossible source and destination vertices.
int error;
// size = count of the number of vertexs which have
// had their shortest paths determined.
int size;
error = check_digraph();
if (error) {
printf(" %s \n", ERROR2);
return;
}
error = 1;
AISD wer. 2 str. 64
while (error) {
printf("\n Enter the Source Vertex Number ==> ");
scanf("%d", &source);
if ((source >= 1) && (source <= NUM_OF_VERTICES))
error = 0;
else
printf("%s \n", ERROR3);
}
error = 1;
while (error) {
printf("\n Enter the Destination Vertex Number ==> ");
scanf("%d", &destination);
if ((destination >= 1) &&
(destination <= NUM_OF_VERTICES))
error = 0;
else
printf(" %s \n", ERROR4);
}
// put all vertex phases to NOTFOUND and
// shortestpath lengths to HUGE_WEIGHT
init_digraph_vertices();
VERTICES[source].shortestpath = 0;
VERTICES[source].phase = FOUND;
size = 0;
while (size++ < NUM_OF_VERTICES) {
// return vertex with minimum shortest path
min = get_min();
// this vertex is no longer available, i.e., TAKEN.
VERTICES[min].phase = TAKEN;
// determine shortest paths from a given vertex.
relax (min);
}
// show the shortest path from source to destination.
show_paths (source, destination);
}
void Weighted_DiGraph::init_digraph(void)
{
int i, j;
for (i = 1; i <= NUM_OF_VERTICES; i++)
for (j = 1; j <= NUM_OF_VERTICES; j++)
adj_matrix(i, j) = 0;
}
void Weighted_DiGraph::init_digraph_vertices(void)
{
for (int i = 1; i <= NUM_OF_VERTICES; i++) {
VERTICES[i].phase = NOTFOUND;
VERTICES[i].shortestpath = HUGE_WEIGHT;
}
}
// get_min():
// Returns shortest path to an available vertex
//
int Weighted_DiGraph::get_min(void)
{
int min = HUGE_WEIGHT, // min path found so far
AISD wer. 2 str. 65
index = 0; // vertex index
for (int i = 1; i <= NUM_OF_VERTICES; i++) {
if (VERTICES[i].phase == FOUND) { // vertex is available
if (VERTICES[i].shortestpath < min) {
// new minimum
index = i;
min = VERTICES[i].shortestpath;
}
}
}
return index;
}
// relax():
// Determines shortest paths to vertices
// reachable from a given vertex.
//
void Weighted_DiGraph::relax(int min)
{
for (int i = 1; i <= NUM_OF_VERTICES; i++) {
// WT_ADJACENCY_MATRIX[min][i] == adj_matrix(min, i)
if (adj_matrix(min, i) &&
(VERTICES[i].phase != TAKEN)) {
// there is a path and the end vertex is available
VERTICES[i].phase = FOUND;
if ((VERTICES[min].shortestpath +
adj_matrix(min, i)) < (VERTICES[i].shortestpath))
// a shorter path then previously found is available.
// Store newly found shortest path.
VERTICES[i].shortestpath = VERTICES[min].shortestpath +
adj_matrix(min, i);
}
}
}
void Weighted_DiGraph::show_paths(int source, int destination)
{
if (VERTICES[destination].shortestpath < HUGE_WEIGHT)
printf("\n Shortest %s %d to %d = %d\n",
"path from vertex", source, destination,
VERTICES[destination].shortestpath);
else // vertex was not reachable from source
printf("\nNo path available %s %d to %d\n",
"from vertex", source, destination);
}
int Weighted_DiGraph::check_digraph (void)
{
int i, j;
for (i = 1; i <= NUM_OF_VERTICES; i++)
for (j = 1; j <= NUM_OF_VERTICES; j++)
// if (WT_ADJACENCY_MATRIX[i][j] < 0)
if (adj_matrix(i, j) < 0)
return 1;
return 0;
}
// intro(): Prints introduction and limitation.
AISD wer. 2 str. 66
void Weighted_DiGraph::intro (void)
{
printf ("\n *** OOP IMPLEMENTATION OF %s %s %s",
"WEIGHTED DIGRAPH ***",
"\n USING ADJACENCY MATRIX AND",
"\n DIJKSTRAS SHORTEST PATH");
printf ("\n\n %s %s %s %s %s %s \n\n",
"This program will create a directed graph via",
"\n inputs from the screen, determine the shortest",
"\n path from a given source to a given destination,",
"\n and output the shortest path length.",
"\n\n NOTE: This program currently has a limitation",
"\n of no more than 100 vertices in the digraph.");
}
void main(void)
{
Weighted_DiGraph digraph_obj(100);
int success;
digraph_obj.intro();
success = digraph_obj.build_graph();
if (success)
digraph_obj.find_shortest_path();
}
Implementacja grafu przy pomocy listy powiązań (sąsiedztwa).
Przykład
B
C
A *-> (B,7)*-> (D,5)*-> (F,6)NULL
B *-> (C,10)NULL
A
D
C *-> (D,20)NULL
D NULL
F
E
E *-> (D,5)NULL
F *-> (E,8)NULL
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
typedef int KEY_TYPE;
#include "bc_graph.h" // For base class "Graph"
const int HUGE_WEIGHT = 999999999; // for infinity
enum VISIT_FLAG {TRUE, FALSE};
class Wt_DiGraph : private Graph {
private:
typedef char DATA_TYPE;
typedef int WEIGHT;
typedef int INDEX;
typedef struct ADJACENT_VERTEX {
KEY_TYPE vrtx_key;
WEIGHT weight;
AISD wer. 2 str. 67
ADJACENT_VERTEX *next;
} *ADJACENCY_LIST_PTR;
typedef struct VERTEX {
KEY_TYPE vrtx_key;
DATA_TYPE data;
WEIGHT label;
VISIT_FLAG visited;
int hops, path[20];
ADJACENCY_LIST_PTR adj_list_hd_ptr;
} *VERTEX_PTR;
// VERTEX_ARY[MAX_VERTEX] :An array of vertices
VERTEX_PTR VERTEX_ARY;
int MAX_VERTEX;
INDEX TAIL;
int build_wt_digraph();
void print_digraph(void);
public:
Wt_DiGraph (int max_no_of_vertices);
~Wt_DiGraph();
int build_graph(void) {return build_wt_digraph();}
int is_graph_empty(void);
void find_shortest_path(void);
int get_min(void) {return 0;} // Not implemented
void show_paths(int, int) {} // Not implemented
int check_graph(void) {return 0;} // Not implemented
void print_graph(void) { print_digraph(); }
VERTEX_PTR create_vertex();
void intro (void);
void add_vertex(KEY_TYPE, DATA_TYPE);
INDEX search_vertex(KEY_TYPE);
void add_adjacent_vrtx(KEY_TYPE, KEY_TYPE, WEIGHT);
void get_src_dst_vertices(KEY_TYPE *src_vrtx_key,
KEY_TYPE *dst_vrtx_key);
};
Wt_DiGraph::Wt_DiGraph(int max_no_of_vertices)
{
MAX_VERTEX = max_no_of_vertices;
VERTEX_ARY = new VERTEX[MAX_VERTEX];
TAIL = -1; // array of vertices is empty
}
Wt_DiGraph::~Wt_DiGraph()
{
if (!is_graph_empty()) {
for (INDEX i = 0; i <= TAIL; i++) {
ADJACENCY_LIST_PTR
adjacency_ptr = VERTEX_ARY[i].adj_list_hd_ptr;
while (adjacency_ptr != NULL) {
ADJACENCY_LIST_PTR tmp_ptr = adjacency_ptr;
adjacency_ptr = adjacency_ptr->next;
delete tmp_ptr;
}
}
}
delete [] VERTEX_ARY;
AISD wer. 2 str. 68
}
int Wt_DiGraph::is_graph_empty(void)
{
return (TAIL == -1);
}
Wt_DiGraph::VERTEX_PTR Wt_DiGraph::create_vertex()
{
VERTEX_PTR new_ptr;
new_ptr = new VERTEX;
if (new_ptr == NULL)
printf("\n create_vertex: alloc failed \n");
return (new_ptr);
}
void Wt_DiGraph::add_vertex(KEY_TYPE new_key, DATA_TYPE new_data)
{
// Is the vertex array full? If so, error msg
if ((TAIL + 1) != MAX_VERTEX) {
VERTEX_ARY[++TAIL].vrtx_key = new_key;
VERTEX_ARY[ TAIL].data = new_data;
VERTEX_ARY[ TAIL].label = 0;
VERTEX_ARY[ TAIL].hops = 0;
VERTEX_ARY[ TAIL].visited = FALSE;
VERTEX_ARY[ TAIL].adj_list_hd_ptr = NULL;
}
else
printf ("\n add_vertex: Array of vertices is full\n");
}
int Wt_DiGraph::build_wt_digraph(void)
{
KEY_TYPE key1, key2;
int n_vertices, edge_weight,
maxweight = HUGE_WEIGHT,
vrtx_ary_index;
printf("\n Enter number of vertices in your Weighted DiGraph:");
scanf("%d", &n_vertices);
if (n_vertices > MAX_VERTEX) {
printf ("\n build_wt_digraph: %s %d \n",
"Number of vertices is more than max",
MAX_VERTEX);
return(0);
}
for (INDEX i = 0; i < n_vertices; i++) {
add_vertex(i, i);
printf("\n Vertex: %2d has been created.", i);
}
printf("\n");
for (i = 0; i < n_vertices; i++) {
key1 = (KEY_TYPE) i;
vrtx_ary_index = search_vertex(key1);
for (INDEX j = 0; j < n_vertices; j++) {
key2 = (KEY_TYPE) j;
if (j != i) {
printf(" Enter %s %2d to Vertex %2d: ",
AISD wer. 2 str. 69
"distance from Vertex", i, j);
// printf(" Else enter n/N for next vertex\n");
if (scanf("%d", &edge_weight) == 1) {
getchar(); // if there is an edge then insert it
add_adjacent_vrtx (key1, key2, edge_weight);
printf("%s: %2d to Vertex: %2d %s\n",
" Edge from Vertex", i ,j, "was created");
if (maxweight < edge_weight)
maxweight = edge_weight;
} // end of (scanf( ...))
else {
getchar();
printf(" No new edge was created.\n");
}
} // if j != i
} // for j < n_vertexs
} // for i < n_vertexs
return(1);
}
void Wt_DiGraph::print_digraph(void)
{
ADJACENCY_LIST_PTR adjacency_hd_ptr;
printf("\n\n GRAPH VERTICES ADJACENCY LISTS");
printf("\n ============== ===============\n");
if (is_graph_empty()) {
printf("\n Weighted digraph is empty");
return;
}
for (INDEX i = 0; i <= TAIL; i++) {
printf(" %d: ",
VERTEX_ARY[i].vrtx_key);
adjacency_hd_ptr = VERTEX_ARY[i].adj_list_hd_ptr;
while (adjacency_hd_ptr != NULL) {
printf(" %d ->", adjacency_hd_ptr->vrtx_key);
adjacency_hd_ptr = adjacency_hd_ptr->next;
}
printf(" NULL \n");
}
}
Wt_DiGraph::INDEX Wt_DiGraph::search_vertex(KEY_TYPE srch_key)
{
if (!is_graph_empty()) {
for (INDEX i = 0; i <= TAIL; i++)
if (srch_key == VERTEX_ARY[i].vrtx_key)
return (i);
}
return (-1); // not found
}
void Wt_DiGraph::add_adjacent_vrtx(
KEY_TYPE to_adjacent_key,
KEY_TYPE adjacent_vrtx_key, WEIGHT new_weight)
{
INDEX vertex1;
vertex1 = search_vertex (to_adjacent_key);
if (vertex1 == -1) {
printf("\n add_adjacent_vrtx: %s \n",
AISD wer. 2 str. 70
"To-adjacent vertex not in graph");
return;
}
if (search_vertex (adjacent_vrtx_key) == -1) {
printf("\n add_adjacent_vrtx: %s \n",
"Adjacent vertex not in graph");
return;
}
ADJACENCY_LIST_PTR new_ptr = new ADJACENT_VERTEX;
if (new_ptr == NULL)
return;
new_ptr->vrtx_key = adjacent_vrtx_key;
new_ptr->weight = new_weight;
new_ptr->next = NULL;
new_ptr->next = VERTEX_ARY[vertex1].adj_list_hd_ptr;
VERTEX_ARY[vertex1].adj_list_hd_ptr = new_ptr;
}
void Wt_DiGraph::find_shortest_path(void)
{
ADJACENCY_LIST_PTR adjacency_ptr;
VERTEX_PTR end_ptr, min_label_vertex, tmp_vertex;
WEIGHT label, temp, shortest_dist = 0;
INDEX src_vrtx_index, dst_vrtx_index;
KEY_TYPE src_vrtx_key, dst_vrtx_key;
if (is_graph_empty()) {
printf("\n find_shortest_path: Empty graph\n");
return;
}
get_src_dst_vertices(&src_vrtx_key, &dst_vrtx_key);
for (INDEX i = 0; i <= TAIL; i++)
VERTEX_ARY[i].label = HUGE_WEIGHT;
src_vrtx_index = search_vertex (src_vrtx_key);
if (src_vrtx_index == -1) {
printf("\n find_shortest_path: Source vertex %i %s",
src_vrtx_key, "is not in graph");
return;
}
dst_vrtx_index = search_vertex (dst_vrtx_key);
if (dst_vrtx_index == -1) {
printf("\n find_shortest_path: Dest vertex %i %s",
dst_vrtx_key, "is not in graph");
return;
}
end_ptr = &VERTEX_ARY[dst_vrtx_index];
min_label_vertex = &VERTEX_ARY[src_vrtx_index];
min_label_vertex->label = 0;
min_label_vertex->path[min_label_vertex->hops] =
min_label_vertex->vrtx_key;
while (min_label_vertex->vrtx_key != end_ptr->vrtx_key) {
temp = HUGE_WEIGHT;
for (INDEX i = 0; i <= TAIL; i++) {
if ((VERTEX_ARY[i].visited != TRUE) &&
(temp > VERTEX_ARY[i].label)) {
temp = VERTEX_ARY[i].label;
min_label_vertex = &VERTEX_ARY[i];
}
AISD wer. 2 str. 71
}
shortest_dist = min_label_vertex->label;
adjacency_ptr = min_label_vertex->adj_list_hd_ptr;
label = min_label_vertex->label;
while (adjacency_ptr != NULL) {
tmp_vertex = &VERTEX_ARY[search_vertex (
adjacency_ptr->vrtx_key)];
tmp_vertex->label = label + adjacency_ptr->weight;
// Keep shortest path information for each vertex
// starting from source vertex to it
for (i = 0; i < min_label_vertex->hops; i++) {
tmp_vertex->path[i] = min_label_vertex->path[i];
}
tmp_vertex->hops = min_label_vertex->hops;
tmp_vertex->path[tmp_vertex->hops++] =
min_label_vertex->vrtx_key;
// elist_ptr = elist_ptr->next;
adjacency_ptr = adjacency_ptr->next;
} // end of while (adjacency_ptr != NULL)
min_label_vertex->visited = TRUE;
} // end of while (min_label_vertex->vrtx_key ...)
// --- Print shortest path
printf("\n %s: %2d to Vertex: %2d is: %d\n",
"Shortest Distance from Vertex", src_vrtx_key,
dst_vrtx_key, shortest_dist);
printf(" The Shortest Path is: ");
for (i = 0; i < end_ptr->hops; i++)
printf(" %d ->", end_ptr->path[i]);
printf(" %d \n", end_ptr->vrtx_key);
// --- Print number of hops in shortest path
printf(" %s: %2d to Vertex: %2d is: %d\n",
"Number of Hops from Vertex", src_vrtx_key,
dst_vrtx_key, end_ptr->hops);
}
void Wt_DiGraph::get_src_dst_vertices(
KEY_TYPE *src_vrtx_key, KEY_TYPE *dst_vrtx_key)
{
KEY_TYPE vertex1, vertex2;
int num_vertices = 0;
int try1, again;
do {
printf("\n ** To quit enter q/Q **\n");
printf(" ** To calculate shortest %s **\n\n",
"path between two Vertices");
printf(" Enter Source Vertex: ");
try1 = 0;
if (scanf("%d", &vertex1) != 1) {
try1 = 1;
exit (1);
}
// if ((vertex1 < 0) || (vertex1 >= num_vertices)) {
if ((vertex1 < 0) || (vertex1 > TAIL)) {
printf("\n Vertex ** %d ** does not exist\n",
vertex1);
exit(1);
}
getchar();
AISD wer. 2 str. 72
do {
again = 0;
printf(" Enter Destination Vertex: ");
if (scanf("%d", &vertex2) != 1)
again = 1;
if ((vertex2 < 0) ||(vertex2 > TAIL)) {
printf("\n Vertex ** %d ** does not exist\n",
vertex2);
exit (1);
}
getchar();
} while (again);
} while (try1);
*src_vrtx_key = vertex1;
*dst_vrtx_key = vertex2;
}
void Wt_DiGraph::intro(void)
{
printf ("\n *** OOP IMPLEMENTATION OF %s %s %s",
"WEIGHTED DIGRAPH ***",
"\n USING LINKED ADJACENCY LIST AND",
"\n DIJKSTRAS SHORTEST PATH");
printf("\n USAGE: \n %s",
"\n You will first be prompted for number of\n");
printf(" vertices in Digraph, MAX = %d. %s \n",
MAX_VERTEX, "These will be created");
printf("%s %s %s %s %s %s %s",
" and then you will be prompted to create the\n",
" edges with corresponding distance, press n/N\n",
" for the next edge. The Weighted DiGraph will be\n",
" then printed in linearized form. And you will be\n",
" prompted for start vertex, and end vertex of\n",
" path wanted. This will be calculated and\n",
" printed in linearized form. \n");
}
void main(void)
{
Wt_DiGraph lnk_wt_digraph_obj(20);
lnk_wt_digraph_obj.intro();
if (lnk_wt_digraph_obj.build_graph()) {
lnk_wt_digraph_obj.print_graph();
lnk_wt_digraph_obj.find_shortest_path();
}
}