Tämän viikon tehtävät käsittelevät suunnattuja verkkoja. Edellisen viikon hyppytaulukon lisäksi teemana ovat suunnatut syklit.

Topologinen järjestys

Topologinen järjestys on verkon solmujen järjestys, jossa solmu a on ennen solmua b, jos solmusta a pääsee solmuun b. Esimerkiksi verkon

yksi topologinen järjestys on [4,1,5,2,3,6]: Topologinen järjestys on mahdollista muodostaa tarkalleen silloin, kun verkossa ei ole suunnattua sykliä.

Järjestyksen muodostaminen

Topologisen järjestyksen voi muodostaa syvyyshaun avulla. Ideana on käydä läpi verkon solmut ja aloittaa syvyyshaku jokaisesta solmusta, jota ei ole vielä käsitelty. Haun aikana solmuilla on kolme mahdollista väriä 0–2. Aluksi jokaisen solmun väri on 0.

Seuraava pseudokoodi esittää haun toiminnan:

function dfs(s)
    if color[s] == 1
        fail()
    if color[s] == 2
        return
    color[s] = 1
    for u in adj[s]
        dfs(u)
    color[s] = 2

Kun haku saapuu uuteen solmuun, se merkitsee solmun väriksi 1. Sitten kun se on käsitellyt kaikki solmusta lähtevät kaaret, se merkitsee solmun väriksi 2.

Jos haku tulee toista kautta solmuun, jonka värinä on 1, verkossa on negatiivinen sykli eikä topologista järjestystä voi muodostaa. Muuten yksi topologinen järjestys on käänteinen järjestys, jossa solmujen väriksi tuli 2.

Esimerkissämme haku voisi alkaa näin solmusta 1:

Tämän jälkeen haku peruuttaa takaisin solmuun 1: Seuraava haku alkaa solmusta 4: Tämän haun jälkeen koko verkko on käsitelty: Tuloksena on topologinen järjestys [4,5,1,2,3,6]. Huomaa, että tämä on eri järjestys kuin ylempänä, ja mahdollisia järjestyksiä on yleensä suuri määrä.