|
271. Design a compact data structure representation of a graph
Microsoft Interview Questions and Answers
(Continued from previous question...)
271. Design a compact data structure representation of a graph
Question:
Design a compact data structure representation of a graph
maybe an answer:
If the graph is not dense (i.e., E is small as compared to V) then you can have a linked list of all the vertices that are connected to any given vertex. If it's dense then you can use a matrix representation where M[i, j] = 1 means there is an edge from Vi to Vj. Following is a compact representation for "undirected" graph:
unsigned char * CreateUndirectedGraph(unsigned int vertices)
{
unsigned char *mem = NULL;
if(vertices > 0)
{
vertices = (vertices*(vertices + 1))/2;
unsigned int count = 0;
count = vertices >> 3;
if(vertices & 0x00000007)
{
count++;
}
mem = new unsigned char[count];
for(int i=0;i<count;i++)
*(mem + i) = 0;
}
return mem;
}
void SetEdge(unsigned int v1, unsigned int v2, bool value, unsigned char *mem)
{
if(mem != NULL)
{
if(v1 < v2)
{
unsigned int t = v1;
v1=v2;
v2=t;
}
unsigned int pos = (v1*(v1+1))/2 + v2;
unsigned int bytenum = pos >> 3;
unsigned char mask = ((unsigned char)1 << ((pos & 0x00000007) - 1));
if(value)
{
mem[bytenum] |= mask;
}
else
{
mem[bytenum] &= ~mask;
}
}
}
(Continued on next question...)
Other Interview Questions
| 