An Insight into Graphs
(Page 1 of 4 )
An understanding of graphs can actually help simplify apparently difficult problems. They're a useful tool that belongs in every programmer's toolkit. In this introductory article, you will learn how graphs and programming relate to each other.
"Everything should be made as simple as possible, but not simpler," said the great theoretical physicist Albert Einstein. Indeed, why should we bother to understand and possibly even solve practical problems beyond our comprehension? If only we could bring them down to a level that is straightforward enough for an immediate solution.
This is the entry point of an article series I will write relating to the graphs. During this series, I will present many algorithms that usually relate to a simple observation. I will focus on the programming part most of the time and offer to you only minimal background knowledge.
During this first article, you will learn some general information about graphs, and more importantly, how we represent them in our coding languages, which for me will be C most of the time. So if you are interested in this field, come aboard and keep reading.
Graphs in their essence were constructed and used to solve complex-looking problems that we face in our everyday life. The idea is that we need to find the common bonds between similar-looking issues and make them simple enough so that we can find for them an answer that will work every time.
Graphs are the road to simplification. There are countless problems that may be represented as a graph; however, before we learn that we need to find out what a graph is. Graphs come from the vast land of mathematics; they try to represent a set of objects that are connected by some rule with another set of links.
-A prime example of a simple directed graph-
To make all this a little more interesting, the objects at the points are vertices(nodes/points) while the links are referred to as edges (lines). That's pretty simple so far, right? To make all this a little more complicated, the relationships may be bidirectional (as in the case of you and your mother) or they may work only in one direction (as in the case of the president and the vast majority of people). The latter connections are called directed edges.
The problems stem from our daily life, and with the knowledge described above, I'm sure you can already think of a couple. Nevertheless, if not, let me help you with one: the road system of a country where the cities represent the objects and the roads the edges. Alternatively, think about the relationships between people at a meeting, where the vertices are the individuals, and if there is a connection between two of them, there will be an edge.
The pipe system transporting gases, water, oil and so forth, also has the potential to be the base of a graph. Finding out the maximum amount that can flow through the pipes in a moment is something to take into account when we build them, and oil companies are willing to pay a lot of cash for this information.
From this, we can also deduce that sometimes the edges may have an additional attribute -- something that will point out the length of the edge or how much of a substance can flow through it. Moreover, the examples can follow on endlessly. The idea is that this is something worth investigating and developing a theory around.
Next: The Theory >>
More Code Examples Articles
More By Gabor Bernat
