A practical introduction to GRAPHS

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:

  • Breadth First Search

–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

 


Breadth First Search (BFS)

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

Queue.Add (1st Vertice )

While (Exists unexplored vertices){

v= queue.remove();

v.visited =true;

for each (ai :neighbours of v)

if (not visited(ai)) queue.add(ai);

}

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


Depth First Search (DFS)

 

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *