Graf bo'ylab yurish - BFS va DFS

metro = {
    "Chilonzor":     ["Mirzo Ulug'bek", "Novza"],
    "Novza":         ["Chilonzor", "Milliy bog'"],
    "Milliy bog'":   ["Novza", "Xalqlar do'stligi"],
    "Xalqlar do'stligi": ["Milliy bog'", "Paxtakor"],
    "Paxtakor":      ["Xalqlar do'stligi", "Mustaqillik maydoni", "Alisher Navoiy"],
    "Mustaqillik maydoni": ["Paxtakor", "Amir Temur xiyoboni"],
    "Alisher Navoiy": ["Paxtakor", "G'afur G'ulom"],
    "G'afur G'ulom": ["Alisher Navoiy"],
    "Amir Temur xiyoboni": ["Mustaqillik maydoni"],
    "Mirzo Ulug'bek": ["Chilonzor"],
}

from collections import deque


def bfs(graf, boshlangich):
    """Grafni daraja bo'ylab aylanadi. O(V + E)."""
    korilgan = {boshlangich}
    navbat = deque([boshlangich])
    tartib = []

    while navbat:
        joriy = navbat.popleft()          # navbatning BOSHIDAN
        tartib.append(joriy)

        for qoshni in graf[joriy]:
            if qoshni not in korilgan:
                korilgan.add(qoshni)      # navbatga qo'shishda belgilaymiz
                navbat.append(qoshni)

    return tartib


for raqam, bekat in enumerate(bfs(metro, "Paxtakor"), start=1):
    print(f"{raqam:>2}. {bekat}")

from collections import deque


def eng_qisqa_yol(graf, boshlanish, tugash):
    """Vaznsiz grafda eng qisqa yo'lni topadi. O(V + E)."""
    if boshlanish == tugash:
        return [boshlanish]

    korilgan = {boshlanish}
    navbat = deque([boshlanish])
    qayerdan = {boshlanish: None}          # yo'lni tiklash uchun

    while navbat:
        joriy = navbat.popleft()

        for qoshni in graf[joriy]:
            if qoshni in korilgan:
                continue

            korilgan.add(qoshni)
            qayerdan[qoshni] = joriy
            navbat.append(qoshni)

            if qoshni == tugash:           # topdik - yo'lni tiklaymiz
                yol = []
                tugun = tugash
                while tugun is not None:
                    yol.append(tugun)
                    tugun = qayerdan[tugun]
                return yol[::-1]

    return None                            # yo'l yo'q


yol = eng_qisqa_yol(metro, "Mirzo Ulug'bek", "G'afur G'ulom")

print("Eng qisqa marshrut:")
for raqam, bekat in enumerate(yol, start=1):
    print(f"  {raqam}. {bekat}")
print(f"\nJami: {len(yol) - 1} ta bekat")

from collections import deque


def masofalar(graf, boshlangich):
    """Har bir vershinagacha bo'lgan eng qisqa masofani hisoblaydi."""
    masofa = {boshlangich: 0}
    navbat = deque([boshlangich])

    while navbat:
        joriy = navbat.popleft()
        for qoshni in graf[joriy]:
            if qoshni not in masofa:
                masofa[qoshni] = masofa[joriy] + 1
                navbat.append(qoshni)

    return masofa


print("Paxtakordan masofalar:")
for bekat, qadam in sorted(masofalar(metro, "Paxtakor").items(), key=lambda j: j[1]):
    print(f"  {qadam} bekat  {'#' * qadam:<6} {bekat}")

def dfs_rekursiv(graf, joriy, korilgan=None, tartib=None):
    """Chuqurlik bo'yicha aylanish. O(V + E)."""
    if korilgan is None:
        korilgan, tartib = set(), []

    korilgan.add(joriy)
    tartib.append(joriy)

    for qoshni in graf[joriy]:
        if qoshni not in korilgan:
            dfs_rekursiv(graf, qoshni, korilgan, tartib)

    return tartib


for raqam, bekat in enumerate(dfs_rekursiv(metro, "Paxtakor"), start=1):
    print(f"{raqam:>2}. {bekat}")

def dfs_stek(graf, boshlangich):
    """Rekursiyasiz DFS - stek yordamida."""
    korilgan = set()
    stek = [boshlangich]
    tartib = []

    while stek:
        joriy = stek.pop()                # stekning OXIRIDAN - BFS dan yagona farq!

        if joriy in korilgan:
            continue

        korilgan.add(joriy)
        tartib.append(joriy)

        for qoshni in reversed(graf[joriy]):
            if qoshni not in korilgan:
                stek.append(qoshni)

    return tartib


print(dfs_stek(metro, "Paxtakor")[:5])

def komponentlar(graf):
    """Grafning bog'langan bo'laklarini topadi."""
    korilgan = set()
    natija = []

    for vershina in graf:
        if vershina in korilgan:
            continue

        komponent = []
        stek = [vershina]

        while stek:
            joriy = stek.pop()
            if joriy in korilgan:
                continue
            korilgan.add(joriy)
            komponent.append(joriy)
            stek.extend(q for q in graf[joriy] if q not in korilgan)

        natija.append(sorted(komponent))

    return natija


tarmoq = {
    "Husanboy": ["Sardor"],
    "Sardor": ["Husanboy", "Malika"],
    "Malika": ["Sardor"],
    "Bekzod": ["Nodira"],
    "Nodira": ["Bekzod"],
    "Aziza": [],
}

for raqam, guruh in enumerate(komponentlar(tarmoq), start=1):
    print(f"{raqam}-guruh ({len(guruh)} kishi): {', '.join(guruh)}")

def sikl_bormi(graf):
    """Yo'naltirilmagan grafda sikl borligini tekshiradi."""
    korilgan = set()

    def tekshir(joriy, ota):
        korilgan.add(joriy)
        for qoshni in graf[joriy]:
            if qoshni not in korilgan:
                if tekshir(qoshni, joriy):
                    return True
            elif qoshni != ota:          # ko'rilgan va otamiz emas -> sikl
                return True
        return False

    for vershina in graf:
        if vershina not in korilgan:
            if tekshir(vershina, None):
                return True
    return False


daraxt = {"A": ["B", "C"], "B": ["A"], "C": ["A"]}
sikli_bor = {"A": ["B", "C"], "B": ["A", "C"], "C": ["A", "B"]}

print("Daraxtda sikl:", sikl_bormi(daraxt))
print("Uchburchakda sikl:", sikl_bormi(sikli_bor))

def topologik_sarala(bogliqliklar):
    """Bajarish tartibini aniqlaydi. DAG uchun. O(V + E)."""
    korilgan = set()
    jarayonda = set()
    natija = []

    def yur(vazifa):
        if vazifa in jarayonda:
            raise ValueError(f"Aylanma bog'liqlik: {vazifa}")
        if vazifa in korilgan:
            return

        jarayonda.add(vazifa)
        for keyingi in bogliqliklar.get(vazifa, []):
            yur(keyingi)
        jarayonda.discard(vazifa)

        korilgan.add(vazifa)
        natija.append(vazifa)

    for vazifa in bogliqliklar:
        yur(vazifa)

    return natija[::-1]


# "A: [B, C]" = A ni bajarish uchun avval B va C kerak
loyiha = {
    "Saytni ishga tushirish": ["Testlash", "Serverni sozlash"],
    "Testlash": ["Backend yozish", "Frontend yozish"],
    "Backend yozish": ["Ma'lumotlar bazasini loyihalash"],
    "Frontend yozish": ["Dizayn tayyorlash"],
    "Ma'lumotlar bazasini loyihalash": [],
    "Dizayn tayyorlash": [],
    "Serverni sozlash": [],
}

print("Bajarish tartibi:")
for raqam, vazifa in enumerate(topologik_sarala(loyiha), start=1):
    print(f"  {raqam}. {vazifa}")