How to test if a graph is fully connected and finding isolated graphs from an adjacency matrix

I have large sparse adjacency matrices that may or maybe not be fully connected. I would like to find out if a matrix is fully connected or not and if it is, which groups of nodes belong to a group/cluster. I have an example matrix:

matnew =
 0     1     1     0     0     0     0
 1     0     0     0     0     0     0
 1     0     0     1     0     0     0
 0     0     0     0     0     0     0
 0     0     0     0     0     1     1
 0     0     0     0     1     0     0
 0     0     0     0     0     1     0

There are bi-directional edges and directed edges which belong to 2 separate clusters: $1\leftrightarrow 2$, $1\leftrightarrow 3$, $3\rightarrow 4$, and in the next cluster $5\leftrightarrow 6$, $5\rightarrow 7$, $7\rightarrow 6$.

The first approach is to use a function to calculate the paths between nodes

>> floyd_warshall_all_sp(sparse(matnew))
ans =
 0     1     1     2   Inf   Inf   Inf
 1     0     2     3   Inf   Inf   Inf
 1     2     0     1   Inf   Inf   Inf
Inf   Inf   Inf     0   Inf   Inf   Inf
Inf   Inf   Inf   Inf     0     1     1
Inf   Inf   Inf   Inf     1     0     2
Inf   Inf   Inf   Inf     2     1     0

That works great by looking off the diagonal for Inf and then clustering, but my matrices are in the size of thousands of nodes and it is slow (too slow for my needs). Is there a method/algorithm which just checks connectivity?*

I thought about checking the walk lengths as an approximation, but to be certain I would have to guess that they are not more than a number of jumps eg 10. Which may be reasonable but even then doing the matrix multiplication of a 1000x1000 many times is not so great for an approximation.

>> (matnew^1)+(matnew^2)+(matnew^3)+(matnew^4)+(matnew)^5
ans =
 6     7     7     3     0     0     0
 7     3     3     3     0     0     0
 7     3     3     4     0     0     0
 0     0     0     0     0     0     0
 0     0     0     0     5     7     4
 0     0     0     0     4     5     3
 0     0     0     0     3     4     2

But it does reveal quite a bit about the connectivity.

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]]

The second smallest eigenvector (Fiedler vector) of the Laplacian can be used to reveal information about the number of disconnected components.