Graph Basics

Document last modified: 

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

Undirected

V = {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)}

 

Directed

V = {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)

Degree - has to do with the number of edges incident on a vertex

Path

Cycles

Connected

 

Operations

What operations might we want to do on a graph? Here are some common ones:

Representation

Given graph G = (V, E).

• May be either directed or undirected.
• Two common ways to represent for algorithms:

  1. Adjacency lists.

  2. Adjacency matrix.

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—we’ll drop the cardinality.

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

Adjacency lists

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

Vertex u’s list has all vertices v such that (u, v) Î E. (Works 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

We’ll use weights later on for spanning trees and shortest paths.

Performance:

Example: For a directed graph:

Adjacency matrix

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

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

Performance:

Example - 4 × 4 matrix

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 edge is missing for vertex 5?

 

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

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.

add_edge is just inserting a node into the linked list: 

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;
}
adjacent_to 
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.