An undirected graph G (think of it as a social network) is a graph in which edge

Question

An undirected graph G (think of it as a social network) is a graph in which edges are not directed. If (u, v) is an edge, then (v, u) is also an edge. Here is how you can generate a random undirected graph from the graph module we used: G graph.random_graph(10, 0.4, directed = False) Write a Python program to count the number of communities in an undirected graph Two communities, in this problem, are not connected at all. For example, the graph below has 3 communities: Nodes in undirected graphs do not have In and Out neighbors. Instead, they only have a Neighbors attribute. In other words, the ids of neighbors of node 0 are G.Neighbors[0].

Explanation / Answer

since i dont have the graph module i cannot code .But follwing is the pseudocode and logic :

For the above graph:

get the neighbours of first node

1-> 3,4,2,6

store this in a list l=[3,4,2,6]

now find the neighbours of the neighbours and add them to previous list but do not repeat elements

neighbours of 2->1,6,5

neighbours of 3->1,6

neighbours of 4->1

neighbpurs of 5->2

neighbour of 6->1,2,3

after adding all neighbours to a list and removing duplicates we get first community

l=[1,2,3,4,5,6]

visited_nodes=[]

add this to another list visited_nodes=visitednodes.extend(l) to keep track of visited nodes

community_count=community_count+1

no go on to node which are not in the visited_nodes so lets say 7

neighbour of 7->8,10

find the neighbours of neighbor like we did before and store it in a list

m=[7,8,9,10]

this is our second community

community_count=community_count+1

now add this to visited_nodes=visited_nodes.extend(m)

now go on again to node not in visited_node lets say 11

neighbour of 11->12

find the neighbours of neighbor like we did before and store it in a list

n=[11,12,13,14]

this is our third community

now add this to visited_nodes.extend(n)

community_count=community_count+1

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.