A graph is a data structure that represents how data is connected. Think of a social network like FaceBook or Twitter.
- Vertex - a node
- Edge - the connection (line) between two vertices.
- Adjacent - Vertices connected by an edge are "adjacent" to each other.
A graph where all vertices are connected to each other in some way. Otherwise it is a disconnected graph.
A connected graph. All vertices are connected to each other in some way
A disconnected graph. Here Fred is not connected to any other vertex.
The edges indicate the direction of the relationship.
If we follow the direction of the edges and do not find any loops, then there are no directed cycles. The graph formed is a directed acyclic graph.
A DAG is always topologically ordered. This means that for each edge in the graph, the start vertex of the edge occurs earlier in the sequence than the ending vertex of the edge.
The graph in the directed graph section above is NOT a DAG, because it contains a cycle (a loop). Starting at any node, n, and following the edges will always bring us back to n.
The following directed graph is a DAG, because it contains no cycles. Following the path from any node, n, will never lead back to n.
Vector version of Image:Tred-G.png, Public domain, via Wikimedia Commons
Some application areas of DAGs:
- Routing in computer networks
- Job scheduling
- Data processing
- Citation graphs
A number (weight) is assigned to each edge. These numbers could represents things such as distance, or costs, or whatever is appropriate for the problem. Weighted graphs are used in shortest path problems such as the traveling salesman problem.
Dijkstra's Algorithm is a famous algorithm to solve the shortest path problem.
Attribution: Tore.opsahl, Public domain, via Wikimedia Commons
A tree is a type of graph. All trees are graphs, but not all graphs are trees.
The difference between a tree and a graph is:
- A graph may have vertices (nodes) that are not connected.
- A graph my contain cycles