Testing for Unconnected Components in an Undirected Graph
With a graph structure it is possible that parts of the graph will not be connected to each other. An example of this would be with social networks, not all users are friends with other users.
The code will find the total number of connected components of the graph, or graph parts in an undirected graph.
See code below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#Uses python3 # Given an undirected graph with n vertices and m edges, # compute the number of connected components in it. import sys class UserGraph: def __init__(self): self.data = [] # data list from user self.edges = [] # convert data list into edges self.cc = [] #connected components self.cc_cnt = 0 #connected components count self.visited = [] # keep track if visited node before self.adj = [] # adjancency matrix def read(self): """read the input data file """ input = sys.stdin.read() self.data = list(map(int, input.split())) def explore(self,k_node): """start with k_node and recursively check all edges """ self.visited[k_node] = True self.cc[k_node] = self.cc_cnt for j in range(len(self.visited)): if self.adj[k_node][j] and not self.visited[j]: success = self.explore(j) def number_of_components(self): """Test if nodes are connected use depth first search and determine connected number_of_components check if nodes are in the same component """ for k_node in range(len(self.adj)): if not self.visited[k_node]: self.cc_cnt += 1 self.explore(k_node) def process_input(self): """process the input from data file """ n, m = self.data[0:2] self.data = self.data[2:] self.edges = list(zip(self.data[0:(2 * m):2], self.data[1:(2 * m):2])) self.adj = [[0] * n for _ in range(n)] self.visited = [False] * n # haven't visited any nodes self.cc = [-1] * n # nothing is connected def populate_adjacency_matrix(self): """ create symmetric adjancency matrix for undirected graph """ for (a, b) in self.edges: self.adj[a - 1][b-1] = 1 self.adj[b - 1][a-1] = 1 # print(self.adj) def graph_components(self): self.process_input() self.populate_adjacency_matrix() self.number_of_components() return self.cc_cnt if __name__ == '__main__': test_Graph = UserGraph() test_Graph.read() print(test_Graph.graph_components()) |
Leave a Reply