• Home
• About
• References
• Shibumi

First of all, I should give some information about what algorithm is and where we use them. After that I will give an introduction to Graph Algorithms and keep its details to next articles If you look the header of the doc you can see a version number, it means that i will be updating these article series periodically.

An algorithm is a formula or a set of steps that helps us to solve a particular problem. Normally we use many kinds of algorithms during our life in order to solve problems. As you may guess easily, there are different problems and different solutions which means  many algorithms. Many different problems can be modeled as graphs and we use graph algorithms to solve them. These writing is about one of them named Graph Algorithms

Lets start with a simple algorithm to understand what it is. For instance, lets assume we want to cook omelette.  We have cheese, eggs, oil, salt and the others needs. These are what we have and what we want is a well-prepared omelette. Now we think about the steps of the work.

You can see the steps of the omelette on the example in step by step. However, in some case, you may turn back to the previous step, and these cases happen via loops and clauses. Anyway, I guess it is easy to understand what exactly algorithm is with that example.

Of course, there is not only that way to figure the algorithms but also there are many ways and flow charting is one them. There are two figure below shows you calculation of N factorial with two ways; classical and recursive. You may give some minutes to them if you  dont have any knowledge about flow chart and try to understand what is happening there. I strongly recommend the ones who don’t have any idea that try to write all the steps of calculation like above and then restudy to charts.

There are many kinds of algorithms.

Now after this introduction to algorithm concept we can turn back to our topic. Graph theory provides a language for talking about the properties of relationships. You can see the graphs almost everywhere, in an electric circuit, computer networks, the houses on the road, etc.

More precisely, a graph G = (V,E) consists of a set of vertices(node) V together with a set E of vertex pairs or edges. Graphs can be used to represent essentially any relationship. For example, think about a cities, roads (edges) and the places (nodes).

Several fundamental properties of graphs impact the choice of the data structures used to represent them and algorithms available to analyze them. The first step in any graph problem is determining the flavors of graphs you are dealing with:

Think about the roads which are edges, there are two individual kind of roads according to their directions, like double and single. You can use double-way roads both coming and going, however you can use highways just one way. Now using this metaphor, we can say that, the roads only one ways are directed edges from one node to other node. Other case, it is undirected, because there is no specification for the direction and all the communication channels are open both nodes. As you can see from figure there are directions between the nodes.

Look at the graph figure above, if there was a value on edges then it would be Wighted graph. Knowing the weights of edges is the same as knowing the distance between two places. So, using that tiny information we can say that the graph above is a directed unweighted graph.

Sometimes there can be cycles in the graphs, this is logical; again when you think about the roads of places, you can see the cycles. These kind of graphs are called Cyclic graphs. The figure above again cyclic graph and also directed and unweighted. B-C-E-D-B this is the cyclic part of it.

Soon…..

Yorumlar

Henüz Yorum Yok.

Yorum Yazın