<jupyter_start><jupyter_text>Most students confuse SPT and MST algorithms. Here is the difference: MST: The minimum spanning tree Prim's and Kruskal's algorithms will be analyzed in this notebook to find MST. These algorithms work only for undirected graphs. Prim's algorithm requires a source vertex to be defined. However, Kruskal's does not require any source vertex to be defined. Prim's algorithm finds the minimal weight spanning tree starting from a given node while continuing to visit each node. Kruskal's algorithm finds minimal weight spanning tree starting from the shortest edges of the nodes that has not been visited while continuing to visit each nodeA minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together.  SPT: Shortest path treeCheck the Djikstra and Bellman-Ford algorithms in this depository to find SPT from single source.Dijkstra and Bellman Ford are both for finding all the shortest paths from a defined single start node to all other nodes. They can be used for directed or undirected graphs.  Running times of MST & SPT algorithms:DJKSTRA with heapq: O(E*logV), Prims: O(E*log V), KRUSKAL: (E*logE)<jupyter_code># Prepare all the test sets for directed graphs, undirected graphs, adjacency lists, and dictionary of connections 

import numpy as np
np.random.seed(0)

# Create a directed graph with random integers from 0 to 7, that is size (7,7)
probability_set = [0.7, 0.05, 0.05, 0.05, 0.05, 0.05, 0.05]
weight_list = np.arange(0,7)
directed_graph = np.random.choice(weight_list, p = probability_set, size = (7,7))
size = 7
for i in range(len(directed_graph)):
    for j in range(len(directed_graph[i])):
        if i == j: 
            directed_graph[i][j] = 0
print('directed graph')
print(directed_graph, '\n')


# create an adjeceny list from a directed graph
adj_list = []
for i in range(len(directed_graph)): # each row
    for j in range(len(directed_graph[i])): # each column
        if directed_graph[i][j] == 0:
            continue
        adj_list.append([i, j, directed_graph[i][j], ]) # i, w, v
print('adj list of a directed graph where all connections can be seen in u, v, w format')
print(adj_list, '\n')


# create an undirected graph in matrix form (where a---b == b---a)
size = 10
undirected_graph_matrix = np.zeros([size, size])
probability_set = [0.5, 0.05, 0.1, 0.1, 0.03, 0.03, 0.03, 0.01, 0.1, 0.05]
vertex_list = np.arange(0,10)
for i in range(size): # each vertex
    for j in range(size): # immediate connections of each vertex
        random_weight = np.random.choice(vertex_list, p = probability_set)
        undirected_graph_matrix[i][j] = random_weight
        undirected_graph_matrix[j][i] = random_weight
        if i == j:
            undirected_graph_matrix[i][j] = 0   
print('undirected graph')
print(undirected_graph_matrix, '\n')   


# create a dictionary to view just the connections of an undirected graph without the weights
all_connections = {}
for i in range(len(undirected_graph_matrix)): # for each key make a list for values
    all_connections[i] =  []  
    for j,v in enumerate(undirected_graph_matrix[i]): # each item in the values list
        if v == 0:
            continue
        else:
            all_connections[i].append(j)
print('dictionary view of connections of an undirected graph without the weights')
print(all_connections, '\n')


# create an undirected graph in a matrix format where connections can be seen once
size = 10
undirected_graph_matrix2 = np.zeros([size, size])
probability_set = [0.5, 0.05, 0.1, 0.1, 0.03, 0.03, 0.03, 0.01, 0.1, 0.05]
vertex_list = np.arange(0,10)
k = -1
for i in range(size): # each vertex
    k += 1
    for j in range(k, size): # immediate connections of each vertex
        random_weight = np.random.choice(vertex_list, p = probability_set)
        undirected_graph_matrix2[i][j] = random_weight
        if i == j:
            undirected_graph_matrix2[i][j] = 0   
print('undirected graph where connections can be seen once')
print(undirected_graph_matrix2, '\n')    


# create a dictionary from an undirected graph where connections can be seen for once
all_connections2 = {}
for i in range(len(undirected_graph_matrix)): # for each key make a list for values
    all_connections2[i] =  []  
    for j,v in enumerate(undirected_graph_matrix[i]): # each item in the values list
        if v == 0:
            continue
        else:
            all_connections2[i].append(j)
print('dictionary view of a connections of an undirected graph where connections can be seen once without the weights')
print(all_connections2, '\n')<jupyter_output>directed graph
[[0 1 0 0 0 0 0]
 [4 0 0 2 0 0 5]
 [0 0 0 3 2 4 6]
 [2 0 2 0 0 0 5]
 [0 0 0 2 0 0 0]
 [0 0 0 5 0 0 0]
 [0 0 0 0 0 0 0]] 

adj list of a directed graph where all connections can be seen in u, v, w format
[[0, 1, 1], [1, 0, 4], [1, 3, 2], [1, 6, 5], [2, 3, 3], [2, 4, 2], [2, 5, 4], [2, 6, 6], [3, 0, 2], [3, 2, 2], [3, 6, 5], [4, 3, 2], [5, 3, 5]] 

undirected graph
[[0. 0. 0. 0. 8. 0. 9. 3. 0. 0.]
 [0. 0. 9. 0. 0. 3. 0. 3. 2. 8.]
 [0. 9. 0. 0. 3. 0. 7. 1. 0. 0.]
 [0. 0. 0. 0. 0. 3. 3. 9. 0. 0.]
 [8. 0. 3. 0. 0. 9. 0. 2. 0. 8.]
 [0. 3. 0. 3. 9. 0. 6. 0. 2. 5.]
 [9. 0. 7. 3. 0. 6. 0. 2. 2. 3.]
 [3. 3. 1. 9. 2. 0. 2. 0. 2. 0.]
 [0. 2. 0. 0. 0. 2. 2. 2. 0. 8.]
 [0. 8. 0. 0. 8. 5. 3. 0. 8. 0.]] 

dictionary view of connections of an undirected graph without the weights
{0: [4, 6, 7], 1: [2, 5, 7, 8, 9], 2: [1, 4, 6, 7], 3: [5, 6, 7], 4: [0, 2, 5, 7, 9], 5: [1, 3, 4, 6, 8, 9], 6: [0, 2, 3, 5, 7, 8, 9], 7: [0, 1, 2, 3, 4, 6, 8], 8: [1, 5, 6, 7, 9], 9: [1, 4, 5, 6, 8]} 

undirecte[...]<jupyter_text>Given an undirected graph, determine if it contains cycle:Approach 1: DFS from an arbitrary vertex and keep going until you see a market vertex but this has a potential danger since it traverses back and forth and sees the already seen vertices, you may not count the node where it is seen. The worst case would be O(V+E)Approach 2: Weighted Quick Union UF object:For each edge, check if the two vertices are connected, if not union them. Iterate through all vertices. If they are already connected, it means there is a cycle. Worst case is O(V + Elog*V) if path compressionn is applied<jupyter_code># Detect if there is any cycles in an undirected graph where connections can be seen once
# Prepare the test set as dict of connections 
test_graph_cycle = {0: [1], 1: [3, 6], 2: [4, 5], 3: [2], 4: [0], 5: [], 6: []} # 2--4--0 cycle is added

class Graph: 
    def __init__(self, graph): 
        self.graph = graph # default dictionary to store graph in adj list format
        self.parent = np.arange(0, len(self.graph))
         
            
    def isCyclic(self):  
        for k,v in self.graph.items(): 
            for each_value in v: 
                x = self.find_parent(k)  
                y = self.find_parent(each_value) 
                if x == y: 
                    print('graph contains cyclic connection')
                    return True 
                else: # union them (assign the item's parent in the value to the key's parent)
                    self.parent[y] = x 

    def find_parent(self, i): 
        if self.parent[i] != i: # has no parent return the index
            return self.find_parent(self.parent[i])
        else: # has a parent return the parent's index
            return self.parent[i] 
  

    
# Create a graph given in the above diagram 
g = Graph(test_graph_cycle) 
# test the class
print(g.isCyclic())
# view the parent list after all vertices are seen
print(g.parent)
# Apply path compression and union by rank method on an acyclic directed graph and detect cycles
# Prepare a test set as a dictionary view of an acyclic undirected graph where connections seen once

test_conn = test_graph_cycle = {0: [1], 1: [3, 6], 2: [4, 5], 3: [2], 4: [], 5: [], 6: []}
    
class Graph2():
    def __init__(self, graph):
        self.graph = graph 
        self.parent = np.arange(0, len(graph)) # initialize the parent of the vertex to itself 
        self.rank = np.zeros(len(graph)) # all ranks start from zero for each vertex
                
        
    def is_graph_cyclic(self):
        for k,v in self.graph.items(): # for each vertex
            k_parent = self.find_parent(k)
            for j in v: # for each connection of each vertex
                j_parent = self.find_parent(j)
                if k_parent == j_parent:
                    return True
                else:
                    self.union(k_parent, j_parent)
        
        
    def find_parent(self, vertex):
        if self.parent[vertex] != vertex:
            self.parent[vertex] = self.find_parent(self.parent[vertex])
        return self.parent[vertex]
             
    
    def union(self, u, v): # path compression and union by rank 
        if self.rank[u] > self.rank[v]:
            self.parent[v] = u
        elif self.rank[u] < self.rank[v]:
            self.parent[u] = v
        else: # if the ranks are the same
            self.parent[v] = u
            self.rank[u] += 1
            

            
gtest = Graph2(test_conn)
print(gtest.is_graph_cyclic())
# view the parent and rank after all vertices are visited
print(gtest.parent, gtest.rank)

# Prepare an undirected graph in matrix form where connections can be seen once to write Kruskal's

test_matrix = undirected_graph_matrix
print(undirected_graph_matrix)

# represent the matrix connection as an adjacency list
adj_list = []
for i in range(len(test_matrix)):
    for j in range(len(test_matrix[i])):
        if i != j and test_matrix[i][j] != 0:
            adj_list.append([i,j, test_matrix[i][j]]) # the representation is source, target, weight as u, v, w
print(sorted(adj_list, key = lambda x: x[2]))


# view thnumber of vertices:
V = list(set([i[0] for i in adj_list] + [i[1] for i in adj_list]))
print(V)
# Write Kruskals to find the MST of a given adjacency list representation of an undirected graph 

class Kruskals_MST():
    def __init__(self, connections): # the connections format is [[u,v,w], ..] as adjacency list
        self.connections = sorted(connections, key = lambda item : item[2]) 
        # assign the parents list to indices of vertices
        self.parent = np.arange(len(test_matrix))
        # initial ranks are assigned to 0
        self.rank = np.zeros(len(test_matrix))
        
        
    def find_parent(self, item):
        if self.parent[item] != item:
            return self.find_parent(self.parent[item])
        else:
            return item
        
       
    def create_MST(self):
        self.MST = []
        i = 0 # each item's index that will be in the MST
        e = 0 # each item in connections list
        while i < (len(self.parent) - 1) and e < len(self.connections):
            # MST can only have V-1 number of items in it. This length will cover to visit all vertices
            u, v, w = self.connections[e]
            u_parent = self.find_parent(u)
            v_parent = self.find_parent(v)
            if u_parent != v_parent:
                self.MST.append(self.connections[e])
                self.union(u_parent, v_parent)
                i += 1
            e +=1
        return self.MST
   
        
    def union(self, vertex1, vertex2): # union by rank and path compression
        if self.rank[vertex1] > self.rank[vertex2]:
            self.parent[vertex2] = self.parent[vertex1]
        elif self.rank[vertex1] < self.rank[vertex2]: 
            self.parent[vertex1] = self.parent[vertex2]
        else: # only increase the rank of one of the vertices if both have the same rank
            self.parent[vertex1] = self.parent[vertex2]
            self.rank[vertex1] += 1
        
        
test_kruskals = Kruskals_MST(adj_list)
print(test_kruskals.create_MST())
# print(test_kruskals.parent)
# Apply prims algorithm to find the MST from a defined starting vertex of the test graph
# input is unsorted adj list

test_matrix = undirected_graph_matrix

def Prims(vertex, adj_list): 
  
    # initialize empty edges array and empty MST
    MST = []
    edges = []
    visited = []

    # run prims algorithm until we create an MST that contains every vertex from the graph
    while len(MST) < len(test_matrix) - 1:
    
        # mark this vertex as visited, vertex = 0 is initially chosen.
        visited.append(vertex)

        # add each edge to list of potential edges
        for r in range(0, len(adj_list)): # this loop will only append the current vertex's connections. 
            edge = adj_list[r]
            if edge[0] == vertex and edge[2] != 0:
                edges.append(edge)
        # find edge with the smallest weight to a vertex that has not yet been visited
        minEdge = [None,None,np.inf]
        for e in range(0, len(edges)):
            if edges[e][2] < minEdge[2] and edges[e][1] not in visited:
                minEdge = edges[e]
        
        # push min edge to MST
        MST.append(minEdge)
        # start at new vertex and reset min edge
        vertex = minEdge[1]
        # remove the used edge from the edges list
        edges.remove(minEdge)
        
        
    return MST 
  
# pass the # of vertices and the graph to run prims algorithm 
#%timeit prims(0, adj_list)
print('result:', Prims(0, adj_list))<jupyter_output>result: [[0, 7, 3.0], [7, 2, 1.0], [7, 4, 2.0], [7, 6, 2.0], [7, 8, 2.0], [8, 1, 2.0], [8, 5, 2.0], [6, 3, 3.0], [6, 9, 3.0]]
{'fraction_non_alphanumeric': 0.108623118558612, 'fraction_numerical': 0.03470008156002076, 'mean_word_length': 2.5777188328912466, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 9, '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': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '565165', 'license': 'MIT', 'n_tokens_mistral': 4726, 'n_tokens_neox': 4267, 'n_words': 1708, 'path': 'Prims_and_Kruskals_MST_algorithms.ipynb', 'repo_name': 'volkansonmez/Algorithms-and-Data-Structures-2-', 'size': '13487'}