Graph representations and BFS

Çizge nedir?

A graph G = (V, E) consists of a set V of vertices and a set E of edges, where each edge is a pair of vertices. Examples:

G = (V, E) çizgesi, V tepeler kümesi ile E kenarlar kümesinden oluşur; her kenar bir tepe çiftidir. Örnekler:

Road networks: vertices are cities or junctions, edges are roads (the slide shows Stony Brook, Riverhead, Greenport, Montauk and other Long Island towns).

Yol ağları: tepeler şehirler veya kavşaklar, kenarlar yollardır (slaytta Stony Brook, Riverhead, Greenport, Montauk ve Long Island’daki diğer yerleşimler gösterilir).

Electronic circuits: junctions are vertices, components are edges.

Elektronik devreler: bağlantı noktaları tepe, devre elemanları kenardır.

Social networks, the World Wide Web (pages and links), control flow inside a program, and similarity graphs where an edge means two items are alike.

Sosyal ağlar, World Wide Web (sayfalar ve bağlantılar), program içindeki kontrol akışı ve bir kenarın iki nesnenin benzer olduğunu belirttiği benzerlik çizgeleri.

Throughout the course n is the number of vertices and m the number of edges.

Ders boyunca n tepe sayısını, m ise kenar sayısını gösterir.

Çizge türleri

Skiena: “learning to talk the talk is an important part of walking the walk.” The flavour decides which algorithms apply.

Skiena: “Bir işin dilini öğrenmek, o işi yapabilmenin önemli bir parçasıdır.” Hangi algoritmaların uygulanabileceğini çizgenin türü belirler.

Arkadaşlık çizgesi: Bir örnek üzerinden terimler

Let the vertices be people and join two people by an edge if they are friends. Asking natural questions about it introduces the standard terms:

Tepeler insanlar olsun; iki insan arkadaşsa aralarını bir kenarla birleştirin. Bu yapı hakkında doğal sorular sormak, standart terimleri tanıtır:

If I am your friend, are you mine? That is asking whether the graph is undirected. The “has heard of” graph is directed (famous people have not heard of Skiena); other relationships are necessarily symmetric.

Ben sizin arkadaşınızsam siz de benim arkadaşım mısınız? Bu, çizgenin yönsüz olup olmadığını sorar. “Adını duymuş olma” çizgesi yönlüdür (ünlü insanlar Skiena’nın adını duymamıştır); başka ilişkiler ise zorunlu olarak simetriktir.

Am I linked by a chain of friends to a celebrity? A path is a sequence of edges connecting two vertices. Since a short chain is more impressive than a long one, we care about the shortest path.

Bir arkadaş zinciriyle bir ünlüye bağlı mıyım? Yol, iki tepeyi bağlayan bir kenar dizisidir. Kısa bir zincir uzun olandan daha etkileyici olduğundan en kısa yolla ilgileniriz.

Is there a chain between any two people at all? A graph is connected if there is a path between every pair of vertices. A directed graph is strongly connected if there is a directed path both ways between every pair. “Six degrees of separation” presumes the world’s friendship graph is connected.

Herhangi iki insan arasında bir zincir var mı? Her tepe çifti arasında bir yol varsa çizge bağlıdır. Yönlü bir çizgede her çift arasında her iki yönde de yönlü bir yol varsa çizge güçlü bağlıdır. “Altı derecelik ayrılık” düşüncesi, dünyanın arkadaşlık çizgesinin bağlı olduğunu varsayar.

Who has the most friends? The degree of a vertex is the number of edges touching it.

En çok kimin arkadaşı var? Bir tepenin derecesi, ona değen kenarların sayısıdır.

What is the largest group of mutual friends? A clique is a set of vertices every pair of which is joined; the densest possible subgraph. In a friendship graph, big cliques are workplaces, schools, congregations.

Herkesin birbiriyle arkadaş olduğu en büyük grup hangisidir? Klik, her çifti birbirine bağlı bir tepeler kümesidir; mümkün olan en yoğun alt çizgedir. Arkadaşlık çizgesinde büyük klikler iş yerleri, okullar ve cemaatlerdir.

Çizgeyi saklama: Komşuluk matrisi

Use an n × n table M where M[i, j] = 1 if (i, j) is an edge and 0 otherwise. Checking whether an edge exists is one lookup. The cost is space: n² entries even when the graph has only a few edges. An undirected graph could store only half the matrix (it is symmetric), but a sparse graph still wastes almost all of it.

M[i, j], (i, j) bir kenarsa 1, değilse 0 olacak şekilde n × n boyutlu bir M tablosu kullanın. Bir kenarın varlığını denetlemek tek bir erişim gerektirir. Bedeli bellek alanıdır: çizgede yalnızca birkaç kenar olsa bile n² hücre. Yönsüz çizgede matrisin yalnızca yarısı saklanabilir (matris simetriktir), ancak seyrek bir çizgede bunun da neredeyse tamamı boşa gider.

Çizgeyi saklama: Komşuluk listeleri

Keep an array of n pointers; entry i points to a linked list of the vertices adjacent to i. The slide’s example has vertex 1 adjacent to 2 and 5; vertex 2 to 1, 5, 4, 3; vertex 3 to 2 and 4; vertex 4 to 5, 2, 3; vertex 5 to 1, 2, 4. Notice that every undirected edge appears twice, once in each endpoint’s list.

n işaretçiden oluşan bir dizi tutun; i. giriş, i’ye komşu tepelerin bağlı listesine işaret etsin. Slayttaki örnekte 1 tepesi 2 ve 5’e; 2 tepesi 1, 5, 4, 3’e; 3 tepesi 2 ve 4’e; 4 tepesi 5, 2, 3’e; 5 tepesi 1, 2, 4’e komşudur. Her yönsüz kenarın, uçlarının her birinin listesinde birer kez olmak üzere iki kez yer aldığına dikkat edin.

To test whether edge (i, j) exists, scan list i for j, which costs O(dᵢ), the degree of i. In a sparse graph dᵢ is much smaller than n. If deletions are needed, the two copies of an edge can be linked to each other by a pointer.

(i, j) kenarının varlığını sınamak için i listesini j’yi arayarak tarayın; bunun maliyeti i’nin derecesi olan O(dᵢ)’dir. Seyrek çizgede dᵢ, n’den çok küçüktür. Silme işlemleri gerekiyorsa bir kenarın iki kopyası bir işaretçiyle birbirine bağlanabilir.

Hangisini kullanmalı?

Both are useful, but adjacency lists win for most problems because most real graphs are sparse and most algorithms traverse rather than look up specific edges. The rest of the course assumes adjacency lists.

İkisi de yararlıdır; fakat gerçek çizgelerin çoğu seyrek ve algoritmaların çoğu belirli kenarları aramak yerine dolaşım yaptığı için komşuluk listeleri çoğu problemde üstündür. Dersin geri kalanında komşuluk listeleri varsayılır.

Derste kullanılan komşuluk listesi gerçeklemesi

Each edge is a small record and each vertex owns a list of them:

Her kenar küçük bir kayıttır ve her tepe bu kayıtların bir listesine sahiptir:

edgenode:
    y        (the other endpoint)
    weight   (edge weight, if any)
    next     (next edge in this vertex's list)

graph:
    edges[1..n]    (edges[i] = head of vertex i's list)
    degree[1..n]   (number of edges out of each vertex)
    nvertices, nedges
    directed       (true or false)

edgenode:
    y        (diğer uç tepe)
    weight   (varsa kenar ağırlığı)
    next     (bu tepenin listesindeki sonraki kenar)

graph:
    edges[1..n]    (edges[i] = i tepesinin listesinin başı)
    degree[1..n]   (her tepeden çıkan kenar sayısı)
    nvertices, nedges
    directed      (true veya false)

Reading a graph from a file: the first line gives n and m, then one edge per line. Each edge is inserted at the head of its list in O(1):

Dosyadan çizge okuma: İlk satır n ve m’yi verir; ardından her satırda bir kenar bulunur. Her kenar, kendi listesinin başına O(1) sürede eklenir:

insert_edge(g, x, y, directed):
    create an edgenode p with p.y = y, p.weight = 0
    p.next = g.edges[x]
    g.edges[x] = p              (insert at head of x's list)
    g.degree[x] = g.degree[x] + 1
    if not directed:
        insert_edge(g, y, x, true)   (add the reverse copy)
    else:
        g.nedges = g.nedges + 1

insert_edge(g, x, y, directed):
    p.y = y, p.weight = 0 olan bir edgenode p oluştur
    p.next = g.edges[x]
    g.edges[x] = p              (x listesinin başına ekle)
    g.degree[x] = g.degree[x] + 1
    if not directed:
        insert_edge(g, y, x, true)   (ters kopyayı ekle)
    else:
        g.nedges = g.nedges + 1

The recursive trick at the end adds the reverse edge for undirected graphs without counting the edge twice.

Sondaki özyineleme tekniği, yönsüz çizgelerde kenarı iki kez saymadan ters kenarı ekler.

Hazırlık: Çizge gösterimleri arasında dönüşüm

For an undirected graph with n vertices and m edges:

n tepeli ve m kenarlı yönsüz bir çizge için:

Adjacency matrix → adjacency lists. Scan every matrix entry; each 1 becomes a list insertion. O(n²), because the matrix has to be read whole.

Komşuluk matrisi → komşuluk listeleri. Matrisin bütün hücrelerini tarayın; her 1, listeye bir ekleme işlemine dönüşür. Matrisin tamamı okunmak zorunda olduğundan O(n²).

Adjacency lists → incidence matrix. (An incidence matrix has a row per vertex and a column per edge, with a 1 where the vertex is an endpoint of that edge.) Walk the lists, giving each edge a column number as it is met and marking its two endpoints. Creating the matrix costs O(nm) just to zero it out, which dominates.

Komşuluk listeleri → geliş matrisi. (Geliş matrisinde her tepe için bir satır, her kenar için bir sütun vardır; tepe kenarın uçlarından biriyse hücre 1’dir.) Listeleri dolaşın; karşılaştığınız her kenara bir sütun numarası verin ve iki ucunu işaretleyin. Matrisi oluştururken yalnızca sıfırlamak bile O(nm) maliyetlidir ve baskın terim budur.

Incidence matrix → adjacency lists. Each column has exactly two 1s; scan each column to find them and insert the edge. O(nm) for scanning the whole matrix.

Geliş matrisi → komşuluk listeleri. Her sütunda tam iki tane 1 vardır; bunları bulmak için her sütunu tarayın ve kenarı ekleyin. Matrisin tamamını taramak O(nm) sürer.

The theme: a representation costs at least its own size to read or write, so the matrix representations impose their size on every conversion.

Ana fikir: Bir gösterimi okumak veya yazmak en az kendi boyutu kadar maliyetlidir; bu nedenle matris gösterimleri her dönüşüme kendi boyutlarının maliyetini yükler.

Dolaşım: Genel fikir

One of the most basic graph problems is to visit every vertex and edge. Two requirements: for efficiency, visit each edge at most twice (once from each endpoint); for correctness, be systematic enough not to miss anything. A maze is a graph, so a traversal algorithm has to be at least strong enough to get you out of any maze.

En temel çizge problemlerinden biri, her tepe ve kenarı ziyaret etmektir. İki gereklilik vardır: verimlilik için her kenarı en fazla iki kez (her ucundan bir kez) ziyaret etmek; doğruluk için hiçbir şeyi atlamayacak kadar sistematik olmak. Labirent bir çizgedir; dolayısıyla dolaşım algoritması sizi herhangi bir labirentten çıkarabilecek kadar güçlü olmalıdır.

The key idea is to mark vertices as they are found. Every vertex is always in one of three states, and only ever moves forward through them:

Temel fikir, tepeleri bulundukça işaretlemektir. Her tepe her zaman üç durumdan birindedir ve bu durumlar arasında yalnızca ileri yönde hareket eder:

Undiscovered: never seen.

Keşfedilmemiş: Hiç görülmemiş.

Discovered: seen, but not all of its edges have been examined yet.

Keşfedilmiş: Görülmüş, fakat bütün kenarları henüz incelenmemiş.

Processed: all of its edges have been examined.

İşlenmiş: Bütün kenarları incelenmiş.

We keep a “to-do list” of vertices that are discovered but not yet processed. At the start only the start vertex is discovered. To process a vertex, look at each edge leaving it; whenever an edge leads to an undiscovered vertex, mark that vertex discovered and add it to the to-do list.

Keşfedilmiş ama henüz işlenmemiş tepelerin bir “yapılacaklar listesini” tutarız. Başlangıçta yalnızca başlangıç tepesi keşfedilmiştir. Bir tepeyi işlemek için ondan çıkan her kenara bakın; bir kenar keşfedilmemiş tepeye ulaştığında o tepeyi keşfedilmiş olarak işaretleyin ve yapılacaklar listesine ekleyin.

Whatever order we take vertices from the to-do list, each edge is looked at exactly twice, once from each endpoint. That order is the only difference between BFS and DFS: BFS keeps the to-do list as a queue (first found, first processed); DFS keeps it as a stack.

Tepeleri yapılacaklar listesinden hangi sırayla alırsak alalım, her kenara her ucundan birer kez olmak üzere tam iki kez bakılır. BFS ve DFS arasındaki tek fark bu sıradır: BFS yapılacaklar listesini kuyruk olarak (ilk bulunan, ilk işlenen), DFS ise yığın olarak tutar.

Correctness. Every vertex and edge in the start vertex’s connected component is eventually visited. Suppose some vertex u were never visited but had a neighbour v that was. Then v was at some point processed, its edges were examined, and the edge to u would have discovered u. Contradiction.

Doğruluk. Başlangıç tepesinin bağlı bileşenindeki her tepe ve kenar sonunda ziyaret edilir. Bir u tepesinin hiç ziyaret edilmediğini, fakat v komşusunun ziyaret edildiğini varsayın. O hâlde v bir noktada işlenmiş, kenarları incelenmiş ve u’ya giden kenar u’yu keşfetmiş olmalıydı. Çelişki.

BFS

BFS uses two boolean arrays, discovered and processed, plus a parent array recording which vertex discovered each vertex. Discovered vertices wait in a FIFO queue, so the oldest, which are closest to the start, are expanded first.

BFS, discovered ve processed adlı iki Boole dizisi ile her tepeyi hangi tepenin keşfettiğini kaydeden parent dizisini kullanır. Keşfedilen tepeler bir FIFO kuyruğunda bekler; bu nedenle başlangıca en yakın olan, en önce keşfedilmiş tepeler önce genişletilir.

bfs(G, start):
    queue q = {start}; discovered[start] = true
    while q is not empty:
        v = dequeue(q)
        process_vertex_early(v)
        processed[v] = true
        for each edge (v, y):
            if not processed[y] or G is directed:
                process_edge(v, y)
            if not discovered[y]:
                enqueue(q, y)
                discovered[y] = true
                parent[y] = v
        process_vertex_late(v)

bfs(G, start):
    q kuyruğu = {start}; discovered[start] = true
    while q boş değilse:
        v = dequeue(q)
        process_vertex_early(v)
        processed[v] = true
        for her (v, y) kenarı:
            if not processed[y] or G yönlü ise:
                process_edge(v, y)
            if not discovered[y]:
                enqueue(q, y)
                discovered[y] = true
                parent[y] = v
        process_vertex_late(v)

The test not processed[y] stops an undirected edge being processed twice (it is seen from both ends). The three hooks process_vertex_early, process_edge and process_vertex_late are deliberately left empty: filling them in customises the traversal. Set them to print, and you print each vertex and each edge exactly once.

not processed[y] sınaması, yönsüz bir kenarın iki kez işlenmesini engeller (kenar her iki ucundan da görülür). process_vertex_early, process_edge ve process_vertex_late adlı üç uyarlama noktası bilinçli olarak boş bırakılmıştır; bunları doldurmak dolaşımı özelleştirir. Yazdırma yapacak şekilde tanımlarsanız her tepeyi ve her kenarı tam bir kez yazdırırsınız.

Cost. Each vertex is enqueued and dequeued once, and each edge is looked at twice: O(n + m) with adjacency lists.

Maliyet. Her tepe bir kez kuyruğa eklenir ve bir kez çıkarılır; her kenara iki kez bakılır: komşuluk listeleriyle O(n + m).

BFS ağacı ve en kısa yollar

The parent array defines a tree, rooted at the start vertex, with an edge from each vertex to the vertex that discovered it. This is the BFS tree.

parent dizisi, kökü başlangıç tepesi olan ve her tepeden onu keşfeden tepeye bir kenar içeren bir ağaç tanımlar. Bu, BFS ağacıdır.

Because BFS discovers vertices in order of increasing distance from the root, the BFS tree has a precious property: the tree path from the root to any vertex x uses the fewest possible edges of any path in the graph. That is, BFS computes shortest paths when every edge counts as 1. (For edges with different lengths, wait for Dijkstra in Lecture 14.)

BFS tepeleri kökten artan uzaklık sırasıyla keşfettiği için BFS ağacının değerli bir özelliği vardır: kökten herhangi bir x tepesine giden ağaç yolu, çizgedeki bütün yollar arasında mümkün olan en az sayıda kenarı kullanır. Yani her kenar 1 sayıldığında BFS en kısa yolları hesaplar. (Uzunlukları farklı kenarlar için Ders 14’teki Dijkstra algoritmasını bekleyin.)

Reconstructing the path. Parent pointers point towards the root, so you can only walk from x back to the root, not the other way. Walk backwards, or let recursion reverse the order for you:

Yolu yeniden oluşturma. Ebeveyn işaretçileri köke doğru yönelir; bu yüzden yalnızca x’ten köke geri yürüyebilirsiniz, tersi yönde değil. Geriye doğru yürüyün veya özyinelemenin sırayı sizin için tersine çevirmesine izin verin:

find_path(start, end, parent):
    if start == end or end == −1:
        print start
    else:
        find_path(start, parent[end], parent)
        print end

find_path(start, end, parent):
    if start == end or end == −1:
        print start
    else:
        find_path(start, parent[end], parent)
        print end

The recursive call happens before printing, so the printing comes out root-first.

Özyinelemeli çağrı yazdırmadan önce gerçekleştiği için çıktı kökten başlayarak üretilir.

Uygulama: Bağlı bileşenler

The connected components of an undirected graph are its separate pieces: sets of vertices with paths inside each set and no edges between sets. Many complicated-looking questions are really component questions. “Can a Rubik’s cube (or the 15-puzzle) be solved from every position?” asks whether the graph of legal positions, with edges for legal moves, is connected.

Yönsüz bir çizgenin bağlı bileşenleri, birbirinden ayrı parçalarıdır: her kümenin içinde yollar bulunan, fakat kümeler arasında kenar bulunmayan tepe kümeleri. Karmaşık görünen birçok soru aslında bir bileşen sorusudur. “Rubik küpü (veya 15 bulmacası) her konumdan çözülebilir mi?” sorusu, geçerli konumların tepe, geçerli hamlelerin kenar olduğu çizgenin bağlı olup olmadığını sorar.

Everything discovered by one BFS lies in the same component. So: run BFS from vertex 1, label everything it reaches as component 1; find the next undiscovered vertex and run BFS from it for component 2; repeat until every vertex is discovered.

Tek bir BFS’nin keşfettiği her şey aynı bileşendedir. Dolayısıyla 1 tepesinden BFS çalıştırın ve ulaştığı her şeyi bileşen 1 olarak etiketleyin; keşfedilmemiş sonraki tepeyi bulun ve bileşen 2 için oradan BFS başlatın; bütün tepeler keşfedilene kadar tekrarlayın.

connected_components(G):
    c = 0
    for each vertex i:
        if not discovered[i]:
            c = c + 1
            print "Component", c
            bfs(G, i)       (with process_vertex_early printing the vertex)

connected_components(G):
    c = 0
    for her i tepesi:
        if not discovered[i]:
            c = c + 1
            print "Bileşen", c
            bfs(G, i)   (process_vertex_early tepeyi yazdırır)

Total cost O(n + m), since each vertex and edge is touched once over all the searches.

Bütün aramalar boyunca her tepe ve kenara bir kez dokunulduğu için toplam maliyet O(n + m)’dir.

Uygulama: İki renkle boyama (iki parçalı çizgeler)

Vertex colouring assigns a colour to each vertex so that no edge joins two vertices of the same colour. A graph that can be coloured with only two colours is bipartite. Bipartite graphs are common: students and the courses they take form one (edges only go between a student and a course, never student-student or course-course).

Tepe boyama, hiçbir kenar aynı renkte iki tepeyi birleştirmeyecek biçimde her tepeye bir renk atar. Yalnızca iki renkle boyanabilen çizge iki parçalıdır. İki parçalı çizgeler yaygındır: öğrenciler ve aldıkları dersler böyle bir çizge oluşturur (kenarlar yalnızca öğrenciyle ders arasındadır; öğrenci–öğrenci veya ders–ders arasında asla değildir).

BFS finds a two-colouring, or proves there is none: whenever a vertex is discovered, colour it the opposite of its parent. Every processed edge is checked; if its endpoints have the same colour the graph is not bipartite.

BFS iki renkli bir boyama bulur veya böyle bir boyama olmadığını kanıtlar: her tepe keşfedildiğinde onu ebeveyninin karşıt rengine boyayın. İşlenen her kenar denetlenir; uçları aynı renkteyse çizge iki parçalı değildir.

twocolor(G):
    colour every vertex UNCOLOURED; bipartite = true
    for each vertex i:
        if not discovered[i]:
            colour[i] = WHITE
            bfs(G, i)

process_edge(x, y):
    if colour[x] == colour[y]:
        bipartite = false; report the offending edge (x, y)
    colour[y] = complement(colour[x])

twocolor(G):
    her tepenin rengini UNCOLOURED yap; bipartite = true
    for her i tepesi:
        if not discovered[i]:
            colour[i] = WHITE
            bfs(G, i)

process_edge(x, y):
    if colour[x] == colour[y]:
        bipartite = false; ihlal eden (x, y) kenarını bildir
    colour[y] = complement(colour[x])

The first vertex of each component can be given whichever colour we like; the rest is forced. Cost: O(n + m).

Her bileşenin ilk tepesine istediğimiz rengi verebiliriz; geri kalan renkler zorunlu olarak belirlenir. Maliyet: O(n + m).