Algorithms - Intro to Graphs

Intro to Graphs

What are graphs?

So while you might think that graphs are things like these:



..you're right! That is a graph. But when computer scientists talk about graphs, they actually mean these:



..unless they're talking about the first kind. They really should have come up with two different names for them.

Types of graphs

Graphs have nodes and edges. Looking at the diagram above, the nodes are the blue circles and the edges are the arrows connecting the nodes together.

The graph below is an undirected graph, because the edges do not have a direction.



The graph below this one is a multigraph because there is more than one edge possible between 2 nodes (it is also undirected)



The next graph is a digraph which is short for directed graph, because the edges have directions attached to them.



The next one is an edge weighted graph, because the edges have weights applied to them funnily enough.

Applications of graphs

So you're probably thinking that graphs are really nice to look at but not really useful, but you can use graphs to model a lot of things, so here's a couple of examples.

First of all is a graph used to show the distances between some places. The nodes here are the places and the (weighted) edges are the paths between them and their length. Notice how it isn't a digraph, because you can travel down a path in any direction (unless it's a one way system!)



Another example that I don't want to draw is electrical components (nodes) separated by wire (edges), but you get the point.

Dijkstra's Algorithm

(It's pronounced 'dike-stra')

This is an algorithm for finding the shortest path to visit all the nodes in a graph, you can read more on it here until we do it in lectures and I'll update this.

Graph Terminology

• Nodes are sometimes called points or vertices


• Edges are sometimes called arcs or lines


• 2 nodes linked together (by an edge) are adjacent


• On a digraph, you have a source node and a destination node depending on which way the arrow points


• On undirected graphs (undigraphs? undead graphs?) the number of edges attached to a node is the degree of the node


• On a digraph, the number of edges with the node as it's source is called the out-degree of the node, and the in-degree for nodes coming into it


• A subgraph of a graph is basically just a portion of the graph

That's all for the introduction to graphs!