# Practical guide to graphs

• This tutorial will provide a practical introduction to graphs, their properties and their applications. The demonstrations of their properties will be just enounced, leaving this task to other, more rigorous tutorial.
• Definition : • a graph is structure consisting of edges(1,2,3,4) connected by vertices (1-3, 2-3,1-4)
• Categories : – Oriented (Directed) – where the edges can lead only from one edge to the other–Not oriented (undirected) – edges can go both ways
• Auxiliary definitions
• Connex component: a subset of a graph where all vertices are connected by a path (For example in the graph bellow we have two connex components {1,2,3,4} in red and {5,6,7} in blue. ## Graph exploration

```There are 2 main graph explorations algorithms:

```

–Exploring all direct neighbors of a vertice, then going to the neighbors’ neighbors

• Depth First Search

–Explore the one neighbor, try to go as deep as we can with the exploration

Idea : We use a queue (FIFO – First In First Out list) in which we add the neighbors to explore

For each node use an extra  variable which mark whether the vertice was already  explored, so to ensure vertices are explored only once

Algorithm :

Mark all vertices as unexplored

While (Exists unexplored vertices){

v= queue.remove();

v.visited =true;

for each (ai :neighbours of v)

}

Using this algorithm the connex components are  explored in linear time, in a layered fashion as seen in the example presented here : 