In a broader context, a graph is a symbolic representation of a network, and
while the nodes and edges may represent a spatial relationship, such as the
example previously discussed, this doesn’t have to be the case. Graphs can
be used to represent networks of any kind, from telephone networks and
the World Wide Web to electronic circuits and artificial neural networks.
Ü
NOTE Graphs can be either connected or unconnected. A graph is consid
-
ered to be connected when it’s possible to trace a path from every single node
to every other.
Graphs A, B, D, and E in Figure 5.3 are examples of connected graphs.
Graphs C and F are examples of unconnected graphs.
A More Formal Description
A graph, G, can be formally defined as the set of nodes or vertices, N, link
-
ing with the set of edges, E. You will often find this written as:
(5.1)
If each node in a graph is labeled with an integer in the range 0 to (N-1), an
edge can now be referred to by the nodes it connects, for example 3-5 or
19-7.
Many graphs have edges that are weighted — they contain information
about the cost of moving from one node to another. For example, in the
graph shown in Figure 5.2, the cost of traversing an edge is the distance
between the two nodes it connects. In a graph representing the tech-tree for
The Secret Life of Graphs | 195
Graphs
Figure 5.3. Examples of graphs
{}
,GNE=

Get Programming Game AI by Example now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.