Say you have an adjacency matrix like the one in your question. You can determine connected components by doing a breadth-first (or depth-first) search in the matrix without having to remake copies or delete vertices.
You'll start each connected component search with the first vertex that you haven't placed in a component yet. The first one will be vertex $v_1$:
Initialize the connected component $C_1 = \{v_1\}$ and then move across $v_1$'s row in the adjacency matrix. We see that $v_1$ is adjacent to $v_5$, so $v_5$ gets added to the component $C_1 = \{v_1,v_5\}$, and we move on to $v_5$'s row. $v_5$ is connected to $v_1$ (seen already) and $v_9$, so add $v_9$ to $C_1$, and move on to $v_9$, which is adjacent to $v_5$ (seen already). Since we've reached the end of this tree, we're done with this component and get $C_1 = \{v_1,v_5,v_9\}$.
Now, take the next vertex that we haven't seen yet ($v_2$) and set $C_2 = \{v_2\}$. $v_2$ is adjacent to $v_3$ and $v_6$, so we get $C_2 = \{v_2,v_3,v_6\}$, and the next vertex to check is $v_3$, which is adjacent to $v_2$ and $v_6$, both seen. Then move to the next vertex $v_6$ and note that its adjacent to $v_2$ and $v_3$ (both seen), so we're done with this component too.
On to $C_3$, the same procedure gets us $C_3 = \{v_4,v_7,v_8\}$. All vertices $v_1$ through $v_9$ have been seen at this point so we're done, and the graph has $3$ components.
I don't know what language are you using, but in ruby it would look like this (for an input given by adjacency lists):
#!/usr/bin/ruby
# encoding: utf-8
def dfs_run(graph, visited, start)
return [] if visited[start]
visited[start] = true
output = [start]
graph[start].each do |neighbour|
output += dfs_run(graph, visited, neighbour)
end
output
end
def weakly_connected_components(input_graph)
# make the graph undirected
graph = input_graph.clone
input_graph.each do |vertex, neighbours|
neighbours.each do |n| graph[n] += [vertex] end
end
graph.each do |vertex, neighbours|
neighbours.sort!
neighbours.uniq!
end
# run dfs
output = []
visited = {}
graph.keys.each do |vertex|
output << dfs_run(graph, visited, vertex).sort unless visited[vertex]
end
# return an array of wcc
output
end
# an example
graph = {0=>[1, 2, 3, 5], 1=>[0, 2, 3], 2=>[0, 1, 3, 5], 3=>[0, 1, 2, 4, 5, 6], 4=>[0], 5=>[0, 1, 2, 3, 4, 6], 6=>[0, 2, 3, 5], 7=>[8], 8=>[0], 9=>[]}
# transformed to the following undirected graph: {0=>[1, 2, 3, 4, 5, 6, 8], 1=>[0, 2, 3, 5], 2=>[0, 1, 3, 5, 6], 3=>[0, 1, 2, 4, 5, 6], 4=>[0, 3, 5], 5=>[0, 1, 2, 3, 4, 6], 6=>[0, 2, 3, 5], 7=>[8], 8=>[0, 7], 9=>[]}
print weakly_connected_components(graph), "\n"
# outputs [[0, 1, 2, 3, 4, 5, 6, 7, 8], [9]]
Best Answer
First, you should choose an arbitrary vertex, let it be $1$ to make it simple.
Then, the algorithm starts, $1$ is "done", now we check all neighbours of $1$, and we write them to our list: $1,2,3$. (We made the edges (1,2) and (1,3)). No more neighbours, so we check for new ones. $2$ has no more neighbours, $3$ has $4$ as a neighbour, so we have $1,2,3,4$(We made edge (3,4)). After this, we have $1,2,3,4,5,6$(We made edge(4,5)(4,6)). If you start the algorithm with $1$, then this is your result.
Your spanning tree: Vertexes are $1,2,3,4,5,6$, edges are $(1,2),(1,3), (3,4), (4,5),(4,6)$.
My description was not very "professional", but hope you understand the task. :)
Here is an other example to make it clearer, from Wikipedia:
We want to make a spanning tree from Frankfurt. This is the result if you run BFS: