in grpah what will be the fastest way to find all the nodes connected to one node but not connected to another node.?

Say you have two nodes P and Q. Now we have to find the nodes having edge with Q but not with 开发者_开发技巧P. What is the fastest way to do this? What algorithm or data structure should I use? Currently whenever adding an edge I am maintaining a vector with each node which saves all the nodes connected to that node (Lets call this Vi for ith node). Also I am having adjacency matrix. Roughly something like this I am doing.

for each node in Vq

check if it is connected to P using adjacency matrix

do something with this node

Do you think anything faster can be done here?

Almost the same thing:

• Take the P row and the Q row from the adjacency matrix
• For node I,
  • if the I'th column has a 0 in the P row and a 1 in the Q row, do operation.

This is being explicit about not having another loop inside the for loop for "checking if it is connected".

That's the fastest you can do theoretically (this is O(n) and the theoretical lowerbound is O(n)). In practice, you might be able to optimize it depending on what language you're using and what it's optimized to do. For example Matlab would love it if you phrased it as:

nodes = (~rowP)*rowQ';

Correct me if I'm wrong, but it should run no faster than linear time. Every node must be checked, but the existence of an edge is verified in constant time.