Graph
A graph is a way to represent a set of vertices (also known as nodes) and the connections between them, called edges. It is a fundamental data structure used to model relationships between objects.
In a graph, vertices can represent any kind of entities, such as cities in a map, web pages in a website, or even individuals in a social network. The edges represent the relationships or connections between these entities.
Directed graph
A directed graph, also known as a digraph, is a type of graph where each edge is assigned a direction. This means that the edge connects a source vertex to a target vertex, indicating a one-way relationship between them.
Directed graphs are commonly used to represent relationships or flows between entities in various fields, such as computer networks, social networks, logistical systems, and more. For example, in a transportation system, directed edges could represent the flow of vehicles from one intersection to another, while in a social network, directed edges could represent the direction of a friendship, or following relationship.
In a directed graph, we classify the vertices into two categories based on their connectivity with the edges - "in-degree" and "out-degree". The in-degree of a vertex represents how many edges point towards it, while the out-degree represents how many edges start from it.
Undirected graph
Undirected graphs are a common data structure used in computer science to represent a collection of nodes and the connections between them. In this type of graph, the connections between nodes are bidirectional, meaning that if node A is connected to node B, then node B is also connected to node A.
For example, consider a social network where each person is represented by a node, and the connections between nodes indicate friendships. In an undirected graph, if Person A is friends with Person B, then Person B is also friends with Person A.
Undirected graphs have various algorithms associated with them, including:
Depth-First Search (DFS): DFS can be used to find a path between two nodes, check connectivity, or detect cycles in a graph.
Breadth-First Search (BFS): BFS is useful for finding the shortest path between two nodes or discovering if a graph is bipartite.
Minimum Spanning Tree (MST): An MST is a subgraph that connects all the nodes with the minimum total edge weight, without creating any cycles.
Weighted graph
A weighted graph is a type of graph in which each edge is assigned a numerical value called a weight. These weights represent the "cost" or "distance" associated with traversing that edge. The main purpose of using weights in a graph is to model real-world scenarios more accurately, where different edges may have varying costs or importance.
In a weighted graph, paths between vertices are not just determined by the presence or absence of edges, but also by the cumulative weight of those edges. This allows for more precise analysis and decision-making, as it considers the actual cost of moving from one vertex to another.
The weights assigned to edges can represent various factors, such as distance, time, cost, or any other relevant metric, depending on the context of the problem being modeled. Weighted graphs find numerous applications in fields like transportation planning, network routing, optimization problems, and many others.
Tree
All trees are graphs, but not all graphs are trees. Trees is essentially undirected graphs that is connected and acyclic, meaning that there are no cycles or loops in the graph. Because of that we know that all trees have |V|-1 edges, one less than the amount of vertices in the graph(tree).
In a tree, each pair of vertices is connected by exactly one unique path. This means that there is only one way to travel between any two vertices in the graph. Additionally, there are no closed loops or circuits in a tree, ensuring that there are no repeated edges or vertices.
A tree has a hierarchical structure with a designated root vertex, from which all other vertices are connected through edges. Each vertex in the tree, except for the root, has exactly one parent vertex and zero or more child vertices. This parent-child relationship forms a branching structure, similar to the branches of a tree, which is why it is called a tree.
Tree structures:
Binary trees Vertices have no more than 2 children
Binary search-tree: Vertices have no more than 2 children. Parents are larger than every node in its left subtree and smaller than (equal) all nodes in its right subtree.
Minimum Spanning Tree (MST): An MST is a subgraph that connects all the nodes with the minimum total edge weight, without creating any cycles. If you instead connect all the nodes with the maximum total edge weight you will get a maximum spanning tree.
AVL-Trees: Stable binary-search tree. That means all AVL trees are binary search trees, but not all binary search tress are AVL trees. Keeps control over the height of each node, if two subtrees have a height difference < -1 or > 1 it will perform rotation(s) to stabilize the tree. This ensures a nice tree structure that has the minimal overall height it can have. This supports quick traversing.
Red/black trees The root is 'colored' black, the rest can be colored either red or black. Red nodes cant have red children. There has to be equally amont of black nodes in every path from the root to the leafnodes. This gives a stable tree structure, almost as stable as AVl and it requires less rotations.
