A graph is a non-linear data structure consisting of a finite set of vertices and edges connecting them.
A path in a graph is a sequence of vertices such that every pair of neighboring vertices is connected by an edge. In other words, for every , there is an edge between and .
The first vertex is called the start of the path, and the last vertex is called the end of the path.
Examples from the figure:
The length of a path is the number of edges in it.
A cycle is a path that starts and ends at the same vertex, that is, .
Example from the figure:
A connected component is a set of vertices such that any vertex in the set can reach any other vertex in the same set using graph edges.
For the graph in the figure, the connected components are:
Edges can be directed or undirected.
If an edge is undirected, then we can move both from to and from to .
If an edge is directed, then movement is allowed only from to .
An edge may have a weight .
The weight represents the cost of using that edge. For example, in a road network, vertices may represent cities, edges may represent roads, and the weight may represent the cost or distance of traveling along that road.
There may be more than one edge between the same pair of vertices. Such edges are called multiple edges or parallel edges.
A vertex may also have an edge to itself. Such an edge is called a loop.
An undirected graph is a graph in which all edges are undirected.
A directed graph is a graph in which all edges are directed.
An acyclic directed graph is a directed graph that contains no cycles.
A connected graph is a graph in which every vertex can reach every other vertex.
In other words, it consists of exactly one connected component.
A tree is a connected undirected graph with no cycles.
Important properties of a tree:
A bipartite graph is a graph whose vertices can be divided into two groups such that every edge connects a vertex from one group to a vertex from the other.
So there are no edges connecting two vertices from the same group.
A binary tree is a tree in which each vertex has at most two children.
Each child is itself the root of another binary tree.
In each vertex, we usually store the data and pointers to its parent and children.
There are three common ways to traverse a binary tree:
Algorithm:
Traversal result:
Algorithm:
Traversal result:
Algorithm:
Traversal result:
struct Node {
Node* parent;
Node* left;
Node* right;
int value;
Node(Node* parent_, int value_) : parent(parent_),
value(value_),
left(nullptr),
right(nullptr) {}
};
void printPreOrder(Node* node) {
if (node == nullptr) {
return;
}
cout << node->value << " ";
printPreOrder(node->left);
printPreOrder(node->right);
}
void printInOrder(Node* node) {
if (node == nullptr) {
return;
}
printInOrder(node->left);
cout << node->value << " ";
printInOrder(node->right);
}
void printPostOrder(Node* node) {
if (node == nullptr) {
return;
}
printPostOrder(node->left);
printPostOrder(node->right);
cout << node->value << " ";
}