Introduction to Graph Theory(Old) - Eishaaya/GMRDataStructuresTest GitHub Wiki
Graphs are considered by many computer scientists to be the most important and applicable data structure. They consist of edges and vertices, where two endpoint vertices make up an edge. A single vertex can have no edges, as many edges are there are vertices, or any number between. The interconnected network of vertices via edges make up a graph.
|
|
Mathematically, graphs just are pairs of values (edges). Take, for example, the above left image.
The nodes are A, B, C, D, E, F and their edges are:
- Node A goes to: B, D or C
- Node B goes to: A, C or E
- Node C goes to: A or B
- Node D goes to: A, E, or F
- Node E goes to: B or D
- Node F goes to: D
Graphs can either be undirected or directed; there is either a two-way connection between the vertices or a one-way connection, respectively. An undirected graph can have at most as many edges as the number of paired vertices in the graph. A directed graph can have at most n/2 edges, where n is the number of vertices.
|
|
Graphs are further characterized by their densities. A sparse graph has at most as many edges as the number vertices, and a dense graph has many edges relative to the number of vertices. When there are as many edges as possible, a graph is considered complete.
|
The connections within a graph can also be weighted, meaning there is a cost associated with each pair of vertices. A weighted graph can tell you how much each path to the same destination costs. This adds a level complication, because taking the path with the least amount of nodes is not necessarily the cheapest path, a concept that is important in pathfinding algorithms.
|
|
Graphs can be represented by either by an adjacency matrix or an adjacency list. Adjacent nodes are nodes with an edge between them.
Adjacency Matrix:
With a matrix representation for an undirected graph, nodes A and B are adjacent if the values at [row A, column B] and [row B, column A] are both 1. This is not the case for directed graphs. In a directed graph, node A can be adjacent to B without B having to be adjacent to A. The matrix always has dimensions [V, V], where V is the number of vertices.
|
|
Adjacency List:
With a list representation, each vertex holds a list of its neighbors.
|
A matrix representation is a great option when nodes are not frequently added or removed. The matrix would usually be a two-dimensional array, and since array access is fast, values can be quickly searched or changed. On the other hand, adding or removing a node from the graph would be inefficient. A new array with different dimensions would have to be created, and the values of the old array would have to be copied into the new array.
For a volatile graph, a list representation is a much better option. When nodes are added, they are simply added to the list of nodes, and when edges are created they are quickly added to the edge list of each node. Generally, lists are the better option overall:
| Add Vertex | Add Edge | Remove Vertex | Remove Edge | Search | |
| Adj. List | O(1) | O(1) | O(V + E) | O(E) | O(V) |
| Adj. Matrix | O(V^2) | O(1) | O(V^2) | O(1) | O(1) |
|
Finally, graphs can be searched in the same way as trees: breadth-first search and depth-first search. Searching is especially useful with pathfinding algorithms. The two algorithms discussed here are Dijkstra and A*.
|
Applications:
- Model the internet
- Airline connections
- City Road network
- Wireframe drawings in computer graphs
- Social networks
|