Fastest way to find all neighbours of a vertex in a graph I'm looking for the fastest way to find all neighbours of a vertex in an undirected Graph.  Please improve on the code if possible.

neighbours[g_Graph, v_] :=
 Module[
  {vl = VertexList[g],
   pos},
  pos = Position[vl, v][[1, 1]];
  Pick[VertexList[g], AdjacencyMatrix[g][[pos]], 1]
 ]


I need it to work fast both for sparse and dense graphs.


It is essential to the performance of this solution that it uses SparseArrays.
This is a bottleneck in my application.  Since my graph is constantly changing, trying to precompute neighbours or using memoization will complicate things significantly.


I'd like to stress that speed is essential here.  Here's a graph to test on:

max = 4000;
c = 0.3;

tg = RandomGraph[{max, Round[c max^2]}];

neighbours[tg, 1]; // Timing
As of Mathematica 9.0 we have the function AdjacencyList[g,v].
Since this is built into Mathematica, I would assume that it is the fastest implementation.

In[1]:= g = CompleteGraph[7];
In[2]:= AdjacencyList[g, 4]
Out[2]= {1, 2, 3, 5, 6, 7}
In[3]:= g = CompleteGraph[{3,4}];
In[4]:= EdgeList[g]
Out[4]= {1 &lt;-&gt; 4, 1 &lt;-&gt; 5, 1 &lt;-&gt; 6, 1 &lt;-&gt; 7, 2 &lt;-&gt; 4, 2 &lt;-&gt; 5, 2 &lt;-&gt; 6, 2 &lt;-&gt; 7, 3 &lt;-&gt; 4, 3 &lt;-&gt; 5, 3 &lt;-&gt; 6, 3 &lt;-&gt; 7}
In[5]:= AdjacencyList[g, 5]
Out[5]= {1, 2, 3}