Hello @all, As I have mentioned on several posts here on forums, I am only now starting to learn graphs in a more educated, methodical and serious way, so, after I have studied DFS for few days and due to me not finding anything useful online, I decided I would write this tutorial so people can benefit from it and hopefully having an easier time in learning about graphs :) [note: I still don't know much things about graphs, but, I believe that writing about a topic we learnt, it's the best way to strengthen our knowledge on it, so, if any flaws are found, please feel free to correct them :)]
Graphs are everywhere! From social networks, to route planning and map analysis, passing by party planning, electric circuits analysis and even Galatik football tournaments (:D ) there are actually few domains of Science and everyday life where Graphs can't be seen as useful. As such, it can be quite an intimidating topic, especially because all the mathematical theory that lies behind them, seems to be a bit far from this reality. I will try to define a Graph, state some terminology and end with the first of two graph traversal methods, which, as we will see ahead, are both essential in "reading" the graph (in the sense of gathering information about its structure) and, with some additions, allows us to solve some simple problems.
Formally, we define a graph as being composed by two sets, V and E, respectively denoting the set of vertices and the set of edges. We say that vertices are connected by edges, so an edge connects two vertices together. If we generically denote a graph as G, we usually denote it by its two sets, such that the following notation is very common: G(V, E)  is the graph G composed by V vertices and E edges. Below is a simple example of what a graph looks like (the description is in portuguese, but, it should be easy to understand): So we can immediately see that the small orange circles represent vertices and the black lines represent edges. Please note that while it might seem a bit formal and confusing at the beginning, when we talk about graphs, this is the terminology we are going to use, as it is the only terminology we have which allows us to understand all graph algorithms and to actually talk about graphs, so, for someone who finds this a bit confusing, please twist your mind a bit :) So, now we know how to define a graph and how it is formally represented. This is very important for the remaining of this post, so, make sure you understand this well :) However, for sure that graphs aren't only about defining a set of vertices and edges, are they? Well, it turns out that things can get a little bit more complicated and there are some special types of graphs besides the generic one, which was the one we just looked at. So, let us see what more kinds of graphs we can have.
As it was mentioned on the foreword, graphs are used to model a lot of different everyday and science problems, so, it was necessary to devise more particular types of graphs to suit such vast problemset. Let's see some definitions about these "special" graphs and examples of application domains: Type 1: Directed Graph On a Directed Graph, the edges can have an associated direction. This type of graph can be particularly useful if we are modelling for example some given system of roads and/or highways to study traffic, as we can have a defined way on a given road. Making the edges directed embeds this property on the graph. Type 2: Directed Acyclic Graph It is alike the graph above, except that on this particular type of graph we can't have "loops", i.e., we can't start a given path along the graph starting on vertex A and ending of vertex A again. Type 3: Weighted Graph In a weighted graph, the main characteristic is that the edges can have an associated "cost". Mathematically speaking (and also in Operations Research) this "cost", need not to be money. It can model any given quantity we desire and it is always "attached" to the problem we are modelling: if we are analysing a map it can represent the cost of a given road due to a toll that's placed there, or distances between cities. In Sports, it can represent the time taken by a professional paddling team to travel between two checkpoints, etc, etc... The possibilites are endless. Besides these types there are also many other types of graphs (a tree, for instance, can be seen as a particular type of graph) that were devised for more advanced applications and that I really don't know much about yet, so these will be all the types of graphs I will talk about on this introductory post.
It turns out that one of the hardest things about graphs for me (besides wrapping your head around the enormous amount of applications they have) is that literally everything on them is highly dependent on the problem they are modelling, even the way we decide to represent them is. However, there are not that many ways to represent a graph internally in computer memory and even from that small universe we are going to focus solely on two representation schemes. Representation via adjacency lists and representation via adjacency matrix. For a better understanding, let us consider the graph below:
We can see now, thanks to our formal definition given earlier on this text, that this graph is composed from two sets, the set of the vertices and the set of the edges. We have 4 vertices and 4 edges. However, only the information concerning the number of vertices and edges is not sufficient for us to describe a given graph, because, as you might have figured out by now, the edges could be placed differently (like in a square, for example.) and we wouldn't be able to know it. This is why there are representations of graphs which allows us to "visualize" the graph in all of its structure, from which the adjacency matrix will be the one we will study in the first place.
The adjacency matrix (let's call it A) is very simple to understand and, as the name itself says, it's a representation that is based on a matrix of dimensions V x V, where it's elements are as follows: A(i,j) > 1, if there exists an edge between vertex i and vertex j; A(i,j) > 0, otherwise; So, for the above graph, its adjacency matrix representation is as follows:
The representation as an adjacency list is usually more convenient to represent a graph internally as it allows for an easier implementation of graph traversal methods, and it is based, also, as the name states, in having a "list of lists" for each vertex, that states the vertices to which a given vertex is connected. As a picture is worth a thousand words, here is the adjacency list representation of the above graph: here, the symbol / is used to denote end of list :) Now that we have looked into two of the most common ways of representing a graph, we are ready to study the first of two traversal algorithms, DepthFirst Search.
DepthFirst search, often known as DFS (it stands for the beginning letters of each word) is a graph traversal algorithm where the vertices of the graph are explored in depth first order, with the search algorithm backtracking whenever it has reached the end of the search space, visiting the remaining vertices as it tracks back. This idea is illustrated on the figure below where the order by which vertices are visited is described as a number (note that this is a tree, but, also, as discussed earlier, a tree is a particular kind of graph, and it has the advantage of being easy to visualize). As the vertices are first explored to a certain order and then we must backtrack to explore remaining vertices, the DFS algorithm can be naturally implemented in a recursive fashion. Also please note that we assume here that the visited vertices are visited only once, so we can have, in pseudocode:
It's now important to mention two things: The first one is that in Graph Theory, DFS is usually presented in an even more formal fashion, mentioning colors and discovery times and end times for each vertex. Well, from what I understood, in programming contests the above routine is enough and the purpose of having array visited() is precisely to "replace" the color attributes that are related to discovery and end times, which I chose to ommit to keep this post in the ambit of programming competitions. Finally, to end this explanation, what is more important to mention is that DFS usually is implemented with something more besides only that code. Usually we "add" to DFS something "useful" that serves the purpose of the problem we are solving and that might or might not be related to two of most well known applications of DFS, which are:
FIRESC problem is the perfect problem for us to put our skills to test :) Once we understand how to model the problem in terms of graphs, implemeting it is simply using one of the applications of DFS (finding connected components). Simply, we can model this is terms of graphs as follows: Let us define a graph whose vertices are people. An undirected edge connects two people who are friends. On this graph, two vertices will be of the same color if they share an edge. This represents that the two people should have to go in the same fire escape route. We wish to maximize the number of colors used. All the vertices in a connected component in this graph will have to be in the same color. So as you see, we need to count the size of all connected components to obtain part of our answer, and below I leave my commented implementation of this problem, largely based on the work of @anton_lunyov and on the post found on this site (yes, I had to use google translate :p ).
I hope you have enjoyed this short introduction to graphs and I really hope this can help anyone willing to study graphs to come across a rigorous, yet simple and understandable text :) Best regards, Bruno asked 17 Jul '13, 22:24

@kuruma Real Nice One! Keep it up bro! Your editorials are always superb. :) I have a little something to add. This is about the array Please note that this answer is entirely based on the DFS algorithm as given in CLRS text book (Introduction to Algorithms).
Now, For example, the problem of labelling / classifying edges of a directed graph as treeedge / forwardedge / backedge / crossedge. (Go here to know a little bit more on what these labels mean.) Edges used in DFS (i.e., edges from a node Following is a pseudocode, solving edgelabelling problem.
The solution given here talks about using the discovery time and finishing time to identify and classify edges. This is one example, where just having the array answered 18 Jul '13, 09:42
1
Hey @tijoforyou, yes, I was perfectly aware that such arrays are not only there for the sake of completeness and might really be needed at some point (just as you showed :) ). I opted for not including them to keep the text as introductory as possible and also because it was what it was mentioned on that russian website link I provided :)
(18 Jul '13, 14:43)

@kuruma hey this is my blog on coding.Just started it. I'll soon be posting about graphs.Do take a look at it. http://cod3rutopia.blogspot.in/ answered 18 Jul '13, 12:27

Thank you for this post. Keep up the good work. Yes, the best way to learn something is to explain it to others. Thank you for your lovely post and i hope you have a good day you beautiful human being! answered 19 Jul '13, 02:03

Nice work kuruma....keep it up.It was written in a neat and crisp way.This tutorial was required by many newbies. One can expect people implementing this tutorial's code from the next contests :) answered 23 Jul '13, 13:29
Thank you very much for the positive feedback @re_hash! I hope I can implement all these ideas in next contests myself as well :D
(23 Jul '13, 19:27)

@bruno Really nice post. if you want to learn some more things about graphs i would recommend DSA course in NPTEL by Prof. Naveen Garg. here is the link. answered 17 Jul '13, 23:16
Thank you very much @kcahdog I will look into it asap :D Also, do you know any more problems which are as straightforward as FIRESC? I wanted to train more :D
(18 Jul '13, 02:26)
1
@kuruma Doing excellent work by writing good stuff.Here are some really straightforward ones Try the pacman dfs and bfs. https://www.hackerrank.com/categories/ai/astarsearch
(18 Jul '13, 02:47)
Thank you very much for this link @jaskaran_1 and I am glad you liked my post :) It is amazing to see my work recognized and I really feel like I am learning new things now!! :)
(18 Jul '13, 03:00)
1
@kuruma Even i am new to graphs and GALACTIK is the only graphs problem i have solved so far. Will keep you updated if i find any interesting problems
(18 Jul '13, 16:26)
Thank you very much @kcahdog :) I really tried very hard to solve GALACTIK during contest, but, I couldn't :(
(18 Jul '13, 19:36)
Interestingly, GALACTIK can also be solved using the DisjointSet Data structure. My solution was based on DFS. But out of curiosity (as I was lazy, didn't try this version), once the contest was over, I checked if someone has solved it using DisjointSets, and found @mugurelionut's solution.
(18 Jul '13, 21:53)
showing 5 of 6
show all

@Kuruma Great post !!! Even I learnt about graphs only after the FIRESC problem :) Also, just wanted to share one of my learnings from the GALACTIK problem (http://www.codechef.com/JULY13/problems/GALACTIK) , which I solved using graphs. I was always confused regarding when to use BFS and when to use DFS. By default I always used DFS. But looks like solving GALACTIK with DFS will give TLE! After many wrong attempts I finally got AC when I shifted to BFS :) answered 18 Jul '13, 10:27
I got AC with DFS!!
(18 Jul '13, 10:39)
And because of the ease of programming, me too, usually (or by default :P ) use DFS!!!
(18 Jul '13, 10:40)
Hello @vpyati, yes, I also really, really want to solve GALACTIK problem :D I am eagerly waiting for editorials and although I have seen some AC solutions I want to understand everything at its fullest extent :)
(18 Jul '13, 14:44)
GALACTICK could be solved using Disjoint Sets data structure instead of DFS and BFS. This would have sped up the code by many times :)
(20 Jul '13, 01:18)
I solved the problem first by Disjoint Sets and then by DFS. Learned a lot about DFS from GALACTIK that helped me in FEB14 in solving DRGHTS.
(17 Feb '14, 17:13)

Awesome post !! Easy to understand and really good for a beginner . . I tried my hand on implementing some of the graph algorithms in python and I've uploaded it on github link , if someone wants to go through them , its available . It might be a bit messy though , I've tried my best to make it look good and readable . Hope it helps !! answered 18 Sep '13, 22:19

https://theoryofprogramming.wordpress.com/ Have a look at this blog it contains nice stuff on graphs and trees.. answered 03 Feb '15, 22:19

i am not getting what is sz_connct_compt is? could u please explain me? answered 22 Jun '15, 10:56
It tells that a particular friend has sz_connct_compt number of connected friends. Means, if 1>2 and 2>3 and 3>5,6 so when we dfs(1) the sz_connct_compt will become 5, as there are 5 friends that will be liking to escape by same route. I hope now you have understood. @amanjain7793
(23 Aug '15, 11:02)

Nice tutorial, made DFS so clear as you used it to solve a problem, This is a great help for beginners please continue this kind of tutorials. answered 11 Mar '17, 18:17

following link is be very useful for u to understand binary tree traversal(preorder, inorder, postorder) in detail including graphs: https://youtu.be/8QD9U3OSmW4 answered 04 Apr '17, 23:03

This is nice. A correction. "Vertices" instead of "Vertexes".
Thanks, I will fix this!
@admin , why does it say "asked n days ago by kuruma" shouldn't it rather say "posted n days ago by kuruma" ? btw @Kuruma, really nice and helpful post :)
Thank you @v_akshay, I'm glad you liked this :) About the asked vs posted part, as this was a "question", it says asked, but, I guess that is just how the forums work :)
@Kuruma its really helpful thanks!!