# Faster way to check connectivity from adjacency matrix

I have an adjacency matrix, A. I want to check if there is a path (from any vertex) which can traverse all of the vertices such that no vertex is visited again.

A = {{0, 0, 0, 1, 1, 0, 0, 0, 0}, {0, 0, 0, 1, 1, 1, 0, 0, 0}, {0, 0, 0,
0, 1, 1, 0, 0, 0}, {1, 1, 0, 0, 0, 0, 1, 0, 0}, {1, 1, 1, 0, 0, 0,
1, 0, 1}, {0, 1, 1, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 1, 1, 0, 0, 1,
0}, {0, 0, 0, 0, 0, 0, 1, 0, 1}, {0, 0, 0, 0, 1, 1, 0, 1, 0}};


I solved this by constructing an AdjancencyGraph and then using FindPath for all of the vertices to check if any path exists.

getPathsFromNode[adjMatrix_, node_] :=
Flatten[#, 1]&@


Now, I check if there is any path from any vertex.

(getPathsFromNode[A, #]!={}) & /@ Range[9] // Flatten[#, 1] &
(*{True, True, True, False, False, False, True, False, True}*)


This process is very slow. Is there any other way to check if a path exits without contructing an Adjacency graph?

• Have you seen FindHamiltonianCycle[]? Apr 8, 2017 at 5:22
• @J.M. I tried FindHamiltonianCycle[A // AdjacencyGraph], It returns empty list. Apr 8, 2017 at 5:27
• Use FindHamiltonianPath Apr 8, 2017 at 7:31
• @Szabolcs Thanks. The speed has increased by an order. Apr 8, 2017 at 7:39
• Szabolcs suggestion is probably the best method to use (for general $A$). Are there any restrictions on the graph/matrix? Apr 9, 2017 at 7:32

This is the Hamiltonian path problem. Use FindHamiltonianPath.