An Insight into Graphs - Adjacent List Representation in C
(Page 4 of 4 )
In this section, I will present the implementation of the adjacent list in some C code. The idea is to make a structure that is linked together with no memory waste; to achieve this, it will be created dynamically.
For this, we will proceed as follows. Create a new type containing an int value (the vertex to which it is linked) and a pointer to this kind of type, meaning the following: point to where this edge has a connection. For an easy update of the list, we will create a function that will have as parameters the row where we insert the item and what will be inserted.
The function should take care that no point will be added twice. Moreover, it will arrange the points in an increasing order. The list should be created dynamically with the calloc function. At the nth position will be listed to what vertexes it has edges. If NULL is present in the p_next, the list is over. If the place itself is NULL, there are no edges. Take a look at the code snippets now. First, the creation of the new type:
// A structure for the element point
struct ListIt
{
int value;
ListIt *p_next;
};
// typedef for the pointer type
typedef list * pListIt;
The add function:
// Here we need to make sure that the items are added in // correct order
bool add(pListIt &dest, int val)
{
//create the item
pListIt p;
p = (pListIt) malloc(sizeof(ListIt));
p -> value = val;
if(!dest) // first item addition
{
p -> p_next = NULL;
dest = p;
}
else
{
pListIt find = dest;
pListIt at = NULL;
// first find the first greater number, insert before
while(find && find->value <= val)
{
if( find->value == val) // do not add a duplicate
{
free(p);
return false;
}
at = find;
find = find->p_next;
}
// insert at
if (at) // insert at a valid point
{
p->p_next = at->p_next;
at->p_next = p;
}
else // insert at the start
{
p->p_next = dest;
dest = p;
}
}
return true;
}
The creation of the type after we know its size:
v = (pListIt *) calloc(n+1,sizeof(pListIt));
The read method with an edge list in the file:
for (i = 1; ; i++)
{
scanf("%d %d",&from,&to); // from -> to
if(feof(stdin))
break;
add(v[from], to);
++m;
//add(v[to], value); // directed graph or not
}
}
Moreover, we read from it the data and print it:
void print()
{
int i;
pListIt j ;
for( i = 1; i <= n; ++i)
{
j = v[i];
printf("n%d -> ", i);
while( j)
{
printf(" %d ",j->value);
j = j->p_next;
}
}
}
Now if we use a little more complicated input file with an edge list:
22
1 2
1 3
1 4
2 5
5 7
5 8
3 6
6 9
6 10
8 2
8 1
9 11
10 3
11 12
11 13
11 14
11 3
12 8
12 15
13 16
12 20
14 17
14 18
15 19
15 20
16 21
16 22
18 9
19 12
20 11
22 13
The result will be just as clear:
1 -> 2 3 4
2 -> 5
3 -> 6
4 ->
5 -> 7 8
6 -> 9 10
7 ->
8 -> 1 2
9 -> 11
10 -> 3
11 -> 3 12 13 14
12 -> 8 15 20
13 -> 16
14 -> 17 18
15 -> 19 20
16 -> 21 22
17 ->
18 -> 9
19 -> 12
20 -> 11
21 ->
22 ->
Now you can already imagine the graph (which is a tree) that the large list of the edges tries to describe. The reading in of the edges assures that you miss none of them, while our code and algorithm will make sure that the code is as optimized and efficient as it can be for a couple of algorithms.
For now I will stop here; nevertheless, I will be back soon with the Prüfer code and traveling algorithms inside graphs. Thank you for investing your time and reading until this point; with the hope that you learned a lot from this article, I invite you to comment it here on the blog or even better join our forums at DevShed or DevHardware and ask there any question you might have. Live With Passion!
| DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware. |
