An Insight into Graphs - Graphs and programming
(Page 3 of 4 )
Now that we've finished our discussion of theory, we can start with the proper programs and algorithms. However, as sad as it is, we cannot draw up the graph for coding languages, so we need to code it somehow. There exists several representation modes; each of them will be more or less adequate to a specific algorithm, and to achieve maximal efficiency we need to use the correct one.
There are around seven types of representation, however I will present only a couple of them in detail, as the rest will have little importance to the algorithms we are going to study later on.
The first and the most important one is the adjacent list, where for every vertex is enumerated all the vertexes with which it has a direct connection (though for directed graphs, only the out-going edges will be taken into account). Realizing this in code is a little more complicated, so I have allocated it to it the next page.
The edge list is the enumeration of the edges with the syntax from node to node. This can be easily made with a matrix of 2 X m(number of edges). This is the one used most of the time when you read in the graph, as it makes it easy to add and remove edges.
The adjacent matrix will have n columns and n rows, where at the i-th row and j-th column will be:
---> k if there exists k number of edges between "i" and "j" if "i" is not equal with "j".
---> h if, there exists h number of loop edges if "i" equal "j".
---> 0 if there exists no edge between "i" and "j".
Furthermore, there exists the circle matrix representation, the incidence matrix or the cut matrix; however, I will not discuss these as they are too rarely used; search for them on the Internet if you are interested. The last one will be the representation of trees.
This is done most of the time with a single array of n, where the "i"-th place will be the number of its ancient. The root item will be -1 or 0 depending on implementation. This way we can even determine the road from the root to a leaf by applying recursive calls to this array.
Next: Adjacent List Representation in C >>
More Code Examples Articles
More By Gabor Bernat
