Data structure

Proper structures for proper algorithms.

Published at 2018-02-25, Updated at 2013-02-26.
Single Source Shortest Path

Single Source Shortest Path

Posted in Data structure at 2011-10-25 by #care-crew

A common problem is to find the shortest way from one to another point. Dijkstra created the solution, which is used as a basis for car navigation systems and traffic systems. In a Graph are several nodes, one node can have a connection to another node, the c...

All Pairs shortest Path

All Pairs shortest Path

Posted in Data structure at 2011-10-25 by #care-crew

Another common problem is to find the shortest pairs within a graph. An algorithm from Floyd is explained. The best solution is to use a matrix for implementation. If a node does not have a direction connection to another node the cost is unlimited. The alg...

Minimal Spanning Tree

Minimal Spanning Tree

Posted in Data structure at 2011-10-25 by #care-crew

The algorithm from Kruskal enables to extract the minimal spanning tree out of a Graph. Useful to save edges. The algorithm sorts all edges depending on their costs. Starting with the lowest. A new graph without edges is created. Now take the edge with the ...

Plane Sweep Algorithm

Plane Sweep Algorithm

Posted in Data structure at 2011-10-25 by #care-crew

Imagine you want to create your own video game or your own collision detector. The Plane Sweep Algorithm is the basic, you can adjust it to your needs. In the picture above you can see the red sweepline. And you see a lot of lines. Our goal is to find out o...

Introduction to Data Structures

Introduction to Data Structures

Posted in Data structure at 2011-10-25 by #care-crew

A data structure represents data of any kind in a way that is useful for an algorithm. There are different kind of data structures and it is important to use the right one depending on the problem which should be solved. A data structure can be static, it wil...

Segment Tree

Segment Tree

Posted in Data structure at 2011-10-25 by #care-crew

A Segment Tree is a data structure that enables you to find points in geometry. It is dynamic and its simplest form is the binary tree. Each Node of the tree saves the top and bottom of the saved Interval, a list of Intervals(lines in this area) and its left ...

Hierarchical Data in a Relational Database

Hierarchical Data in a Relational Database

Posted in Data structure at 2011-10-25 by #care-crew

Relational Databases like Mysql (or similar) do not support storing xml like data natively. There are different solutions for it and we present you another one. The table structure: id INTEGER PRIMARY INCREMENT name VARCHAR(50) parent INTEGER deepness INT...

Semantic Interoperability

Semantic Interoperability

Posted in Data structure at 2011-11-28 by #care-crew

The semantic heterogeneity creates conflicts between the interoperability of software and web services. Human persons are able to figure out the conflicts, but computers do not have the abilities to solve the conflicts. The result of a search query returns ma...