Throw away everything you learned in math and science about graphs, because graphs in computer science are completely different.

(Except don't actually throw them away. Traditional graphs can be helpful for answering the important questions.)

Instead of talking about those pesky x and y values, we'll be putting values into nodes and edges. Nodes are the objects we'll be dealing with and edges show how they're connected. Say you're using a graph to show relationships between people. The nodes would be the people themselves (like you, your friends, and Kevin Bacon) and the edges would be how you all know each other (yes, even Kevin Bacon).

Draw out the graph, and you'll see connections between people you didn't even realize. Sounds like great networking material, eh?

Graphs represent connections—edges—between things—nodes, also known as vertices. And they can represent just about anything. You can even have two edges going between the same two nodes if that's how you want to show different relationships. If you can find a number of steps that takes you from one node to another, you've found a path.

You have to be careful, though, because sometimes graphs can cause you to begin where you started (called a loop). That can be good for certain problems, but other times loops can cause problems with running something endlessly.

A graph is only as strong as its number of connected vertices. If a graph has any vertices that aren't connected to anything else (that means they have no edges), the graph's considered disconnected. A discrete graph is disconnected to the extreme: all of its nodes are unreachable by every other node. If a graph has no disconnected vertices, then it's called—wait for it—connected.

Like we said before, a path is a way to reach one node from another node. It's just a group of edges that give all the steps from leaving one node—like You—and reaching another—the amazing Kevin Bacon. On the path to Kevin Bacon, you could go:

• You→Best Friend→Best Friend's Second Cousin, Twice Removed→KB
• You→Dad→KB
• You→Mom→Best Friend's Second Cousin, Twice Removed→KB

Each path's going to bring you to the exact same place, they just go through different nodes to get there.

Undirected Graphs

When you plan for a trip or vacation, you'll usually assume that there'll be a way get back home from your destination. Most planes/trains/automobiles are going to sell two-way tickets that send you both to your vacation and back home after it's over. If not…you'd go from tourist to squatter pretty quickly. Unless you get creative.

Enter: the undirected graph. An undirected graph is one that lets you go from one node to the other and from the other node to the one. Confused? Look back up at the graph showing how far away you are from Kevin Bacon. You can reach your best friend because…you're their best friend too. That relationship is equal from both directions. If we were to make a graph of all your best friends (because it's a level, duh), then that would be an undirected graph. If you can go from node A to B, then you can also go back from node B to A.

Compare that to…

Directed Graphs

Back before they took our license away, Shmoop was a great driver. Even so, every driver makes innocent mistakes like

• forgetting to turn on your lights at dusk.
• accidentally running a red when you think you can make the light.
• driving the wrong way down a one-way street because you're late to a birthday party and just don't have time for that kind of thing.

No? Just us?

One-way streets are just like directed graphs. (Also, we're pretty sure they're why Google Maps was invented.) Just because you can head one direction on them doesn't mean you can head the other way. In fact, for your safety, it's probably better that you don't try to go the other way.

In a directed graph, heading from Node A to Node B doesn't mean you can head from Node B to Node A. Sometimes you can, but not always. When you can go both directions, that edge is called bidirectional. When you can only go one direction, it's called unidirectional.

When you have a unidirectional graph, you need to know how many ways you can get into each node, and how many ways you can get out. The first one's called the in-degree (…because it's the degree number of how to get into a node) and the opposite's called—wait for it—the out-degree. One node's in-node is another's out-node. Bet you didn't see that one coming.

None of this terminology matters for bidirectional graphs, though, since a node's in-degree is also its out-degree. Instead, you'll only care about the degree of the vertex (which is just how many edges it has).

Cycles

Say you have a series of nodes that start at a node and end at that same node. The path begins and ends at the same place. You've just found a cycle, which can be either good or bad. All graphs can have nodes—whether directed or undirected—but if the entire graph's a cycle, it's called a cycle graph .

Graphs: not too hard, but also filled with boring names. If we were in charge of names, in-degree would be named

• the road to the vertex.
• the number of licks it takes to get to the center of a vertex.
• how many ways can you skin a vertex.

In retrospect, it's probably better that we didn't get to name graph theory things.

Weighted Graphs

You know how they say that the best things in life are free? Unless you're a freegan hippie living in a commune on the arctic tundra of Nunavut, that probably isn't completely true. (If you are, how do you find enough waste to live off of in Nunavut? We're curious.)

For everyone not surviving on free love and caribou meat, there's a price to pay for just about everything in life. Even graphs aren't always free to roam. Weighted graphs have a cost at every edge. Sometimes that equals money, but most of the time it's talking about, well…time.

Ever heard of a little thing called Google Maps? It uses weighted graphs to figure out which path is going to take the least amount of time. It's pretty helpful.