# User:Mahanga/Sandbox

## Contents

## Graphs[edit]

A **graph** is a generalization of the tree structure, where instead of a strict parent/child relationship between tree nodes, any kind of complex relationships between the nodes can be represented. A graph (*G*) is a collection of *vertices* (V) that are linked by *edges* (E). Each edge, sometimes called an arc, consists of a pair of vertices, which are adjacent to one another. Typically, a graph is shown as a set of circles for the vertices, appropriately labelled, which are joined by lines (edges). The two most common representations of graphs are directed and undirected graphs are the two most common representations of graphs.

We will begin with directed graphs, also known as digraphs, which have the easiest to understand representation, and then undirected graphs and finally weighted graphs.

### Graph Terminology[edit]

Before continuing, some knowledge of graph terms is necessary. The order of a graph is the number of its edges, i.e. |*V*(G)|. A common problem is trying to find the length from one vertex to another. This is called finding the path between two vertices. A *path* is a sequence of vertices in a graph where each vertex has an edge from it to the next vertex until reaching the final vertex. The *length* of a path is the number of edges used. A simple path is similar to a path, except it cannot visit the same vertex twice. A graph *cycle* is a path that starts and ends at the same vertex, thus it cycles back.

Graphs are an essential part of Computer Science and play a significant role in real-world applications. For example, a graph can be used to describe the airport system. For example, what is best flight, in terms of total distance, from one city to another? One can use vertices to represent airports and edges to represent the connections between any two airports. In this case, one would most likely use directed graphs with a weight or cost assigned to each edge. Weighted graphs will be explained at the end of this chapter.

## Graph Representations[edit]

[TODO: picture of directed graph]

### Directed Graphs[edit]

The number of edges with one endpoint on a given vertex is called that vertex's **degree**. In a directed graph, the number of edges that point *to* a given vertex is called its **in-degree**, and the number that point *from* it is called its **out-degree**. Often, we may want to be able to distinguish between different nodes and edges. We can associate labels with either. We call such a graph **labeled**.

**Directed Graph Operations**

**make-graph**(): graph- Create a new graph, initially with no nodes or edges.
**make-vertex**(graph*G*, element*value*): vertex- Create a new vertex, with the given value.
**make-edge**(vertex*u*, vertex*v*): edge- Create an edge between
*u*and*v*. In a directed graph, the edge will flow from*u*to*v*. **get-edges**(vertex*v*): edge-set- Returns the set of edges flowing from
*v* **get-neighbors**(vertex*v*): vertex-set- Returns the set of vertexes connected to
*v*

[TODO: also need undirected graph abstraction in that section, and also find a better set of operations-- the key to finding good operations is seeing what the algorithms that *use* graphs actually *need*]

We can use graphs to represent relationships between objects. For example, the popular game *Six Degrees of Kevin Bacon* can be modeled by a graph, in particular, a labeled undirected graph. Each actor becomes a node, labeled by the actor's name. Nodes are connected by an edge when the two actors appeared together in some movie. We can label this edge by the name of the movie. Then the problem of finding a path from any actor to Kevin Bacon in six or less steps easily reduces to the Single Source Shortest Path problem found in the companion Algorithms book. The Oracle of Bacon at the University of Virginia has actually implemented this algorithm and can tell you the path from any actor to Kevin Bacon in a few clicks[1].

#### Adjacency Matrix Representation[edit]

An **adjacency matrix** is one of the two common ways to represent a graph. The adjacency matrix shows which nodes are **adjacent** to one another. Two nodes are adjacent if there is an edge connecting them. In the case of a directed graph, if node is adjacent to node , there is an edge from to . In other words, if is adjacent to , you can get from to by traversing one edge. For a given graph with nodes, the adjacency matrix will have dimensions of . For an unweighted graph, the adjacency matrix will be populated with boolean values.

For any given node , you can determine its adjacent nodes by looking at row of the adjacency matrix. A value of true at indicates that there is an edge from node to node , and false indicating no edge. In an undirected graph, the values of and will be equal. In a weighted graph, the boolean values will be replaced by the weight of the edge connecting the two nodes, with a value of zero indicating no edge.

The memory use of an adjacency matrix is .

#### Adjacency List Representation[edit]

### Graph Traversals[edit]

#### Depth-First Search[edit]

[TODO: depth-first search -- with compelling example]

// Search in the subgraph for a node matching 'criteria'. Do not re-examine // nodes listed in 'visited' which have already been tested. GraphNode depth_first_search(GraphNode node, Predicate criteria, VisitedSet visited) { // Check that we haven't already visited this part of the graph if (visited.contains(node)) { return null; } visited.insert(node); // Test to see if this node satifies the criteria if (criteria.apply(node.value)) { return node; } // Search adjacent nodes for a match for (adjacent in node.adjacentnodes()) { GraphNode ret = depth_first_search(adjacent, criteria, visited); if (ret != null) { return ret; } } // Give up - not in this part of the graph return null; }

#### Breadth-First Search[edit]

[TODO: breadth-first search -- with compelling example] [TODO: topological sort -- with compelling example]

### Undirected Graphs[edit]

In a directed graph, the edges point from one vertex to another, while in an **undirected graph**, they merely connect two vertices.

### Weighted Graphs[edit]

We may also want to associate some cost or weight to the traversal of an edge. When we add this information, the graph is called **weighted**.