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:** G^{1}=(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.

#### Adjacency List

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

#### Adjacency Matrix

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

#### BFS-Breadth First Search

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.

- Produces a "breadth-first tree" with root s that contains all reachable vertices.
- 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.
- The algorithm works on both directed and undirected graphs.

BFS(G, s)

1foreach vertex u V [G] - {s}

2 ………docolor[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)

10whileQ ≠ Ø

11 …..dou ← DEQUEUE(Q)

12 ……..foreach v Adj[u]

13 ………….doif color[v] = WHITE

14 ………………thencolor[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)

1foreach vertex u V [G]

2 …….docolor[u] ← WHITE

3 …………….π[u] ← NIL

4 …………….time ← 0

5foreach vertex u belongs to V [G]

6 ……doifcolor[u] = WHITE

7 ……………thenDFS-VISIT(u)

DFS-VISIT(u)

1 color[u] ← GRAY ▹White vertex u has just been discovered.

2 time ← time +1

3 d[u] time

4foreach v belongs to Adj[u] ▹Explore edge(u, v).

5do ifcolor[v] = WHITE

6thenπ[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.pdf^{2}..plz try 2 solve it by urself 1st then u may visit my code here [[file graphs.java]