-
Notifications
You must be signed in to change notification settings - Fork 0
Home
Information on a Basic Map Navigation Program
A fundamental understanding of graphs and graph theory was acquired through reliable sources such as this article on Graph Theory and a more mathematically inclined view on graphs (discrete mathematics) was obtained from this source.
Different methods for storing graph data can be utilized, with the selection often influenced by the number of nodes involved. While edges depend on the number of nodes, nodes are intrinsically linked to the edges. For instance, in the case of non-directed edges, the number of potential edges ranges from 0 to (n(n-1))/2, while for directed edges, it ranges from 0 to n(n-1), where n represents the number of nodes. Therefore, nodes can be efficiently stored in a linear array. However, determining the appropriate storage mechanism for edges requires careful consideration.
1. Edge list
One commonly employed approach is the utilization of an edge list, which involves storing each edge in a list denoted by v = [(a1, b1, c1), (a2, b2, c2), ...] where a denotes the start node, b denotes the end node, and c denotes the weight carried by the edge. The advantage of this method lies in its minimal memory footprint. Nevertheless, its time-cost operation is significantly higher, as the entire list must be traversed to identify connected nodes.
Another prevalent method for storing edge data is through the use of an adjacency matrix, represented as a 2D matrix. Detailed information regarding the array's configuration can be found in the adjacency matrix link provided. The time-cost operation is highly optimized since there is no need to search an array to verify the existence of an edge or determine its weight. The position of the edge in the array can be identified as A[node1][node2]. However, it should be noted that this approach requires a substantial amount of memory to store the data. The memory size increases in a parabolic fashion as the number of nodes grows. As more nodes are added, the edge population may become sparser, rendering the adjacency matrix less space-efficient when compared to an edge list.
The adjacency list method represents a balanced compromise between the two aforementioned techniques. An illustrative example of this data structure can be found by following the provided link. Although it may not excel in terms of time-cost operations or memory efficiency, the adjacency list offers a satisfactory trade-off, particularly when dealing with moderately populated or non-densely populated edges.
/Information to come/