202: Graphs vs. Trees vs. Hierarchies: Compared.

Before exploring HTML and CSS further, you’re going to need to understand graphs, trees, and hierarchies.

These concepts apply throughout programming and are not limited to just HTML and CSS. But as I was trying to figure out what topic to explain next to you, I realized that you’re going to need to understand these topics in order to master HTML and CSS. You’ll be glad you took the time to understand these when you encounter them again in your code.

A graph is the most general way to relate things. A good example is a map of world countries in Europe or of the states in a map of the United States. Think of how the countries are positioned so they touch one another. In order to go from one country to another, you can either go straight there or you can take a winding path through many countries. You might even pass through a particular country many times on your journey. And with modern airline travel, you can even go from one country to another even if they don’t share a border.

Each country in this example is called a vertex in a graph. The connections between countries either directly through a shared border or indirectly by flying are called edges in a graph. If you were to draw a graph of Europe, you could start by drawing a dot for each country. It helps to put the dots on the graph in the general location of the center of each country. But you don’t have to. You can put the dots wherever you want and they don’t have to follow any scale. Big countries or small don’t matter. Each country gets a dot or a vertex in the graph.

Once you have your vertices drawn, then you can start working on the connections. There’s lots of things to consider when making the edges or connections. What if there’s more than one way to get from one vertex to another? Should you use multiple edges or combine them together into one? What if one way uses a bullet train so it’s fast and easy while another uses pack mules through the mountains? Can you go both ways? Or is the connection one way only? What do you do if one or more vertices are isolated with no way to get to the other vertices?

All trees are actually graphs. But not all graphs can be called trees. There are four special conditions that a graph must follow in order to be considered a tree:

  1. There can be no cycles in a tree. This doesn’t mean that there are no bicycle paths connecting countries. A cycle in this sense is a loop or a way to go around and around in the edges.
  2. Every vertex represents a node that is the root of a subtree. Even a single node can be considered the root of its own subtree. Usually trees refer to the vertices as nodes instead. The two terms are somewhat interchangeable and if you want to you can refer to both of them as nodes even for a graph.
  3. Every two nodes in a tree are connected by exactly one path. That path might have to go up the tree through parent nodes and back down again through other nodes. But it will exist.
  4. A tree is fully connected and has exactly one less edge or connection than nodes. There are no unconnected nodes allowed in a tree.

So how do hierarchies fit into all this? A hierarchy is a tree with a couple extra properties:

  1. The first is inheritance either up or down the hierarchy.
  2. The second property of hierarchies is that they consider roles.

Make sure to listen to the full episode for more details and examples and subscribe to the podcast so you’ll get future episodes automatically.

No comments yet.

Leave a Reply