Application in Computer Science
| The graph pictured above has this adjacency list representation: | ||
| a | adjacent to | b,c |
| b | adjacent to | a,c |
| c | adjacent to | a,b |
In computer science, an adjacency list is a data structure for representing graphs. In an adjacency list representation, we keep, for each vertex in the graph, a list of all other vertices which it has an edge to (that vertex's "adjacency list"). For instance, the representation suggested by van Rossum, in which a hash table is used to associate each vertex with an array of adjacent vertices, can be seen as an example of this type of representation. Another example is the representation in Cormen et al. in which an array indexed by vertex numbers points to a singly linked list of the neighbors of each vertex.
One difficulty with the adjacency list structure is that it has no obvious place to store data associated with the edges of a graph, such as the lengths or costs of the edges. To remedy this, some texts, such as that of Goodrich and Tamassia, advocate a more object oriented variant of the adjacency list structure, sometimes called an incidence list, which stores for each vertex a list of objects representing the edges incident to that vertex. To complete the structure, each edge must point back to the two vertices forming its endpoints. The extra edge objects in this version of the adjacency list cause it to use more memory than the version in which adjacent vertices are listed directly, but these extra edges are also a convenient location to store additional information about each edge (e.g. their length).
Read more about this topic: Adjacency List
Famous quotes containing the words application, computer and/or science:
“It is known that Whistler when asked how long it took him to paint one of his “nocturnes” answered: “All of my life.” With the same rigor he could have said that all of the centuries that preceded the moment when he painted were necessary. From that correct application of the law of causality it follows that the slightest event presupposes the inconceivable universe and, conversely, that the universe needs even the slightest of events.”
—Jorge Luis Borges (1899–1986)
“What, then, is the basic difference between today’s computer and an intelligent being? It is that the computer can be made to see but not to perceive. What matters here is not that the computer is without consciousness but that thus far it is incapable of the spontaneous grasp of pattern—a capacity essential to perception and intelligence.”
—Rudolf Arnheim (b. 1904)
“Nothing matters but the facts. Without them, the science of criminal investigation is nothing more than a guessing game.”
—Blake Edwards (b. 1922)