| Sıra | DOSYA ADI | Format | Bağlantı |
|---|---|---|---|
| 01. | Çizge Gösterimleri | ppt | Sunumu İndir |
Transkript
1 Çizge gösterimleri • G = (V, E) çizgesinin komşuluk listesi gösterimi V sayıda listenin bir dizisi(array), V deki her köşe için bir tane liste – Her Adj[u] listesi u köşesinin bağlı olduğu tüm v köşelerini içerir (rastgele sıralı olarak) – Yönlü veya yönsüz çizgeler için kullanılabilir 1 2 5 4 3 2 5 / 1 5 3 4 / 1 2 3 4 5 2 4 2 5 3 / 4 1 2 Yönsüz çizge
2 Komşuluk listesi gösteriminin özellikleri • Tüm komşuluk listelerinin toplamı – Yönlü çizgelerde: • Her (u, v) kirişi listede sadece bir defa olacağından sayısına – Yönsüz çizgelerde: Her uv kirişi listede 2 defa olacağından sayısna eşittir 1 2 5 4 3 Undirected graph 1 2 3 4 Directed graph E 2 E
3 Komşuluk listesi gösteriminin özellikleri • Hafiza gereksinimi (V + E) • Tercih edildiği çizgeler – Seyrek çizgelerde: E << V 2 • Eksik yönü – u ile v arasında kiriş olup olmadığını hızlı kontrol etmenin bir yolu yoktur • u ya komşu tüm köşelerin listesini bulmak için gerekli süre: (degree(u)) • (u, v) E için kontrol süresi: – O(degree(u)) 1 2 5 4 3 Undirected graph 1 2 3 4 Directed graph
4 Çizge gösterimi • G = (V, E) çizgesinin komşuluk matrisi gösterimi – Köşelerin numaraları 1, 2, … V olsun. – Komşuluk matrisi A V x V nın terimleri aij = 1 eğer (i, j) E 0 aksi durumda 1 2 5 4 3 Yönsüz çizge 1 2 3 4 5 1 2 3 4 5 0 1 10 0 1 1 1 10 1 10 0 0 1 1 10 0 1 1 10 0 A matrisi simetriktir: aij = aji A = AT
5 Komşuluk matrisi gösteriminin özellikleri • Hafiza gereksinimi (V2), G nin kiriş sayısına bağlı değil • Ne zaman tercih edilir – Çizge yoğunsa, yani E sayısı V 2 sayısına çok yakınsa – 2 köşe arasında kiriş olup olmadığını hızlı bulma gereksinimi varsa • u ya komşu tüm köşelerin bulunması süresi: (V) • (u, v) E kontrol süresi: (1)
6 Ağırlıklı çizgeler • Ağırlıklı çizgeler = Her kiriş için atanmış w(u, v) ağırlığı vardır w: E R, ağırlık fonksiyonu • Ağırlıkların hafızada tutulması – Komşuluk listesinde: • w(u,v) sayısı u nun komşuluk listesinde v köşesi ile birlikte tutulur – Komşuluk matrisinde: • w(u, v) saysı matrisin (u, v) ye karşılık gelen yerinde tutulur
7 Çizgelerde arama • Çizgelerde arama = Çizgenin kirişlerini sistemli bir biçimde takip ederek mümkün olan tüm köşelerinde bulunmak • İki temel arama algoritması vardır: – Genişlik öncelikli arama (Breadth-first search) – Derinlik öncelikli arama (Depth-first search) – Bu iki algoritma arasındaki en önemi fark çizgenin üzerinden geçilmemiş kirişlerini hangi sıra ile takip edilmesindedir
8 Breadth-First Search (BFS) • Giriş: – Bir G = (V, E) çizgesi(yönlü veya yönsüz) – Bir s V kaynak köşesi • Amaç: – s köşesinden ulaşılabilir tüm köşelerde öncelikle s e daha yakın olan köşelere kirişlerle gitme koşuluyla bulunmak • Çıkış: – d[v] = s den v ye olan uzaklık (en kısa yoldaki kiriş sayısı), tüm v V ler için – Kökü s de olan BFS ağacı
9 Breadth-First Search (devam.) • Köşeleri s den olan uzaklığın artan sırası ile keşfet-genişlemesine ara, derinlemesine değil – Önce s den 1 kiriş uzakta olan köşeler, sonra 2 kiriş uzakta olan köşeler,… bulunur 1 2 5 4 3 7 7 9 11 12 6
10 Breadth-First Search (devam.) – Her köşe beyaz, gri veya siyah renkte olur – Başlangıçta, tüm köşeler beyaz olur – Keşfedilen köşenin rengi hemen griye dönüşür – Tüm komşuları keşfedilen köşenin rengi sıayaha dönüşür – FIFO ile çalışan Q kuyruğu gri köşeleri içerir 1 2 5 4 3 1 2 5 4 3 kaynak 1 2 5 4 3
11 BFS ağacı • BFS algoritması BFS ağacı üretir – Başlangıçta sadece kökü vardır(kaynak köşe s) – v köşesi u köşesinin komşusu olarak keşfedildiyse (u, v) kirişi ağaca eklenir – u köşesi v nin velisi olur – Her köşe sadece 1 defa keşfedilebilir yani her köşenin sadece 1 velisi vardır 1 2 5 4 3 Kaynak
12 BFS için Veri yapıları • G = (V, E) çizgesi komşuluk listesi ile ifade edilir • color[u] – u V nin rengi [u] – u nun velisi – Eğer u = s (kök) veya u köşesi henüz keşfedilmemişse [u] = NIL • d[u] – s den u ya olan uzaklık • FIFO mantıklı Q kuyruğu (gri köşeleri içerir) 1 2 5 4 3 d=1 =1 d=1 =1 d=2 =5 d=2 =2 kaynak
13 BFS(G, s) 1. for each u V[G] - {s} 2. do color[u] WHITE 3. d[u] ← 4. [u] = NIL 5. color[s] GRAY 6. d[s] ← 0 7. [s] = NIL 8. Q 9. Q ← ENQUEUE(Q, s) Q: s 0 r s t u v w x y r s t u v w x y r s t u v w x y
14 BFS(V, E, s) 10. while Q 11. do u ← DEQUEUE(Q) 12. for each v Adj[u] 13. do if color[v] = WHITE 14. then color[v] ← GRAY 15. d[v] ← d[u] + 1 16. [v] = u 17. ENQUEUE(Q, v) 18. color[u] BLACK 0 1 r s t u v w x y Q: w Q: s 0 r s t u v w x y 1 0 1 r s t u v w x y Q: w, r
COSC3101A 15 Örnek 1 0 1 r s t u v w x y Q: s 0 r s t u v w x y Q: w, r v w x y 1 0 2 1 2 r s t u Q: r, t, x 1 0 2 2 1 2 r s t u v w x y Q: t, x, v 1 0 2 3 2 1 2 r s t u v w x y Q: x, v, u 1 0 2 3 2 1 2 3 r s t u v w x y Q: v, u, y 1 0 2 3 2 1 2 3 r s t u v w x y Q: u, y 1 0 2 3 2 1 2 3 r s t u v w x y Q: y r s t u 1 0 2 3 2 1 2 3 v w x y Q:
16 BFS analizi 1. for each u V - {s} 2. do color[u] WHITE 3. d[u] ← 4. [u] = NIL 5. color[s] GRAY 6. d[s] ← 0 7. [s] = NIL 8. Q 9. Q ← ENQUEUE(Q, s) O(V) (1)
17 BFS analizi 10. while Q 11. do u ← DEQUEUE(Q) 12. for each v Adj[u] 13. do if color[v] = WHITE 14. then color[v] = GRAY 15. d[v] ← d[u] + 1 16. [v] = u 17. ENQUEUE(Q, v) 18. color[u] BLACK (1) (1) Scan Adj[u] for all vertices in the graph • Each vertex is scanned only once, when the vertex is dequeued • Sum of lengths of all adjacency lists = (E) • Scanning operations: O(E) • Total running time for BFS = O(V + E)
18 En kısa yol özelliği • BFS algoritması s V köşesinden ulaşılabilir tüm köşeler en kısa yolları buluyor • En kısa yol uzunluğu (s, u) – s den u ya minimum kiriş sayısıdır r s t u 1 0 2 3 2 1 2 3 v w x y kaynak
19 Derinlik öncelikli arama (DFS) • Giriş: – G = (V, E) (Kaynak köşe verilmez!) • Amaç: – G nin herhangi bir köşesinden başlayarak ve kirişleri üzerinde hareket ederek tüm köşelerini keşfetmek • Çıkış: – 2 zaman değişkeni: • d[v] = v nin keşfedildiği zaman • f[v] = v nin tüm komşularının ziyareti bittiği zaman – DFS ormanı 1 2 5 4 3
20 DFS Veri yapıları • Global değişken: time-step( zaman-adım) – Köşeler keşfedildikçe ve keşfi bittiğinde birer artırılır • color[u] – BFS dekinin aynısı [u] – u nun velisi • d[u], f[u] – keşfedildiği zaman ve keşfin bittiği zaman GriBeyaz Siyah 0 2Vd[u] f[u] 1 ≤ d[u] < f [u] ≤ 2 |V|
21 DFS(G) 1. for each u V[G] 2. do color[u] ← WHITE 3. [u] ← NIL 4. time ← 0 5. for each u V[G] 6. do if color[u] = WHITE 7. then DFS-VISIT(u) • Every time DFS-VISIT(u) is called, u becomes the root of a new tree in the depth-first forest u v w x y z
22 DFS-VISIT(u) 1. color[u] ← GRAY 2. time ← time+1 3. d[u] ← time 4. for each v Adj[u] 5. do if color[v] = WHITE 6. then [v] ← u 7. DFS-VISIT(v) 8. color[u] ← BLACK 9. time ← time + 1 10.f[u] ← time 1/ u v w x y z u v w x y z time = 1 1/ 2/ u v w x y z
23 Örnek 1/ 2/ u v w x y z 1/ u v w x y z 1/ 2/ 3/ u v w x y z 1/ 2/ 4/ 3/ u v w x y z 1/ 2/ 4/ 3/ u v w x y z B 1/ 2/ 4/5 3/ u v w x y z B 1/ 2/ 4/5 3/6 u v w x y z B 1/ 2/7 4/5 3/6 u v w x y z B 1/ 2/7 4/5 3/6 u v w x y z BF
24 Örnek (devam) 1/8 2/7 4/5 3/6 u v w x y z BF 1/8 2/7 9/ 4/5 3/6 u v w x y z BF 1/8 2/7 9/ 4/5 3/6 u v w x y z BF C 1/8 2/7 9/ 4/5 3/6 10/ u v w x y z BF C 1/8 2/7 9/ 4/5 3/6 10/ u v w x y z BF C B 1/8 2/7 9/ 4/5 3/6 10/11 u v w x y z BF C B 1/8 2/7 9/12 4/5 3/6 10/11 u v w x y z BF C B The results of DFS may depend on: • The order in which nodes are explored in procedure DFS • The order in which the neighbors of a vertex are visited in DFS-VISIT
25 Kiriş sınıflandırma • Ağaç kirişleri (beyaz köşeye giden kirişler): – (u, v) ağaç kirişidir eğer v köşesi ilk defa first (u, v) kirişi ile gelinerek ziyaret edilmişse • Geri kiriş (Back edge) (Gri köşeye giden kirişler): – (u, v) geri kiriştir eğer u köşesi v nin soyundan geliyorsa – Döngü kirişler de geri kirişlerdir 1/ u v w x y z 1/ 2/ 4/ 3/ u v w x y z B
26 Kiriş sınıflandırma • İleri kirişler (Forward edges) (Siyah köşelere giden d[u] < d[v] olan kirişler): – (u, v) kirişi ağaç kirişi değilse ve v köşesi u nun soyundan geliyorsa bu kiriş ileri kiriştir • Çapraz kiriş (Cross edge) (Siyah köşelere giden d[u] > d[v] olan kirişler): – Ağaç, ileri, geri olmayan tüm kirişler 1/ 2/7 4/5 3/6 u v w x y z BF 1/8 2/7 9/ 4/5 3/6 u v w x y z BF C
27 DFS(G) analizi 1. for each u V[G] 2. do color[u] ← WHITE 3. [u] ← NIL 4. time ← 0 5. for each u V[G] 6. do if color[u] = WHITE 7. then DFS-VISIT(u) (V) (V) – exclusive of time for DFS-VISIT
28 DFS-VISIT(u) analizi 1. color[u] ← GRAY 2. time ← time+1 3. d[u] ← time 4. for each v Adj[u] 5. do if color[v] = WHITE 6. then [v] ← u 7. DFS-VISIT(v) 8. color[u] ← BLACK 9. time ← time + 1 10.f[u] ← time Each loop takes |Adj[v]| DFS-VISIT is called exactly once for each vertex Total: Σv V |Adj[v]| + (V) = (E) (V + E)
29 Topological Sort Topological sort of a directed acyclic graph G = (V, E): a linear order of vertices such that if there exists an edge (u, v), then u appears before v in the ordering. • Directed acyclic graphs (DAGs) – Used to represent precedence of events or processes that have a partial order a before b b before c b before c a before c a before c What about a and b? Topological sort helps us establish a total order
30 Topological Sort undershorts pants belt socks shoes watch shirt tie jacket TOPOLOGICAL-SORT(V, E) 1. Call DFS(V, E) to compute finishing times f[v] for each vertex v 2. When each vertex is finished, insert it onto the front of a linked list 3. Return the linked list of vertices 1/ 2/ 3/4 5 6/7 8 9/10 11/ 12/ 13/14 15 16 17/18 jackettiebeltshirtwatchshoespantsundershortssocks Running time: (V + E)
31 Topological Sort undershorts pants belt socks shoes watch shirt tie jacket 1/ 2/ 3/4 5 6/7 8 9/10 11/ 12/ 13/14 15 16 17/18 jackettiebeltshirtwatchshoespantsundershortssocks Topological sort: an ordering of vertices along a horizontal line so that all directed edges go from left to right.
32 Strongly Connected Components Given directed graph G = (V, E): A strongly connected component (SCC) of G is a maximal set of vertices C V such that for every pair of vertices u, v C, we have both u v and v u.
33 The Transpose of a Graph • GT = transpose of G – GT is G with all edges reversed – GT = (V, ET), ET = {(u, v) : (v, u) E} • If using adjacency lists: we can create GT in (V + E) time 1 2 5 4 3 1 2 5 4 3
34 Finding the SCC • Observation: G and GT have the same SCC’s – u and v are reachable from each other in G they are reachable from each other in GT • Idea for computing the SCC of a DAG G = (V, E): – Make two depth first searches: one on G and one on GT 1 2 5 4 3 1 2 5 4 3
35 Example a b c d e f g h 1/ 2/3/4 65/7 8/11/ 12/ 13/ 91014 15 16 f 4 h 6 g 7 d 9 c 10 a 14 e 15 b 16 DFS on the initial graph G DFS on GT: • start at b: visit a, e • start at c: visit d • start at g: visit f • start at h Strongly connected components: C1 = {a, b, e}, C2 = {c, d}, C3 = {f, g}, C4 = {h} a b c d e f g h
36 Component Graph • The component graph GSCC = (VSCC, ESCC): – VSCC = {v1, v2, …, vk}, where vi corresponds to each strongly connected component Ci – There is an edge (vi, vj) ESCC if G contains a directed edge (x, y) for some x Ci and y Cj • The component graph is a DAG a b c d e f g h a b e c d f g h
37 Notations • Extend notation for d (starting time) and f (finishing time) to sets of vertices U V: – d(U) = minu U { d[u] } (earliest discovery time) – f(U) = maxu U { f[u] } (latest finishing time) a b c d e f g h 1/ 2/3/4 65/7 8/11/ 12/ 13/ 91014 15 16 C1 C2 C3 C4 d(C1) f(C1) d(C2) f(C2) d(C3) f(C3) d(C4) f(C4) =11 =16 =1 =10 =2 =7 =5 =6
Çizge Gösterimleri
Yazar :
EMRAH ŞAHİN
Yıl : 2003
Anahtar Kelimeler
Daha fazla görüntüle