# Graph Basics

G = (V, E)

V - finite set called the vertex set whose elements are called vertices
E - is a binary relation on V called the edge set, whose elements are called edges

Examples

 UndirectedV = {1, 2, 3, 4, 5} E = {(1,2)(2,1)(1,5)(5,1)(2,5)(5,2)(4,2)(2,4)(4,5)(5,4)(4,3)(3,4)(2,3)(3,2)} DirectedV = {1, 2, 3, 4} E = {(1,2)(2,4)(3,1)(3,2)(4,3)(4,4)}

Directed Graph

The ordered pairs in E represent the direction of the edge, i.e., (tail, head) tail is source vertex and head is the target vertex

Undirected Graph

The pairs in E are unordered pairs, i.e., there is no tail or head and there is no direction to the edge, e.g., (u, v) ∈ E is really the same edge as (v, u)

Adjacent Vertices - means there is an edge from u to v, i.e., (u, v), page 1169.

• undirected graph - (u, v) means v is adjacent to u, and vice versa.

• Example: (2, 3) and (3, 2) are adjacent.

• directed graph - (u, v) means v is adjacent to u, but unless there is an edge (v, u), then u is not adjacent to v.

• Note that this is the opposite of definitions used by most other authors but the distinction can generally be ignored in the algorithms presented in the text.

• Example: (3, 2) means 2 is adjacent to 3 but 3 is not adjacent to 2.

• adjacent vertices are said to be neighbors.

Degree - the number of edges incident on a vertex

• undirected graph - the degree equals the number of edges incident on a vertex.

• Example: vertex 2 has degree 4.

• directed graph:

• in-degree - equals the number of edges who have their head at a vertex, or targeting the vertex

• Example: vertex 2 has in-degree 2.

• out-degree - equals the number of edges emanating from the vertex.

• Example: vertex 2 has out-degree 1.

Path

• Of length k from u to u' in G = (V, E) is a sequence of vertices < v0, v1, ..., vk > where u = v0 and u' = vk, and (vi -1, vi) ∈ E, for i = 1, 2, ..., k

• |P| = Path Length - equals the number of edges in the path

• There is always a 0-length path from u to u

• Reachable - given u and u', u' is reachable from u if there exists a path P from u to u'

• written as u u' for a directed graph

• 1 4 for directed graph at right

Question 22.1 for the directed graph at right

1. Is 1 adjacent to 2?

2. Is 2 1?

3. Is x y  for all x, y ∈ V

4. Is the Web a directed or undirected graph?

5. What does in-degree and out-degree correspond to on the Web?

6. Is x y  for all x, y ∈ V where V is all Web pages?

Cycles

• In Directed Graphs:

• a cycle path (circuit) is a path < v0, v1, ..., vk > such that v0 = vk and |P| ≥ 1

• a simple cycle is when v0, v1, ..., vk in P are distinct, does not contain the same edge more than once.

• a self loop is a cycle of length 1, and a directed graph with no self loops is referred to as simple

• Directed Acyclic Graphs (DAG) - a directed graph with no cycles (circuits)

• In Undirected Graphs:

• a simple cycle is when v0, v1, ..., vk in P are distinct and |P| ≥ 3

(1,2,1) is not a simple cycle.

• Undirected Acyclic Graph - an undirected graph with no simple cycles (circuits)

• Same Cycle - two cycles < v0, v1, ..., vk > and < v'0, v'1, ..., v'k > are the same cycle when there exists an integer j, such that v'i = v'(i = j) mod k for i = 0, .., k - 1

Question 22.2 for the directed graph at right

1. Give one cycle.

2. Is the graph a DAG?

3. Give an example of a DAG.

Connected

• undirected graph

• connected  - when every pair of vertices in V is connected by a path. The graph below has 3 components, it is not a connected graph.

• connected components - if the graph is not connected, then it has connected components where each of these connected components are made up of a subset of vertices from V, and each component is connected

• directed graph

• strongly connected - when every two of vertices in V is reachable from each other

• strongly connected components - if the directed graph is not strongly connected, then it has strongly connected components where each of these strongly connected components are made up of a subset of vertices from V, and each component is strongly connected

• weakly connected - when the underlying undirected graph is connected; a strongly connected directed graph is also weakly connected.

Question 22.3

• Is the graph at right strongly connected?

• Is a binary search tree strongly connected?

• Is a binary search tree weakly connected?

## Operations

What operations might we want to do on a graph? Here are some common ones:
• create (G) - create a graph G.

• add_edge (G, a, b) - add the edge (a, b) to G.

• outdegree (G, a) - return the out-degree of vertex a.

• indegree (G, a) - return the in-degree of vertex a.

• adjacent_to (G, a, b) - return true if a is adjacent to b.

• forall_adjacent_to (G, a, f) - apply the function f to all vertices adjacent to a. Usually implemented as an iterative loop doing something for each vertex adjacent to a.

• forall_path_to (G, a, f) - apply the function f to all vertices reachable from a by some path. Traditionally called "searching" the graph starting from some vertex.

Representation

Given graph G = (V, E).

• May be either directed or undirected.

• Two common ways to represent for algorithms:

When expressing the running time of an algorithm, it's often in terms of both |V| and |E|.

In asymptotic notation — and only in asymptotic notation — drop the cardinality.

Example: O(V + E) rather than O(|V| + |E|).

Array Adj of |V| lists, one array entry per vertex.

Vertex u's list has all vertices v such that (u, v) ∈ E (for both directed and undirected graphs)

C++ representation

 typedef struct node { int to, from; struct node *next; } edgenode, *graph;

Example: For an undirected graph:

If edges have weights, can put the weights in the lists.

Weight: w : E → R

Use weights for spanning trees and shortest paths.

Performance:

• Space: Θ(V + E).

• Time: to access all vertices adjacent to u: Θ(degree(u)).

• Time: to determine if (u, v) ∈ E: O(degree(u)).

Example: For a directed graph:

|V| × |V| matrix A = (ai j ) where i is row, j is column

ai j = 1 if( i, j ) ∈ E
= 0 otherwise

Performance:

• Space: Θ(V2), independent of |E|

• Time: to access all vertices adjacent to u: Θ(V).

• Time: to determine if (u, v) ∈ E: Θ(1).

• Can store weights instead of bits for weighted graph.

Example - 4 × 4 matrix

• Directed graph

V={1,2,3,4}

|V| is 4

E={(1,2) (2,4) (3,1) (3,2) (4,3) (4,4)}

|E| is 6

(1, 2) ∈ E

(3, 1) ∈ E

Out-degree of vertex 3 = 2 or (3,1) and (3,2)

In-degree of vertex 2 = 2 or (3,2) and (1,2)

Question 22.4 - 5 ×5 matrix

1. Directed or undirected graph? How do you know?

2. V?

3. |V|?

4. E?

5. |E|?

6. (1, 2) ∈ E?

7. (2, 1) ∈ E?

8. Out-degree of vertex 4?

9. In-degree of vertex 2?

10. Which edges are missing on vertex 5 for the graph and matrix to agree?

OPERATIONS

Many of the graph operations take time linear in the size of E, i.e., O(|E|).

We know from trees and hash tables that we can probably do better.

Question 22.5

• Suggest an algorithm to search a directed graph for a strongly connected graph (every vertex is reachable).

• What problem must be handled on the directed graph at right?

• How might the problem be resolved?

• What would you guess the worst case performance for an algorithm searching for a vertex in the directed graph? Consider searching for 5 in the lower-right graph.

• What would you guess the worst case performance of the algorithm for determining a strongly connected graph? Consider the upper-right graph.

Representation in C called an edge list, a linked list of edges. A node is:

 typedef struct node { int to, from; struct node *next; } edgenode, *graph;
Create the graph is just setting a pointer equal to NULL.

```void add_edge (graph *G, int a, int b) {
edgenode	*p;

p = malloc (sizeof (edgenode));
p->to = b;
p->from = a;
p->next = *G;
*G = p;
}```
```int adjacent_to (graph G, int a, int b) {
edgenode	*p;
for (p=G; p; p=p->next)
if (p->from == a && p->to == b) return true;
return false;
}
```
outdegree
```int outdegree (graph G, int a) {
edgenode	*p;
int		count;

count = 0;
for (p=G; p; p=p->next)
if (p->from == a) count++;
return count;
}
```

forall_adjacent_to We could do something like this:

```void something (graph G, int a) {
edgenode	*p;

for (p=G; p; p=p->next) {
if (p->from == a) {
/* do something */
}
}
}
```
forall_path_to  For instance, maybe we want to print out every vertex reachable from a given vertex. This is a nontrivial task. A first try would be something like this:
```/* this is wrong! */
void search (graph G, int a) {
for (p=G; p; p=p->next) {
if (p->from == a) {
printf ("%i\n", p->to);
search (G, p->to);
}
}
}```
But this will get us into trouble if there are cycles in the graph; it will just keep going around and around forever.

Need to think of something better.

Later on, will see Depth First Search and Breadth First Search: two ways of dealing with this.