Graphs and Trees
By Herbert J. Bernstein
© Copyright 2003 Herbert J. Bernstein
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
- Adjacency Matrix
- 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: