Graph is a data structure used to store relationships between elements.
Components:
- Vertices (nodes or points)
- Edges (arc or line)
Properties and types:
- Weighted or unweighted
- Directed or undirected
- Cycled or acyclic
- Planar or non-planar
- Biconnected
- Bipartite
- Networks
- Topology
- Sociology
- Lexical analysis
Many functions are implemented in special graph databases.
Relationships between nodes can be stored in:
- Matrixes
- Adjacency lists
Actually, tree is an acyclic connected graph. They were “invented” after trees.
| Graphs | Trees |
|---|---|
| in 1736 | in 1857 |
| by Arthur Cayley | by Leonhard Euler |
- Breadth-first
- Depth-first
- Cheney's algorithm for tracing garbage collection
- shortest path
- testing a graph for bipartiteness
- Maze generation algorithm
- Analysis of networks and relationships
- topological sorting
- Maze generation
Minumum spanning tree is when vertices are connected with minimal possible weight.
- Dijkstra
- All in pairs