Graf Teorisi

// Ağırlıklı graf örneği
Graf G = {
    "A": [("B", 5), ("C", 3)],
    "B": [("D", 7)],
    "C": [("D", 2)]
}

// n×n matrix, A[i][j] = 1 eğer (i,j) kenarı varsa
Matrix A = {
    //   A  B  C  D
    A: [ 0, 1, 1, 0 ],  // A düğümü
    B: [ 1, 0, 0, 1 ],  // B düğümü
    C: [ 1, 0, 0, 1 ],  // C düğümü
    D: [ 0, 1, 1, 0 ]   // D düğümü
}

// Her düğüm için komşularının listesi
AdjList = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C"]
}

// Tüm kenarların listesi
EdgeList = [
    ("A", "B"),
    ("A", "C"),
    ("B", "D"),
    ("C", "D")
]

function DFS(graf, başlangıç):
    visited = new Set()
    stack = [başlangıç]
    
    while stack is not empty:
        düğüm = stack.pop()
        
        if düğüm not in visited:
            visited.add(düğüm)
            process(düğüm)  // Düğümü işle
            
            for komşu in graf[düğüm]:
                if komşu not in visited:
                    stack.append(komşu)

// Döngü tespiti için DFS
function hasCycle(graf):
    renk = {} // Beyaz=0, Gri=1, Siyah=2
    
    for düğüm in graf:
        if renk[düğüm] == 0:
            if dfsVisit(graf, düğüm, renk):
                return True
    return False

function dfsVisit(graf, düğüm, renk):
    renk[düğüm] = 1  // Gri (işleniyor)
    
    for komşu in graf[düğüm]:
        if renk[komşu] == 1:  // Back edge
            return True
        if renk[komşu] == 0 and dfsVisit(graf, komşu, renk):
            return True
    
    renk[düğüm] = 2  // Siyah (tamamlandı)
    return False

function BFS(graf, başlangıç):
    visited = new Set()
    queue = new Queue()
    distance = {}
    
    queue.enqueue(başlangıç)
    visited.add(başlangıç)
    distance[başlangıç] = 0
    
    while queue is not empty:
        düğüm = queue.dequeue()
        process(düğüm)
        
        for komşu in graf[düğüm]:
            if komşu not in visited:
                visited.add(komşu)
                distance[komşu] = distance[düğüm] + 1
                queue.enqueue(komşu)

// En kısa yol bulma (ağırlıksız graf)
function shortestPath(graf, başlangıç, hedef):
    if başlangıç == hedef:
        return [başlangıç]
    
    visited = new Set()
    queue = new Queue()
    parent = {}
    
    queue.enqueue(başlangıç)
    visited.add(başlangıç)
    parent[başlangıç] = null
    
    while queue is not empty:
        düğüm = queue.dequeue()
        
        for komşu in graf[düğüm]:
            if komşu not in visited:
                visited.add(komşu)
                parent[komşu] = düğüm
                queue.enqueue(komşu)
                
                if komşu == hedef:
                    return reconstructPath(parent, hedef)
    
    return null  // Yol bulunamadı

function dijkstra(graf, kaynak):
    distance = {}
    visited = new Set()
    parent = {}
    priorityQueue = new MinHeap()
    
    // Başlangıç değerleri
    for düğüm in graf:
        distance[düğüm] = ∞
        parent[düğüm] = null
    
    distance[kaynak] = 0
    priorityQueue.insert((kaynak, 0))
    
    while priorityQueue is not empty:
        (düğüm, dist) = priorityQueue.extractMin()
        
        if düğüm in visited:
            continue
        
        visited.add(düğüm)
        
        for (komşu, ağırlık) in graf[düğüm]:
            newDistance = distance[düğüm] + ağırlık
            
            if newDistance < distance[komşu]:
                distance[komşu] = newDistance
                parent[komşu] = düğüm
                priorityQueue.insert((komşu, newDistance))
    
    return distance, parent

// Yol yeniden oluşturma
function getPath(parent, kaynak, hedef):
    if parent[hedef] == null and hedef != kaynak:
        return null  // Yol yok
    
    path = []
    current = hedef
    
    while current != null:
        path.prepend(current)
        current = parent[current]
    
    return path

function kruskal(graf):
    mst = []
    edges = getAllEdges(graf)
    edges.sort()  // Ağırlığa göre sırala
    
    unionFind = new UnionFind(graf.vertices)
    
    for (u, v, weight) in edges:
        if unionFind.find(u) != unionFind.find(v):
            mst.append((u, v, weight))
            unionFind.union(u, v)
            
            if mst.length == |V| - 1:
                break
    
    return mst

function prim(graf, start):
    mst = []
    visited = new Set([start])
    priorityQueue = new MinHeap()
    
    // Başlangıç düğümünün kenarlarını ekle
    for (neighbor, weight) in graf[start]:
        priorityQueue.insert((weight, start, neighbor))
    
    while priorityQueue is not empty and visited.size < |V|:
        (weight, u, v) = priorityQueue.extractMin()
        
        if v in visited:
            continue
        
        mst.append((u, v, weight))
        visited.add(v)
        
        for (neighbor, edgeWeight) in graf[v]:
            if neighbor not in visited:
                priorityQueue.insert((edgeWeight, v, neighbor))
    
    return mst

function topologicalSort(graf):
    inDegree = {}
    result = []
    queue = new Queue()
    
    // Gelen dereceleri hesapla
    for düğüm in graf:
        inDegree[düğüm] = 0
    
    for düğüm in graf:
        for komşu in graf[düğüm]:
            inDegree[komşu]++
    
    // Gelen derecesi 0 olanları bul
    for düğüm in graf:
        if inDegree[düğüm] == 0:
            queue.enqueue(düğüm)
    
    while queue is not empty:
        düğüm = queue.dequeue()
        result.append(düğüm)
        
        for komşu in graf[düğüm]:
            inDegree[komşu]--
            if inDegree[komşu] == 0:
                queue.enqueue(komşu)
    
    if result.length != |V|:
        return null  // Döngü var
    
    return result

function topologicalSortDFS(graf):
    visited = new Set()
    stack = []
    
    for düğüm in graf:
        if düğüm not in visited:
            dfsVisit(graf, düğüm, visited, stack)
    
    return stack.reverse()

function dfsVisit(graf, düğüm, visited, stack):
    visited.add(düğüm)
    
    for komşu in graf[düğüm]:
        if komşu not in visited:
            dfsVisit(graf, komşu, visited, stack)
    
    stack.append(düğüm)  // Bitirme sırasına göre

// Oyun haritasında pathfinding
function gamePathfinding(harita, başlangıç, hedef):
    // A* algoritması ile heuristik arama
    openSet = new PriorityQueue()
    closedSet = new Set()
    
    gScore = {başlangıç: 0}
    fScore = {başlangıç: heuristic(başlangıç, hedef)}
    
    openSet.enqueue((fScore[başlangıç], başlangıç))
    
    while openSet is not empty:
        current = openSet.dequeue().second
        
        if current == hedef:
            return reconstructPath(current)
        
        closedSet.add(current)
        
        for komşu in getNeighbors(current):
            if komşu in closedSet:
                continue
            
            tentativeG = gScore[current] + distance(current, komşu)
            
            if tentativeG < gScore.get(komşu, ∞):
                gScore[komşu] = tentativeG
                fScore[komşu] = tentativeG + heuristic(komşu, hedef)
                openSet.enqueue((fScore[komşu], komşu))