## Introduction to graph algorithms

#### Andy Novocin

## Register for PA2 slots

#### http://doodle.com/7kryeiwfvf9ygf7u

#### cs.prof.ninja/programs

## 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**)

## Directed/Undirected

## Weighted/Unweighted

## Dense/Sparse

## Sparse/Dense

## 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?

## cloud.sagemath.com

### 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

## Implementation

```
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;
g->degree[x]++;
if (directed==FALSE)
insert_edge(g, y, x, TRUE);
else
g->nedges++;
}
```