Introduction to Graph Terminology - Eishaaya/GMRDataStructuresTest GitHub Wiki
What Makes a Graph?
A graph is considered by many computer scientists to be the most important and applicable data structure. A graph can represent many data structures such as a linked list or a tree. You can think of a graph as a more flexible version of those data structures. The terminology that you have used to make those prior data structures are Nodes and the connections between those nodes. For example, the connections could be a Next or Previous connection in a linked list or a Parent connection in a tree. Nodes are now called Vertices and the connections between them are now called Edges.
An Edge is made up of two vertices that connect to each other. Edges allow us to represent the connections between vertices in our graph.
A Vertex is simply a node representing some value and can have as many edges as they want, including no edges.
Directed vs Undirected
The main difference between a directed and an undirected graph is how the edges are represented. With an undirected graph the edges do not have a direction, meaning that an edge between vertex A and vertex B goes both ways. For example, if I am looking at vertex A, I can travel to vertex B and vice versa. In comparison, in a directed graph the edges have a direction, so if I have an edge from vertex A to vertex B, then B will not be able to travel to vertex A, but vertex A can travel to vertex B. A way to think about it is in a node class for a tree that does not have a parent connection. A parent can travel to that node (which is a child), but the child can not travel to the parent.
Weighted vs Unweighted
The main difference between a weighted and an unweighted graph is again how the edges are represented. This time it's not about which vertex can go to which vertex, but the cost/weight/distance to use the edge between the two vertices. These attributes are more important in pathfinding, because the shortest path problem relies on minimizing the cumulative weight from the start vertex to the end vertex.
Acyclical vs Cyclical
The difference between an acyclical and cyclical graph is if there is a cycle within the graph. An example of an acyclical graph would be a tree where the node class does not have a parent direction, allowing you to only traverse down the tree and not back to any of the prior nodes. An example of a cyclical graph is a circularly linked list where you can traverse back to the head node.
<-- Previous | Next -->