Check if a pair of vertices have common neighbor
  • Posted: 5 years ago
  • Edit
  • answers (1)
  • views (2351)

Write a function to determine if a given pair of vertices have a common neighbor.


Posted Answers

Two vertices \( A \) and \( B \) have a common neighbor if for some vertex \( C \), the graph contains edge between (\( A \) and \( C \)) and (\( B \) and \( C \)).

public boolean haveCommonNeighbor(String s1, String s2){

int i1 = getIndex(s1);
int i2 = getIndex(s2);

for(int i = 0; i < numVertices; i++){
/* Check if i is a neighbor of both i1 and i2 */
boolean ch1 = false;
boolean ch2 = false;

if(i < = i1)
ch1 = Edges[i1][i];
else
ch1 = Edges[i][i1];

if(i < = i2)
ch2 = Edges[i2][i];
else
ch2 = Edges[i][i2];

return (ch1 & & ch2);
}
return false;
}

You need to Sign In to post your solution.