O'Reilly logo

Programming Game AI by Example by Mat Buckland

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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=

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required