Graphs

In computer science, a graph is a kind of data structure, specifically an abstract data type (ADT), that consists of a set of nodes and a set of edges that establish relationships (connections) between the nodes. The graph ADT follows directly from the graph concept from mathematics.

definition: G1=(V,E), where V is a finite, non-empty set of vertices (singular: vertex) and E is a set of edges (links between pairs of vertices).

comparison:Graph data structures are non-hierarchical and therefore suitable for data sets where the individual elements are interconnected in complex ways. For example, a computer network can be simulated with a graph.

Hierarchical data sets can be represented by a binary or nonbinary tree. It is worth mentioning, however, that trees can be seen as a special form of graph.

# Terminology (Directed, Undirected, Acyclic, Cyclic, Weighted graphs)

When the edges in a graph have no direction, the graph is called undirected, otherwise called directed. In practice, some information is associated with each node and edge.If any number(weight) is assosiated with each edge it is a weighted graph.

Acyclic graphs are those in which thr is no loop formed by edges at all,otherwise thy r called cyclic graphs.

# Representation

Two standard ways to represent a graph G = (V, E):
>as a collection of adjacency lists
>as an adjacency matrix. Either way is applicable to both directed and undirected graphs.

The adjacency-list representation is usually preferred, because it provides a compact way to
represent sparse graphs-those for which |E| is much less than |V|2. Most of the graph
algorithms presented in this book assume that an input graph is represented in adjacency-list
form.
directed graph:the sum of the lengths of all the adjacency lists is |E|, since an edge of
the form (u, v) is represented by having v appear in Adj[u].
undirected graph: the sum of the lengths of all the adjacency lists is 2 |E|, since if (u, v) is an undirected edge, then u appears in v's adjacency list and vice versa.

For both directed and undirected graphs, the adjacency-list representation has the desirable property that the amount of memory it requires is Θ(V + E).

An adjacency-matrix representation may be preferred, however, when the graph is
dense-|E| is close to |V|2-or when we need to be able to tell quickly if there is an edge connecting two given vertices.

# Traversal

Breadth-first search is so named because it expands the frontier between discovered and
undiscovered vertices uniformly across the breadth of the frontier. That is, the algorithm
discovers all vertices at distance k from s before discovering any vertices at distance k + 1.

It is a simplest algo 4 srching a graph nd the archetype 4 many graph algos lik prim's min-spanning algo n Dijkstra's single-source shortest-paths algo.

1. Produces a "breadth-first tree" with root s that contains all reachable vertices.
2. For any vertex v reachable from s, the path in the breadth-first tree from s to v corresponds to a "shortest path" from s to v in G, that is, a path containing the smallest number of edges.
3. The algorithm works on both directed and undirected graphs.

BFS(G, s)
1 for each vertex u V [G] - {s}
2 ………do color[u] ← WHITE
3 ……………d[u] ← ∞
4 …………..π[u] ← NIL
5 color[s] ← GRAY
6 d[s] ← 0
7 π[s] ← NIL
8 Q←Ø
9 ENQUEUE(Q, s)
10 while Q ≠ Ø
11 …..do u ← DEQUEUE(Q)
13 ………….do if color[v] = WHITE
14 ………………then color[v] ← GRAY
15 …………………….d[v] ← d[u] + 1
16 ……………………. π[v] ← u
17 …………………….ENQUEUE(Q, v)
18 ……..color[u] ← BLACK

#### DFS-Depth First Search

The strategy followed by depth-first search is, as its name implies, to search "deeper" in the
graph whenever possible. In depth-first search, edges are explored out of the most recently
discovered vertex v that still has unexplored edges leaving it. When all of v's edges have been
explored, the search "backtracks" to explore edges leaving the vertex from which v was
discovered. This process continues until we have discovered all the vertices that are reachable
from the original source vertex. If any undiscovered vertices remain, then one of them is
selected as a new source and the search is repeated from that source. This entire process is
repeated until all vertices are discovered.

The predecessor subgraph of a depth-first search forms a depth-first forest composed of
several depth-first trees. The edges in Eπ are called tree edges.

The following pseudocode is the basic depth-first-search algorithm. The input graph G may
be undirected or directed. The variable time is a global variable that we use for timestamping.

DFS(G)
1 for each vertex u V [G]
2 …….do color[u] ← WHITE
3 …………….π[u] ← NIL
4 …………….time ← 0
5 for each vertex u belongs to V [G]
6 ……do if color[u] = WHITE
7 ……………then DFS-VISIT(u)
DFS-VISIT(u)
1 color[u] ← GRAY ▹White vertex u has just been discovered.
2 time ← time +1
3 d[u] time
4 for each v belongs to Adj[u] ▹Explore edge(u, v).
5 do if color[v] = WHITE
6 then π[v] ← u
7 DFS-VISIT(v)
8 color[u] BLACK ▹ Blacken u; it is finished.
9 f [u] ▹ time ← time +1

# Topological Sort

TOPOLOGICAL-SORT(G)
1 call DFS(G) to compute finishing times f[v] for each vertex v
2 as each vertex is finished, insert it onto the front of a linked list
3 return the linked list of vertices

# exercizes

plz find programming excersize here assignment2_prog.pdf2..plz try 2 solve it by urself 1st then u may visit my code here [[file graphs.java]

page revision: 37, last edited: 07 Jun 2007 07:28