<jupyter_start><jupyter_text>Graph<jupyter_code>n = 6

graph = {
    1:[(7,2), (9,3), (14,6)],
    2:[(7,1), (10,3), (15,4)],
    3:[(9,1), (10,2), (11,4), (2,6)],
    4:[(15,2), (11,3), (6,5)],
    5:[(6,4),(9,6)],
    6:[(14,1),(2,3), (9,5)],
}

graph2 = [
    (1,2,7),
    (1,3,9),
    (1,6,14),
    (2,3,10),
    (2,4,15),
    (3,4,11),
    (3,6,2),
    (4,5,6),
    (5,6,9),
]

graph3 = [
    (1,2),
    (1,3),
    (1,6),
    (2,3),
    (3,6),
    (4,5),
]<jupyter_output><empty_output><jupyter_text>Dijkstra Algo<jupyter_code>from heapq import heappush, heappop

def dijkstra(graph, start):
    weights = [None]* (len(graph)+1)
    heap = [(0, start)] 
    while heap:
        path_len, min_node = heappop(heap)
        if weights[min_node] is None:
            weights[min_node] = path_len
            for edge_len, node in graph[min_node]:
                if weights[node] is None:
                    heappush(heap, (edge_len+path_len, node))
    return weights                

dijkstra(graph1, 1)<jupyter_output><empty_output><jupyter_text>Kruskal<jupyter_code>def kruskal(graph, n): 
    gp = {i:i for i in range(1,n+1)}
    sets = { i:[i] for i in range(1,n+1)}
    graph.sort(key=lambda x:x[2])
    
    edges_used = []
    for u,v,w in graph:
        if gp[u]!=gp[v]:
            temp = gp[v] 
            for node in sets[gp[v]]:
                gp[node] = gp[u]
                sets[gp[u]].append(node)
            del sets[temp]
            edges_used.append((u,v,w)) 
    return edges_used      
    
kruskal(graph2, n)<jupyter_output><empty_output><jupyter_text>Connected Components (using kruskal)<jupyter_code>def connected_components(graph, n): 
    gp = {i:i for i in range(1,n+1)}
    sets = { i:[i] for i in range(1,n+1)}
    
    for u,v in graph:
        if gp[u]!=gp[v]:
            temp = gp[v] 
            for node in sets[gp[v]]:
                gp[node] = gp[u]
                sets[gp[u]].append(node)
            del sets[temp]
    return len(sets)      
    
connected_components(graph3, n)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.18716577540106952, 'fraction_numerical': 0.05396208070004861, 'mean_word_length': 2.303370786516854, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '497192', 'license': 'Apache-2.0', 'n_tokens_mistral': 915, 'n_tokens_neox': 862, 'n_words': 155, 'path': 'Graphs.ipynb', 'repo_name': 'aadishgoel2013/Must-Do-Coding-Questions', 'size': '2057'}