Graph
Last updated
Description
A graph is a data structure that represents how data is connected. Think of a social network like FaceBook or Twitter.
Graph terminology
Vertex - a node
Edge - the connection (line) between two vertices.
Adjacent - Vertices connected by an edge are "adjacent" to each other.
Types of graphs
Connected Graph
A graph where all vertices are connected to each other in some way. Otherwise it is a disconnected graph.
Directed graph
The edges indicate the direction of the relationship.
Directed Acyclic Graph (DAG)
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.
Some application areas of DAGs:
Routing in computer networks
Job scheduling
Data processing
Genealogy
Citation graphs
Weighted Graph
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.
Tree vs Graph
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
