Programlama Ve Algoritmalar Dersi 8. Ünite Sorularla Öğrenelim

Çizge Algoritmaları

Giriş

1- Çizge nasıl bir veri yapısıdır?

Cevap: Çizge, düğümlerle bu düğümleri birbirine bağlayan kenarlardan oluşan ve ağ görünümünde olan bir tür veri yapısıdır.

2- Çizgeler temel olarak hangi amaç doğrultusunda kullanılmaktadır?

Cevap: Çizgeler, temel olarak birbirleriyle ilişkili verileri temsil etmek için kullanılırlar.

3- Çizgelerin içerdiği düğümlerin özel arama algoritmaları ile bir noktadan başlanarak belirli sırada ziyaret edilebilmesini ve listelenebilmesini sağlayan hangi tür algoritmalar mevcuttur?

Cevap: Çizgelerin içerdiği düğümlerin özel arama algoritmaları ile bir noktadan başlanarak belirli sırada ziyaret edilebilmesini ve listelenebilmesini sağlayan temel olarak enine arama ve önce derinliğine arama algoritmaları mevcuttur.

4- Çizgeler arasındaki en kısa yolu hesaplamak için kullanılan algoritma türü hangisidir?

Cevap: En kısa yol bulma algoritmalarıdır.

Çizgelerle İlgili Temel Kavramlar

5- Yönlü çizge nedir?

Cevap: Yönlü çizge, kenar bağlantılarının yönleri temsil eden oklarla gösterildiği çizgedir.

6- Yönsüz çizge nedir?

Cevap: Yönsüz çizge, kenar bağlantılarının yönleri temsil eden oklar ile gösterilmediği çift yönlü olan çizgedir.

7- İki düğüm arasında bir bağlantı olması hangi kavram ile ifade edilir?

Cevap: Komşuluk kavramı ile ifade edilir.

8- Bir çizgenin tüm düğümleri birbirine komşu ise o çizgi hangi kavram ile ifade edilir?

Cevap: Bir çizgenin tüm düğümleri birbirine komşu ise o çizge, tam çizge olarak ifade edilir.

9- Çakışım nedir?

Cevap: Çakışım, düğüm ile kenar bağlantısı arasındaki ilişkiyi belirtir.

10- Çizgeler için basit yol kavramı neyi ifade etmektedir?

Cevap: Yol (path), çizgenin içerisinde bir düğümden başka bir düğüme ulaşmak için geçilmesi gereken düğümlerdir. Bir yolda tekrar edilen düğümler yoksa bu yola, basit yol (simple path) denilir.

11- Komşuluk matrisi hangi amaçlarla kullanılmaktadır?

Cevap: Çizgeler hakkındaki bir diğer önemli husus ise düğümlerin komşuluk ilişkilerinin temsil edilme şeklidir. Bu amaçla kullanılabilecek en çok bilinen yöntemlerden birisi komşuluk matrisi yöntemidir. Komşuluk matrisi, aynı zamanda çizge algoritmalarının programlama yoluyla bilgisayar ortamında ifade edilmesi amacıyla da kullanılmaktadır.

12- Düğümler arasındaki kenar bağlantıları üzerinde sıfırdan farklı sayısal değerlerin yer aldığı çizge türü hangisidir?

Cevap: Düğümler arasındaki kenar bağlantıları üzerinde sıfırdan farklı sayısal değerlerin yer aldığı çizge türü, ağırlıklandırılmış çizgedir.

Enine Arama Algoritması

13- Enine arama algoritması, ne tür bir algoritmadır?

Cevap: Enine arama, çizgenin bir düğümünden başlanarak, söz konusu düğümün komşu düğümlerinin ve onların da komşularının sırayla ziyaret edildiği arama algoritmasıdır.

14- Enine arama algoritması, uygulanması esnasında hangi veri yapısından faydalanır?

Cevap: Enine arama algoritması, uygulanması esnasında kuyruk veri yapısından faydalanır.

Önce Derinliğine Arama Algoritması

15- Önce derinliğine arama algoritması ne tür bir arama algoritmasıdır?

Cevap: Önce derinliğine arama, çizgenin bir düğümünden başlanarak bu düğümün komşusu üzerinden gidilebilecek en uzak düğüme kadar olan noktaların ziyaret edildiği ve daha sonra geri dönülerek aynı işlemlerin ziyaret edilmemiş düğümler için sürdürüldüğü bir arama algoritmasıdır.

16- Önce derinliğine arama algoritmasının uygulanması esnasında hangi veri yapısından faydalanılır?

Cevap: Önce derinliğine arama algoritmasının uygulanması esnasında yığın veri yapısından faydalanılır.

Dijkstra En Kısa Yol Algoritması

17- Dijkstra algoritması hangi amaçla kullanılmaktadır?

Cevap: Dijkstra algoritması, ağırlıklandırılmış çizgelerde bir başlangıç düğümü ile diğer düğümler arasındaki en kısa mesafeyi tespit etmek için kullanılır.

18- Dijkstra algoritmasının amacını açıklamak için örnek olarak Türkiye haritasındaki şehirlerin bir çizge üzerinde düğümler olarak gösterildiğini varsayarsak, düğümler arasındaki ağırlıklandırılmış kenar bağlantıları neyi temsil edecektir?

Cevap: Her iki şehir çifti arasındaki uzaklığı temsil edecektir.

19- Dijkstra algoritmasının başlangıcında, başlangıç düğümü ile diğer düğümler arasındaki uzaklıkların tamamı hakkında nasıl bir varsayımda bulunulur?

Cevap: Dijkstra algoritmasının başlangıcında, başlangıç düğümü ile diğer düğümler arasındaki uzaklıkların tamamının sonsuz olduğu varsayılır.

20- Dijkstra algoritmasında, varsayılan sonsuz değer ile algoritma ile elde edilen yol uzunluğu hangi durumda değiştirilir?

Cevap: Algoritma, düğümler arasındaki en kısa yolları aradığı için düğümler arasında daha kısa yollar bulundukça, sonsuz değeri ilgili yolun uzunluğu ile değiştirilir.

Sıra-(Soruid) 1-(975938) 2-(975940) 3-(975943) 4-(975945) 5-(975946) 6-(975947) 7-(975952) 8-(975954) 9-(975955) 10-(975958) 11-(975960) 12-(975964) 13-(975967) 14-(975968) 15-(975972) 16-(975973) 17-(975975) 18-(975979) 19-(975985) 20-(975989)