Algorithms For Dummies

  Understanding Graph Basics 

     157

Graphs come in several forms. An undirected graph (as shown in Figure 8-1) is one 

in which the order of the edge entries doesn’t matter. A road map would represent 

an undirected graph in most cases because traffic can travel along the road in both 

directions.

A directed graph, like the one shown in Figure 8-2, is one in which the order of the 

edge entries does matter because the flow is from the first entry to the second. In 

this case, most people call the edges arcs to differentiate them from undirected 

entries.  Consider  a  graph  representation  of  a  traffic  light  sequence  where  Red 

equals 1, Yellow equals 2, and Green equals 3. The three arcs required to express 

the sequence are: 

Go = [Red, Green]

, 

Caution = [Green, Yellow]

, and 

Stop = 

[Yellow, Red]

. The order of the entries is important because the flow from Go, to 

Caution, to Stop is important. Imagine the chaos that would result if the signal 

light chose to ignore the directed graph nature of the sequence.

A third essential kind of graph that you must consider is the mixed graph. Think 

about the road map again. It isn’t always true that traffic flows both ways on all 

roads. When creating some maps, you must consider the presence of one-way 

streets. Consequently, you need both undirected and directed subgraphs in the 

same graph, which is what you get with a mixed graph.

Another graph type for your consideration is the weighted graph (shown in 

 Figure 8-3), which is a graph that has values assigned to each of the edges or arcs. 

Think about the road map again. Some people want to know more than simply the 

direction to travel; they also want to know how far away the next destination is or 

how much time to allocate for getting there. A weighted graph provides this sort 

of information, and you use the weights in many different ways when performing 

calculations using graphs.

FIGURE 8-1: 

Presenting a 

simple undirected 

graph.

---

158