A data structure that consists of a set of nodes (vertices) and a set of edges that relate the nodes to each other. The set of edges describes relationships among the vertices. As a formal definition, a graph G is defined as follows:
G=(V,E) V(G): a set of vertices E(G): a set of edges (pairs of vertices)
Types of Graphs
Directed graph
- all the edges are directed
- Edge (u,v) goes from vertex u to vertex v,
- e.g., route network
Undirected graph
- all the edges are undirected
- Edge (u,v) = edge (v,u)
- e.g., flight network
Applications of Graphs
- Electronic circuits
- Transportation networks
- Highway network
- Flight network
- Computer networks
- Local area network
- Internet
- Web
Trees vs graphs
Trees are special cases of graphs!!
Graph terminology
- Adjacent nodes: two nodes are adjacent if they are connected by an edge
- Path: a sequence of vertices that connect two nodes in a graph
- Complete graph: a graph in which every vertex is directly connected to every other vertex
- What is the number of edges in a complete directed graph with N vertices? N * (N-1)
- What is the number of edges in a complete undirected graph with N vertices? N * (N-1) / 2
- Weighted graph: a graph in which each edge carries a value
Related Posts
- Queue Implementation in C++
- Binary Search Trees and Data Structure
- Bucket Sort (Bin Sort) with Example
- Quick Sort Algorithm with Graphical Explanation
- Heap Sort with Graphical Explanation
- Merge Sort with Graphical explanation
- Graphical Path Finding System using Dijkstra Algorithm
- Applications of Dijkstra Algorithm
- The OpenGL Programming Guide
- Introduction to Recursion in C++
If you enjoyed this article, please consider sharing it!
