Graflar (Graphs)

Transkript

Graflar (Graphs)

Graflar (Graphs)
z
z
z
z
z
z
Graf gösterimi
Uygulama alanları
Graf terminolojisi
Depth first dolaşma
Breadth first dolaşma
Topolojik sıralama
Yrd.Doç.Dr. M. Ali Akcayol
G. Ü. Bilgisayar Mühendisliği Bölümü
Graflar
z
Graflar bilgi parçaları arasındaki ilişkileri gösterirler.
z
Bir G graf V ile gösterilen node’lardan (verteks) ve E ile
gösterilen kenarlardan (Edge) oluşur. Her kenar iki node’u
birleştirir.
z
Her node bir bilgi parçasını gösterir.
z
Her kenar iki bilgi arasındaki ilişkiyi gösterir ve (u, v) şeklinde
şeklinde
ifade edilir. (u, v) iki node’u gösterir.
node
edge
1
Graflar
Uygulama alanları
Elektronik devreler
Baskı devre kartları (PCB)
Entegre devreler
Ulaşım ağları
Otoyol ağı
Havayolu ağı
Bilgisayar ağları
Lokal alan ağları
İnternet
Veritabanları
Entity-relationship diyagram
Graflar
Örnek gösterim:
z
Aşağıdaki şekilde herbir node üç karakter kodlanmış olarak bir
havaalanını göstermektedir.
z
Herbir kenar iki node arasındaki uçuş rotasını ifade etmekte ve
iki node arasındaki uzaklığı ifade etmektedir.
2555
337
HNL
43
17
LAX
1233
849
ORD
802
SFO
1843
DFW
7
138
2
14
PVD
LGA
1120
10
99
MIA
2
Graflar
Kenar türleri:
Directed edge (Yönlendirilmiş kenar)
z
z
z
z
Sıralı node çiftleriyle ifade edilir. (u, v) ile (v, u) aynı değildir.
İlk node orijin ve ikinci node ise hedef olarak adlandırılır.
Örnek: iki nokta arasındaki uçuş.
Undirected edge (Yönlendirilmemiş kenar)
z
z
z
Sırasız node çiftleriyle ifade edilir. (u, v) ile (v, u) aynı şeyi ifade
ederler.
Örnek: uçuş rotası
Yönlendirilmiş graf
z
z
Bütün kenarları yönlendirilmiş graftır.
Yönlendirilmemiş graf
z
z
Hiçbir kenarı yönlendirilmemiş graftır.
Graflar (Terminoloji)
Komşu (Adjacent)
z
Eğer (u, v) ∈ E ise u ve v node’ları komşudur.
v
(u, v)
u
u ve v komşudur
v ve w komşu değildir
k
w
3
Graflar (Terminoloji - devam)
Yol ve basit yol
z
Bir yol v1 den vk ya kadar sıralı node’ları (v1, v2), (v2, v3), …, (vk-1,
vk) kenarlarıyla birbirine bağlar.
z
Bir basit yolda her bir node sadece bir kez bulunur.
v2
v1
- v2, v3, v4, v2, v1 bir yoldur.
v3
v5
v4
- v2, v3, v4, v5 bir basit yoldur.
Cycle ve basit cycle
z
Bir cycle bir yoldur ve başlama ve bitiş node’ları aynıdır.
z
Bir basit cycle’da başlangıç ve bitiş node’ları hariç tüm node’lar
sadece bir kez bulunur.
v2
v1
- v2, v3, v4, v5 , v3, v2 bir cycle’dır v4
v3
v5
- v2, v3, v4, v2 bir basit cycle’dır
4
Bağlı ve bağlı olmayan graf
z
z
Eğer bir graftaki tüm node’lar arasında en azından bir yol varsa
bağlı graftır.
Eğer bir grafta herhangi iki node arasında yol bulunmuyorsa
bağlı olmayan graftır.
v2
v1
v3
v5
v4
bağlı graf
Bağlı ve bağlı olmayan graf (devam)
v7
v3
v1
v8
v2
v4
v5
v6
v9
bağlı olmayan graf
5
Bağlı eleman (connected component)
z
Eğer bir graf bağlı değilse, bağlı alt gruplara göre parçalanabilir.
Bu parçaların herbirine bağlı eleman denir.
v2
v1
v4
v7
v3
v5
v6
v8
v9
Komple graf
z
Eğer bir graftaki her iki node arasında bir kenar varsa komple
graftır.
3 node ile komple graf
4 node ile komple graf
6
Alt graf
z
G (V, E) şeklinde gösterilen bir grafın alt grafı H(U, F) ise U ⊆ V
ve F ⊆ E olur.
v2
v1
v2
v3
v5
v4
v3
v5
v4
H
G
Ağırlıklandırılmış graf
z
Eğer G (V, E) şeklinde gösterilen bir grafta her E kenarına bir
ağırlık değeri atanmış ise ağırlıklandırılmış graf olarak
adlandırılır.
İstanbul
Ankara
2000
1000
3500
İzmir
G
7
Multigraf
z
Multigraf iki node arasında birden fazla kenara sahip olan veya
bir node’un kendi kendisini gösteren kenara sahip olan graftır.
Multiple edge
Self edge
z
z
z
z
a,b ve d kenarları V node’unun kenar bağlantılarıdır.
X node’unun derecesi 5’ tir.
h ve i çoklu (multiple) kenarlardır.
j kendi kendisine döngüdür (self loop).
a
U
V
b
d
h
Z
X
c
e
W
j
i
g
f
Y
8
Yönlendirilmiş graf (Directed graph - Digraph)
z
Eğer G (V, E) şeklinde gösterilen bir grafta her E kenarı bir
yöne (directed edge) sahipse G yönlendirilmiş graftır.
İstanbul
Ankara
1000
Directed edge
2000
3500
İzmir
G
Graflar (Oluşturulması)
z Komşu
matrisi (Adjacency matrix)
Graf iki boyutlu matrisle gösterilir.
z Komşu
listesi (Adjacency list)
Graph n elemanlı m tane bağlı listeyle
gösterilir. n ilgili node’a komşu olan node
sayısını, m ise toplam node sayısını ifade eder.
9
Graflar (Oluşturulması-Komşu Matrisi)
z
Yönlendirilmiş graf için komşu matrisi
Matris[i][j] = 1
0
if (vi, vj)∈E
if (vi, vj)∉E
2
3
4
5
v1 v2 v3 v4 v5
v2
v1
1
v3
v5
v4
G
1 v1 0
1
0
0
0
2 v2 0
0
0
1
0
3 v3 0
1
0
1
0
4 v4 0
0
0
0
0
5 v5 0
0
1
1
0
z
Ağırlıklandırılmış ancak yönlendirilmemiş graf için
komşu matrisi
Matris[i][j] = w(vi, vj)
∞
v1
v2
5
4
G
v3
2
3
8
v4
if (vi, vj)∈E or (vj, vi)∈E
otherwise
7
v5
1
2
3
4
5
v1
v2
v3
v4
v5
1
v1
∞
5
∞
∞
∞
2
v2
5
∞
2
4
∞
3
v3
∞
2
∞
3
7
4
v4
∞
4
3
∞
8
5
v5
∞
∞
7
8
∞
10
Örnek
1
1
2
3
1
2
3
1
0
0
1
2
0
1
1
2
3
1
0
0
1
2
3
4
3
4
1
0
1
1
0
2
1
0
0
0
3
1
0
0
0
4
0
0
0
0
Graflar (Oluşturulması-Komşu Listesi)
z
Yönlendirilmiş graf için komşu listesi
1 v1 → v2
v2
v1
v3
v5
v4
2 v2 → v4
3 v3 → v2 → v4
4 v4
5 v5 → v3 → v4
G
11
z
Yönlendirilmiş ve ağırlıklandırılmış graf için komşu
listesi
v2
v1
5
4
v4
v3
2
3
8
7
v5
1
2
3
4
5
G
v1
v2
v3
v4
v5
→
→
→
→
→
v2(5)
v1(5)
v2(2)
v2(4)
v3(7)
→
→
→
→
v3(2) → v4(4)
v4(3) → v5(7)
v3(3) → v5(8)
v4(8)
Örnek
1
1
2
3
1 Æ 3
2 Æ 2
3 Æ 1Æ2
2
1
2
3
4
Æ
Æ
Æ
Æ
4
3
2 Æ3
1
1
12
Graflar (Komşu Matrisi-Komşu Listesi)
z
Avantajları dezavantajları
Komşu matrisi
z Çok fazla alana ihtiyaç duyar.
z Daha az hafızaya ihtiyaç duyulması için sparse matris
tekniklerinin kullanılması gerekir.
z Herhangi iki node’un komşu olup olmadığına çok kısa
sürede karar verilebilir.
Komşu listesi
z Bir node’un tüm komşularına hızlı bir şekilde ulaşılır.
z Daha az alana ihtiyaç duyar.
z Oluşturulması matrise göre daha zor olabilir.
Graflar (Dolaşma - Traversal)
z
Depth first dolaşma
z Bir v node’una gidildikten sonra v node’unun bir
komşusu seçilir ve ziyaret edilir. Ardından onun bir
komşusu seçilir ve ard arda komşu seçimi yapılarak devam
edilir. Komşu kalmadığında geri dönülür.
z
Breadth first dolaşma
z Bir v node’una gidildikten sonra v node’unun sırasıyla
tüm komşu node’larına gidilir ardından tüm komşu
node’ların komşu node’larına gidilir.
13
z
Depth first arama işlem adımları
Önce bir başlangıç node’u seçilir ve ziyaret edilir.
Seçilen node’un bir komşusu seçilir ve ziyaret edilir.
3. 2.adım ziyaret edecek komşu kalmayıncaya kadar tekrar
edilir.
4. Komşu kalmadığında tekrar geri dönülür ve önceki ziyaret
edilmiş node’lar için adım 2 ve 3 tekrar edilir.
1.
2.
z
Depth first arama
0
1.
1
2.
4
2
3
5
7
4.
5.
6
8
3.
s node’unu seç
visit s
// örn. ekrana yaz
for each edge <s, U>
// U komşu node
if U is not visit
DFS(G, U)
9
14
z
Depth first arama
0
3
1
4
2
3
0
5
7
6
9
8
z
Depth first arama
0
0
3
1
7
4
2
3
5
7
6
8
9
15
z
Depth first arama
0
0
3
1
7
4
2
3
8
5
7
6
9
8
z
Depth first arama
0
0
3
1
7
4
2
3
8
9
5
7
6
8
9
16
z
Depth first arama
0
0
3
1
7
4
2
3
9
5
7
8
6
6
9
8
z
Depth first arama
0
0
3
1
7
4
2
3
8
9
5
6
2
7
6
8
9
17
z
Depth first arama
0
0
3
1
7
4
2
3
8
9
5
6
2
7
6
5
9
8
z
Depth first arama
0
0
3
1
7
4
2
3
8
9
5
6
2
7
6
8
5
9
18
z
Depth first arama
0
0
3
1
7
4
2
3
8
9
5
7
6
2
6
5
4
9
8
z
Depth first arama
0
0
3
1
7
4
2
3
8
9
5
6
2
7
6
8
5
9
4
1
19
z
Depth first arama
0
0
3
1
7
4
2
3
8
9
5
6
2
7
6
5
4
1
9
8
z
Depth first arama
0
0
3
1
7
4
2
3
8
9
5
6
2
7
6
8
5
9
4
1
20
z
Depth first arama
0
0
3
1
7
4
2
3
8
9
5
6
2
7
6
5
4
1
9
8
z
Depth first arama
0
0
3
1
7
4
2
3
8
9
5
6
2
7
6
8
5
9
4
1
21
z
Depth first arama
0
0
3
1
7
4
2
3
8
9
5
6
2
7
6
8
5
9
4
1
z
Breadth first arama işlem adımları
1. Breadth first arama ağaçlardaki level order aramaya
benzer.
2. Seçilen node’un tüm komşuları sırayla seçilir ve ziyaret
edilir.
3. Her komşu queue içerisine atılır.
4. Komşu kalmadığında Queue içerisindeki ilk node alınır ve
2.adıma gidilir.
22
z
Breadth first arama
0
0
1
4
2
3
5
7
6
9
8
0
z
Breadth first arama
0
0
1
3
1
4
2
3
2
5
7
6
9
8
123
23
z
Breadth first arama
0
0
1
3
4
2
3
7
8
2
1
6
5
7
6
9
8
68712
z
Breadth first arama
0
0
1
3
4
2
3
7
8
2
6
4
1
5
5
7
6
9
8
456871
24
z
Breadth first arama
0
0
1
3
4
2
3
7
8
2
6
4
1
5
5
7
6
9
8
45687
z
Breadth first arama
0
0
1
3
4
2
3
7
8
2
6
4
1
5
5
7
6
9
8
4568
25
z
Breadth first arama
0
0
1
3
4
2
3
7
6
4
1
5
9
5
7
8
2
6
9
8
9456
z
Breadth first arama
0
0
1
3
4
2
3
5
7
7
8
2
6
4
1
5
9
6
9
8
9456
26
z
Breadth first arama
0
0
1
3
4
2
3
7
6
4
1
5
9
5
7
8
2
6
9
8
945
z
Breadth first arama
0
0
1
3
4
2
3
5
7
7
8
2
6
4
1
5
9
6
9
8
94
27
z
Breadth first arama
0
0
1
3
4
2
3
7
6
4
1
5
9
5
7
8
2
6
9
8
9
z
Breadth first arama
0
0
1
3
4
2
3
5
7
7
8
2
6
4
1
5
9
6
8
9
28
Graflar (Toplojik sıralama)
z
Topolojik sıralama
z Toplojik sıralama bir graftaki tüm node’ların doğrusal
sıralamasıdır.
z Node’lar arasında öncelik sırası gözönüne alınır.
b
a
c
d
e
Örnekteki grafta topolojik sıralama aşağıdaki gibi
yapılabilir.
z
1- a, c, b, e, d
2- c, a, b, e, d
a
b
c
e
d
Graflar
Haftalık Ödev:
z 10 tane şehir için bir graf yapısı oluşturunuz. Her
şehirden komşu şehirlere olan uzaklık kenar ağırlıkları
200
olarak kullanılacaktır.
10
z
Herhangi bir şehirden
başlayarak tüm şehirleri
dolaşmak için gerekli olan
algoritmayı depth first
dolaşmayla yapınız.
1
90
200
5
110
230
6
125
50
8
4
75
160
220
7
80
2
3
95
100
9
29

Graflar (Graphs)

Transkript

Benzer belgeler

İKİNCİ ÖĞRETİM BÖLÜMLERİMİZDEN %10`a GİREN

Sistem Uzmanı – BASIS

İnşaat Mühendisliği tanıtım sunusu için tıklayınız.

Graf Üzerinde Dolaşma

TESTBOX 2010 - Teknik Destek Grubu

2003 Ekim - İTÜ Uçak ve Uzay Bilimleri Fakültesi

Yürütücü - Ege Üniversitesi Mühendislik Fakültesi Makina

Nodejs Kitap