14. Connected Components

In [1]:

from utils.graph import GraphAdjList as Graph
from utils.graph_properties import GraphPropertiesAdjList as gp

from utils.graph import GraphAdjList as Graph from utils.graph_properties import GraphPropertiesAdjList as gp

In [2]:

g = Graph()
g.insert_node_undirected(1, 0)
g.insert_node_undirected(2, 1)
g.insert_node_undirected(3, 4)

g = Graph() g.insert_node_undirected(1, 0) g.insert_node_undirected(2, 1) g.insert_node_undirected(3, 4)

In [3]:

g.graph

g.graph

Out[3]:

defaultdict(list, {1: [0, 2], 0: [1], 2: [1], 3: [4], 4: [3]})

In [4]:

num_vertices = gp.num_vertices(g.graph)

num_vertices = gp.num_vertices(g.graph)

In [13]:

def DFS_util(graph, node, visited_nodes, temp):
    visited_nodes.add(node)
    temp.append(node)
    for neighbour in graph[node]:
        if neighbour not in visited_nodes:
            DFS_util(graph, neighbour, visited_nodes, temp)
    return temp

def DFS_util(graph, node, visited_nodes, temp): visited_nodes.add(node) temp.append(node) for neighbour in graph[node]: if neighbour not in visited_nodes: DFS_util(graph, neighbour, visited_nodes, temp) return temp

In [16]:

def get_connected_components(graph, num_vertices):
    visited_node_set = set()
    count_connected = 0
    components = []

    for node in range(num_vertices):
        if node not in visited_node_set:
            temp = []
            component = DFS_util(graph, node, visited_node_set, temp)
            components.append(component)
            count_connected += 1

    print(count_connected)
    print(components)

def get_connected_components(graph, num_vertices): visited_node_set = set() count_connected = 0 components = [] for node in range(num_vertices): if node not in visited_node_set: temp = [] component = DFS_util(graph, node, visited_node_set, temp) components.append(component) count_connected += 1 print(count_connected) print(components)

In [17]:

get_connected_components(g.graph, num_vertices)

get_connected_components(g.graph, num_vertices)

2
[[0, 1, 2], [3, 4]]

In [ ]: