## Graphs and Trees

Often we view information in terms of connections between items. Sometimes the connections allow us to specify the relative positions of items, which item comes before which other item. This defines a list of items. Sometimes the connections are more general and non-linear, leading us to consider trees and graphs

A tree is a graph. A graph is a collection of nodes connected to one another by edges. If the edges have a direction, the graph is called a directed graph. If the edges do not have a direction, the graph is called an undirected graph. A path in a graph is a sequence of edges obeying the direction rules of the graph such that the end node of each edge in the path (except for the last edge in the path) is the start node of the next edge in the path. A path is a circuit if the end node of the last edge of the path is the start node of the first edge of the path. A graph is called connected if there is a path from every node to every other node.

One or more values (attribute-values) may be associated with each node of a graph.

One or more values (attribute-values) may be associated with each edge of a graph.

### Directed Graphs

• A graph G is:
• A set of nodes N (also called vertices or points)
• A set of edges E consisting of ordered pairs of nodes ( n1, n2 ) (also called arcs lines).

n1 --------> n2

• Dual of a graph exchanges nodes and edges
• Operations
• Construct an empty graph or a graph from a list of nodes and a list of edges
• Count the nodes in a graph
• Count the edges in a graph
• Add a node to a graph
• Add an edge between two nodes
• Remove an edge from a graph
• Remove a node and all associated edges from a graph
• Link one graph to another at a common node
• Link one graph to another by an edge
• Remove a subgraph from a graph
• Associate a value or mark with a node
• Associate a value or mark wirh an edge
• Find a (shortest) path from a given node to another given node (length defined by number of edges or by sums of some non-negative edge values).
• Find a circuit from a node to itself
• Find the diameter of a graph (the maximum of all shortest paths)
• Find a cut between two nodes (a set of edges that will disconnect those nodes)
• Find a minimal cut between two nodes
• Find the capacity of a path (the mimimum value of a "capacity" value associated with each edge)
• Find the maximal flow between two nodes.
• Representations
• Matrix of Booleans
• Each row and each olumn represents a node
• A true entry represents and edge from the row node to the column node
• Does not permit more than one edge between two nodes
• May be extended to provide values for edges
• Array of Adjacency Lists
• One entry in the array for each node
• Each entry is a list of nodes to which this node is connected
• List of Adjaceny Lists
• Dual-based versions of these representations
• Shortest Path Algorithms
• Dijkstra's algorithm
• Shortest paths from a given node to all other nodes
• Greedy algorithm (add as many nodes as possible each time)
• Maintain a set X of nodes for which the shortest path is known, and mark each member with the length of the shortest path from the starting node.
• Start with the single starting node in set X
• Examine each of the nodes with edges to nodes in X and compare the path lengths.
• Add to X those nodes for which the new path length is minimal.
• Running time depends on the representation: O(card(N)2) for an adjacency matrix, O(card(E)log(card(N)) for an array of adjancency lists

### Trees

• A tree is a directed, connected graph with only one path from any given node to any other node.
• A rooted tree is a tree with one distingushed node (the root) from which there is a path to every other node

```         root node
/|\
/ | \
/  |  \
/   |   \
a    b    c
/\    |   /|\
d  e   f  g h i
/ \  \  \    \  \
```
In a rooted tree every node except the root is connected to the tree by a single edge from a parent node, and the node itself is called a child of the parent. Each child may be viewed as the root of a sub-tree.

In a binary tree each node as at most two children, and each child has an attribute ("side") with the value "left" or "right".

A trie (from retrieval) is a tree structure to handle searchable lists of character strings. The tree branches where words with common roots differ:

```                root
/
a
/ \
l   s
/   / \
l   k   s
/ \   \   \
.   o   .   i
\       \
w       g
\       \
.       n
\
.
```

A balanced tree has paths from the root to the leaf nodes of similar lengths. A 2-3 tree has interior nodes with 2 or 3 children each and every path from the root to a leaf is the same length.

For more on trees, see: