Introduction to graph algorithms

Andy Novocin

Register for PA2 slots

A new type of challenge

The UDel ACM sends out a challenge problem in their weekly email. Here is this week's:

An ascending number is a natural number in which every digit is strictly less than the next digit. What is the sum of all base 16 ascending numbers? Give your answer in base 16. For example, 123, 12358D, 6AE are all ascending numbers base 16.

To sign up for the weekly challenges visit this link (click subscribe).

To submit your solution visit THIS link.

Are these two graphs the same?

Official Graph Definition

A graph is a set of vertices \(V\) and a set of edges \(E\).

If \(v_1\) connects to \(v_2\) then \( (v_1, v_2) \in E \).

Complexities of graph algorithms will typically involve two parameters: \(|V|\) and \(|E|\).

Adjacency Matrix

Our first method of storing a graph in a computer is the adjacency matrix

Create a matrix (array of arrays) with one row and column per vertex.

If an edge exists from \(v_i\) to \(v_j\) then: put a 1 at entry \(i,j\)

Adjacency Matrix p2

\( \left(\begin{array}{rrrrr} 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \end{array}\right) \)

In Class Understanding Problem 1:

Create the adjacency matrix of a complete binary tree with 7 nodes (number them as if they were in a heap).

Sage advice

Don't design a graph algorithm, design a graph from your problem as the algorithm.

Sock Dye

Knuth's Word Games

“gimlets”, “giblets”, “gibbets”, “gibbers”, “libbers”, “limbers”, “lumbers”, “cumbers”, “cambers”, “campers”, “carpers”, “carters”, “barters”, “batters”, “butters”, “putters”, “puttees”, “putties”, “patties”, “parties”, “parries”, “carries”, “carrier”, “currier”, “curlier”, “burlier”, “bullier”, “bullies”, “bellies”, “jellies”, “jollies”, “collies”, “collins”, “colling”, “coaling”, “coaming”, “foaming”, “flaming”, “flaking”, “fluking”, “fluxing”, “flexing”, “fleeing”, “freeing”, “treeing”, “theeing”

Additional Terms

The degree of a vertex is the number of edges eminating from there.

(For directed graphs there is in-degree and out-degree)





In class problem 2:

Consider the following sentence made from 10 letters:

Situation, sir. A neutron star is not neutral!

Create a directed graph of the ten (scrabble one point) letters such that edge exists from \(x \to y\) only if \( y\) follows \(x\) in the sentence.

The weight of an edge can be the number of times it happens in the sentence.

Find a path through all letters which doesn't repeat.

Can you find two letters such that no path of length \(\leq 4\) can connect them?

For solving and playing with graphs.

Please sign up tonight.

Graph data structures

If I have \(n\) vertices then an adjacency matrix has \(\mathcal{O}(n^2)\) entries.

If the graph is sparse then most of these entries are zero.

A sparse solution

An adjacency list

Concept: create an array of vertices each of which has a "next" property storing a pointer to a vertex along an edge.

Thus each vertex has a linked list of "edge partners".

(My preferred solution is to use "sparse linear algebra", ask me for details.)

Adjacency List


insert_edge(graph *g, int x, int y, bool directed){
  edgenode *p;
  p = malloc(sizeof(edgenode));
  p->weight = NULL;
  p->y = y;
  p->next = g->edges[x];
  g->edges[x] = p;
  if (directed==FALSE)
    insert_edge(g, y, x, TRUE);

In class problem 3

Which structure is better adjacency matrix or adjacency list for:

Testing if edge \((x,y)\) is in the graph?

Finding degree of a vertex?

Storage on small graphs?

Inserting an edge?

Deleting an edge?

Traversing the graph?

Goal: cycle, use each vertex once