Graflar (Graphs)

z Graf gösterimi
z Uygulama alanları
z Graf terminolojisi
z Depth first dolaşma
z Breadth first dolaşma
z Topolojik sıralama

[Link]ç.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

G. Ü. Bilgisayar Mühendisliği Bölümü

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

G. Ü. Bilgisayar Mühendisliği Bölümü

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.

849 PVD
1843 ORD 2
SFO 14
802

43 LGA
17
337

7
HNL 2555 138 10
99
1233
LAX DFW 1120
MIA

G. Ü. Bilgisayar Mühendisliği Bölümü

2
Graflar

Kenar türleri:

z Directed edge (Yönlendirilmiş kenar)

z Sıralı node çiftleriyle ifade edilir. (u, v) ile (v, u) aynı değildir.
z İlk node orijin ve ikinci node ise hedef olarak adlandırılır.
z Örnek: iki nokta arasındaki uçuş.
z Undirected edge (Yönlendirilmemiş kenar)
z Sırasız node çiftleriyle ifade edilir. (u, v) ile (v, u) aynı şeyi ifade
ederler.
z Örnek: uçuş rotası
z Yönlendirilmiş graf
z Bütün kenarları yönlendirilmiş graftır.
z Yönlendirilmemiş graf
z Hiçbir kenarı yönlendirilmemiş graftır.

G. Ü. Bilgisayar Mühendisliği Bölümü

Graflar (Terminoloji)
Komşu (Adjacent)

z Eğer (u, v) ∈ E ise u ve v node’ları komşudur.

v k
(u, v)
u w
u ve v komşudur
v ve w komşu değildir

G. Ü. Bilgisayar Mühendisliği Bölümü

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 v3
v1

- v2, v3, v4, v2, v1 bir yoldur. v4 v5

- v2, v3, v4, v5 bir basit yoldur.

G. Ü. Bilgisayar Mühendisliği Bölümü

Graflar (Terminoloji - devam)

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 v3

- v2, v3, v4, v5 , v3, v2 bir cycle’dır v4 v5

- v2, v3, v4, v2 bir basit cycle’dır

G. Ü. Bilgisayar Mühendisliği Bölümü

4
Graflar (Terminoloji - devam)
Bağlı ve bağlı olmayan graf

z Eğer bir graftaki tüm node’lar arasında en azından bir yol varsa
bağlı graftır.
z Eğer bir grafta herhangi iki node arasında yol bulunmuyorsa
bağlı olmayan graftır.

v2
v1 v3

v4 v5
bağlı graf

G. Ü. Bilgisayar Mühendisliği Bölümü

Graflar (Terminoloji - devam)

Bağlı ve bağlı olmayan graf (devam)

v1 v3 v7 v8
v2
v4 v5
v6 v9

bağlı olmayan graf

G. Ü. Bilgisayar Mühendisliği Bölümü

5
Graflar (Terminoloji - devam)
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 v7 v8
v1 v3

v4 v5
v6 v9

G. Ü. Bilgisayar Mühendisliği Bölümü

Graflar (Terminoloji - devam)

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

G. Ü. Bilgisayar Mühendisliği Bölümü

6
Graflar (Terminoloji - devam)
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 v2
v1 v3 v3

v4 v5 v4 v5

G H

G. Ü. Bilgisayar Mühendisliği Bölümü

Graflar (Terminoloji - devam)

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 2000 Ankara

1000
3500

İzmir
G
G. Ü. Bilgisayar Mühendisliği Bölümü

7
Graflar (Terminoloji - devam)
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.

Self edge Multiple edge

G. Ü. Bilgisayar Mühendisliği Bölümü

Graflar (Terminoloji - devam)

z a,b ve d kenarları V node’unun kenar bağlantılarıdır.

z X node’unun derecesi 5’ tir.
z h ve i çoklu (multiple) kenarlardır.
z j kendi kendisine döngüdür (self loop).

V
a b
h j
U d X Z
c e i
W g
f
Y
G. Ü. Bilgisayar Mühendisliği Bölümü

8
Graflar (Terminoloji - devam)
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 1000 Ankara

Directed edge
2000 3500

İzmir
G
G. Ü. Bilgisayar Mühendisliği Bölümü

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.

G. Ü. Bilgisayar Mühendisliği Bölümü

9
 Graflar (Oluşturulması-Komşu Matrisi)
z Yönlendirilmiş graf için komşu matrisi
Matris[i][j] = 1 if (vi, vj)∈E
0 if (vi, vj)∉E 1 2 3 4 5
v1 v2 v3 v4 v5
v2 1 v1 0 1 0 0 0
v1 v3
2 v2 0 0 0 1 0
3 v3 0 1 0 1 0
v4 v5
4 v4 0 0 0 0 0
G 5 v5 0 0 1 1 0

G. Ü. Bilgisayar Mühendisliği Bölümü

Graflar (Oluşturulması-Komşu Matrisi)

z Ağırlıklandırılmış ancak yönlendirilmemiş graf için
komşu matrisi
Matris[i][j] = w(vi, vj) if (vi, vj)∈E or (vj, vi)∈E
∞ otherwise
1 2 3 4 5
v2 v1 v2 v3 v4 v5
v1 2 v3
5 1 v1 ∞ 5 ∞ ∞ ∞
4 3
7 2 v2 5 ∞ 2 4 ∞
v4
8 v5 3 v3 ∞ 2 ∞ 3 7
4 v4 ∞ 4 3 ∞ 8
G
5 v5 ∞ ∞ 7 8 ∞
G. Ü. Bilgisayar Mühendisliği Bölümü

10
Graflar (Oluşturulması-Komşu Matrisi)
Örnek

1 2 1

3 2 3
4
1 2 3 1 2 3 4
1 0 0 1 1 0 1 1 0
2 0 1 0 2 1 0 0 0
3 1 1 0 3 1 0 0 0
4 0 0 0 0
G. Ü. Bilgisayar Mühendisliği Bölümü

Graflar (Oluşturulması-Komşu Listesi)

z Yönlendirilmiş graf için komşu listesi

1 v1 → v2
v2 2 v2 → v4
v1 v3
3 v3 → v2 → v4
4 v4
v4 v5
5 v5 → v3 → v4
G

G. Ü. Bilgisayar Mühendisliği Bölümü

11
 Graflar (Oluşturulması-Komşu Listesi)
z Yönlendirilmiş ve ağırlıklandırılmış graf için komşu
listesi
v2
v1 2 v3
5
4 3 7
v4
8 v5
1 v1 → v2(5)
G 2 v2 → v1(5) → v3(2) → v4(4)
3 v3 → v2(2) → v4(3) → v5(7)
4 v4 → v2(4) → v3(3) → v5(8)
5 v5 → v3(7) → v4(8)
G. Ü. Bilgisayar Mühendisliği Bölümü

Graflar (Oluşturulması-Komşu Listesi)

Örnek

1 2 1

3 2 3
4

1 Æ 2 Æ3
1 Æ 3
2 Æ 1
2 Æ 2
3 Æ 1
3 Æ 1Æ2
4 Æ
G. Ü. Bilgisayar Mühendisliği Bölümü

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.

G. Ü. Bilgisayar Mühendisliği Bölümü

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.

G. Ü. Bilgisayar Mühendisliği Bölümü

13
 Graflar (Dolaşma - Traversal)
z Depth first arama işlem adımları
1. Önce bir başlangıç node’u seçilir ve ziyaret edilir.
2. Seçilen node’un bir komşusu seçilir ve ziyaret edilir.
3. [Link]ı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.

G. Ü. Bilgisayar Mühendisliği Bölümü

Graflar (Dolaşma - Traversal)

z Depth first arama
1. s node’unu seç
0 1
2. visit s
// örn. ekrana yaz
4
2 3. for each edge <s, U>
3
// U komşu node
5 4. if U is not visit
5. DFS(G, U)
7 6

9
8

G. Ü. Bilgisayar Mühendisliği Bölümü

14
 Graflar (Dolaşma - Traversal)
z Depth first arama 0

3
0 1

4
2
3

7 6

9
8

G. Ü. Bilgisayar Mühendisliği Bölümü

Graflar (Dolaşma - Traversal)

z Depth first arama 0

3
0 1
7

4
2
3

7 6

9
8

G. Ü. Bilgisayar Mühendisliği Bölümü

15
 Graflar (Dolaşma - Traversal)
z Depth first arama 0

3
0 1
7

4 8
2
3

7 6

9
8

G. Ü. Bilgisayar Mühendisliği Bölümü

Graflar (Dolaşma - Traversal)

z Depth first arama 0

3
0 1
7

4 8
2
3 9

7 6

9
8

G. Ü. Bilgisayar Mühendisliği Bölümü

16
 Graflar (Dolaşma - Traversal)
z Depth first arama 0

3
0 1
7

4 8
2
3 9

5 6

7 6

9
8

G. Ü. Bilgisayar Mühendisliği Bölümü

Graflar (Dolaşma - Traversal)

z Depth first arama 0

3
0 1
7

4 8
2
3 9

5 6

2
7 6

9
8

G. Ü. Bilgisayar Mühendisliği Bölümü

17
 Graflar (Dolaşma - Traversal)
z Depth first arama 0

3
0 1
7

4 8
2
3 9

5 6

2
7 6
5

9
8

G. Ü. Bilgisayar Mühendisliği Bölümü

Graflar (Dolaşma - Traversal)

z Depth first arama 0

3
0 1
7

4 8
2
3 9

5 6

2
7 6
5

9
8

G. Ü. Bilgisayar Mühendisliği Bölümü

18
 Graflar (Dolaşma - Traversal)
z Depth first arama 0

3
0 1
7

4 8
2
3 9

5 6

2
7 6
5 4

9
8

G. Ü. Bilgisayar Mühendisliği Bölümü

Graflar (Dolaşma - Traversal)

z Depth first arama 0

3
0 1
7

4 8
2
3 9

5 6
2
7 6
5 4

9 1
8

G. Ü. Bilgisayar Mühendisliği Bölümü

19
 Graflar (Dolaşma - Traversal)
z Depth first arama 0

3
0 1
7

4 8
2
3 9

5 6
2
7 6
5 4

9 1
8

G. Ü. Bilgisayar Mühendisliği Bölümü

Graflar (Dolaşma - Traversal)

z Depth first arama 0

3
0 1
7

4 8
2
3 9

5 6
2
7 6
5 4

9 1
8

G. Ü. Bilgisayar Mühendisliği Bölümü

20
 Graflar (Dolaşma - Traversal)
z Depth first arama 0

3
0 1
7

4 8
2
3 9

5 6
2
7 6
5 4

9 1
8

G. Ü. Bilgisayar Mühendisliği Bölümü

Graflar (Dolaşma - Traversal)

z Depth first arama 0

3
0 1
7

4 8
2
3 9

5 6
2
7 6
5 4

9 1
8

G. Ü. Bilgisayar Mühendisliği Bölümü

21
 Graflar (Dolaşma - Traversal)
z Depth first arama 0

3
0 1
7

4 8
2
3 9

5 6
2
7 6
5 4

9 1
8

G. Ü. Bilgisayar Mühendisliği Bölümü

Graflar (Dolaşma - Traversal)

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
[Link]ıma gidilir.

G. Ü. Bilgisayar Mühendisliği Bölümü

22
Graflar (Dolaşma - Traversal)
z Breadth first arama
0
0 1

4
2
3

7 6

9
8

G. Ü. Bilgisayar Mühendisliği Bölümü

Graflar (Dolaşma - Traversal)

z Breadth first arama
0
0 1
3 2 1

4
2
3

7 6

9
8

123

G. Ü. Bilgisayar Mühendisliği Bölümü

23
Graflar (Dolaşma - Traversal)
z Breadth first arama
0
0 1
3 2 1

4
2 7 8 6
3

7 6

9
8

68712

G. Ü. Bilgisayar Mühendisliği Bölümü

Graflar (Dolaşma - Traversal)

z Breadth first arama
0
0 1
3 2 1

4
2 7 8 6 4 5
3

7 6

9
8

456871

G. Ü. Bilgisayar Mühendisliği Bölümü

24
Graflar (Dolaşma - Traversal)
z Breadth first arama
0
0 1
3 2 1

4
2 7 8 6 4 5
3

7 6

9
8

45687

G. Ü. Bilgisayar Mühendisliği Bölümü

Graflar (Dolaşma - Traversal)

z Breadth first arama
0
0 1
3 2 1

4
2 7 8 6 4 5
3

7 6

9
8

4568

G. Ü. Bilgisayar Mühendisliği Bölümü

25
Graflar (Dolaşma - Traversal)
z Breadth first arama
0
0 1
3 2 1

4
2 7 8 6 4 5
3
9
5

7 6

9
8

9456

G. Ü. Bilgisayar Mühendisliği Bölümü

Graflar (Dolaşma - Traversal)

z Breadth first arama
0
0 1
3 2 1

4
2 7 8 6 4 5
3
9
5

7 6

9
8

9456

G. Ü. Bilgisayar Mühendisliği Bölümü

26
Graflar (Dolaşma - Traversal)
z Breadth first arama
0
0 1
3 2 1

4
2 7 8 6 4 5
3
9
5

7 6

9
8

945

G. Ü. Bilgisayar Mühendisliği Bölümü

Graflar (Dolaşma - Traversal)

z Breadth first arama
0
0 1
3 2 1

4
2 7 8 6 4 5
3
9
5

7 6

9
8

94

G. Ü. Bilgisayar Mühendisliği Bölümü

27
Graflar (Dolaşma - Traversal)
z Breadth first arama
0
0 1
3 2 1

4
2 7 8 6 4 5
3
9
5

7 6

9
8

G. Ü. Bilgisayar Mühendisliği Bölümü

Graflar (Dolaşma - Traversal)

z Breadth first arama
0
0 1
3 2 1

4
2 7 8 6 4 5
3
9
5

7 6

9
8

G. Ü. Bilgisayar Mühendisliği Bölümü

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 d
a

c e

z Örnekteki grafta topolojik sıralama aşağıdaki gibi

yapılabilir.

1- a, c, b, e, d
a b c e d
2- c, a, b, e, d

G. Ü. Bilgisayar Mühendisliği Bölümü

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ı
olarak kullanılacaktır. 200
10 1
95
90
z Herhangi bir şehirden 200 80
4
başlayarak tüm şehirleri 2
3 75
dolaşmak için gerekli olan
160
algoritmayı depth first 220
110
5
dolaşmayla yapınız.
7 230 6
100
50 125
9
8

G. Ü. Bilgisayar Mühendisliği Bölümü

29