**ICOM 4035 – Data Structures**

**Spring 2008**

**Laboratory 12: Graphs**

**1.
****Objectives**

- Understand the Graph data structure.
- Study the properties of a Graph.
- View some applications of the Graph.
- Implement some Graphs traversals.

**2.
****Overview**

Like a tree, a graph is a non-linear data structure which
provides the ability to model complex systems. We define a graph G as {V, E} a
collection of **vertices** and **edges**. A **vertex** is an end node in the graph, while the **edges** are lines connecting two vertices together. In figure 1 G =
{{A, C, S, P, M}, {(A, C), (C, S), (P, S). (A, P), (M, M)}}. This graph is **undirected** which means that the edges
have no direction, in other words (A, C) = (C, A). When a graph is directed we
can only travel an edge (V1, V2) from its **source**
V1 (outgoing) to its **destination** V2
(incoming).

Figure 1

A vertex v has a **degree**
d defined as the number of incidents of v. An **incidence** of v is an occurrence of v in either the source or the
destination of an edge. We can have incidence that takes into account all occurrences
of v, outgoing incidence taking only the times that v is the source of an edge
and incoming incidence where v is the destination of an edge. Deg(v) = Odeg(v)
+ Ideg(v). If v1 and v2 share an edge they are **adjacent** to each other.

Graphs can also be weighted, where the edges are weighted
according to the value of the element stored in it (figure 2). Such graphs are
useful to computing optimal paths from a source vertex to a destination vertex.
A **path** is a collection of edges that
connect some vertex v1 with another v2. If all vertices have a path to each
other then the graph is said to be **connected**.
If a graph is not connected it can still
be separated into sub-graphs which can be connected, these are called the
strongly connected components of G.

Figure 2

A **spanning tree**
is a root free tree that is composed of all the vertices G but has no cycles in
it. If G is not connected then we get **forests**
instead of a spanning tree.

Finally a graph also has traversals that allow us to run through the graph and determine its properties. The most common are the Depth First Search (DFS) and the Breadth First Search (BFS).

DFS:

1) Start at a vertex v.

2) Visit v and pass to one of its adjacent (non-visited) vertices and make it v.

3) Repeat 2 until you have visited all the vertices in G. If you reach dead end, backtrack until you have a vertex with non-visited neighbors.

BFS:

1) Start at a vertex v.

2) Make a variable hop = 1 and visit all adjacent vertices that you can reach in 1 edge.

3) Increase the value of hop by one and visit all non-visited vertices that you can reach in hop edges.

4) Repeat 3 until you visit all vertices.

**3.
****Implementation**

The implementation of a graph can be done with several techniques. In this laboratory you will learn three of them.

EdgeListGraph: Probably the easiest one of them but maybe not very efficient. It has the lowest space requirements in a system but also the slowest performance. We define our vertices and edges as follow:

Vertex: Has a reference to the object stored on it plus a reference to the position that it occupies in the collection of vertices in the graph.

Edge: Has a reference to its position in the collection of edges of the graph plus a reference to the object stored on it and the two vertices that form this edge.

AdjacencyListGraph: An extension of the edge list graph. The vertices and edges have the same references inside of them; however this type of graph reduces the search for incidences of a vertex by both the vertices and the edges having a reference to a collection of incidence formed by the edges of a given vertex v or the members of an edge e.

AdjacencyMatrixGraph: The concept of reference to incidence is pretty different in this one. Probably the most complex to understand and definitely the one with the most storage requirements. This type of graph uses the basics vertices and edges. In addition it also has a two dimensional (n x n) squared matrix, where n is the number of vertices in the graph. The positions A(I, J) inside of these matrix are either null if the vertices in the positions I and J are not adjacent or an incidence edge of both vertices I and J.

The implementation of knowing if an edge/vertex has being visited or not can be done either by having a Boolean value inside of them or a hash table with the vertices and edges that have been visited.

**4.
****Practice**

In this laboratory you will need to implement both the DFS and the BFS traversals to use them in two applications of electrical and computer engineering.

For the DFS a power network is provided to you, the idea is to determine if all the destinations of a central power plant have energy and if not determine which ones don’t.

For the BFS you will work on a computer network and find the best route from a router to all of its clients/neighbors according to the weight/cost (value stored in the edge). Also provide for the same network the best route according to number of hops (edges) between the same source router and its clients/neighbors.

The technique to implement the graph provided to you is the Edge List Graph. If you need to determine if a vertex of an edge have been visited or not use the hash table technique. Download the files here.