Connecting nodes in a graph in Java

Making QR Code in Java Connecting nodes in a graph

Another use for graphs involves topological graph theory This problem is highlighted by the Three Cottage problem with three cottages needing to connect to the gas, water, and electricity companies, but their lines can t cross each other (It s impossible, by the way) Connecting lines in a graph without crossing is a problem that circuit board designers face in the placement of chips Another example of eliminating intersections involves transportation designs, such as the design of highways or railroad tracks

Graphs typically represent a chaotic arrangement of data with little or no structure To give graphs some form of organization, computer scientists have created special graphs dubbed trees Like a graph, a tree consists of nodes and edges, but unlike a graph, a tree organizes data in a hierarchy, as shown in Figure 5-5 A tree arranges a graph in a hierarchy with a single node appearing at the top (or the root node) and additional nodes appearing connected underneath (or internal nodes) If a node has no additional nodes connected underneath, those nodes are leaf nodes, as shown in Figure 5-6

A tree can store information at random in its different nodes, which is dubbed an unordered tree However, the tree is already in the form of a hierarchy, so it only makes sense to take advantage of this built-in structure and create an ordered tree An ordered tree provides a distinct beginning node (the root node) with additional nodes organized in a hierarchy Such a hierarchy can store and show relationships of a corporate management team or the spread of a flu epidemic through different cities As a result, ordered trees are a common data structure used to both model and organize data One common use for ordered trees involves storing data Under each root node, you can have 26 internal nodes that each represent a single letter of the alphabet from A to Z Under each of these letter nodes, you can have multiple nodes that contain the actual data, as shown in Figure 5-7

To save the name David Bally, the computer stores the name under the B node To save the name John Burkins, the computer also stores this name under the B node To determine whether to store this new name before or after any existing data, the computer examines the data and sorts it alphabetically In this way, the tree data structure not only stores data, but sorts and organizes it as well If you had a long list of names stored in an array or a collection, finding a name would require searching through the entire array or collection However, if that same list of names is stored in a tree, a name would be much simpler to find because you d only need to look at the first letter of a person s last name to find where it might be stored So if you want to find the name John Bally, start at the B node and ignore any data stored under the other nodes This makes searching and retrieving data much faster than other types of data structures, which is why trees are so commonly used in databases

A variation of an ordered tree is a binary tree Unlike an ordinary tree, every node in a binary tree has at the most two nodes connected underneath To sort data, the left node contains values less than its parent node whereas the right node contains values greater than its parent node, as shown in Figure 5-8 By limiting each node to a maximum of two connected nodes, binary trees make searching and sorting data fast and efficient