Graphs
A graph is a non-linear data structure that can be looked at as a collection of vertices (or nodes) potentially connected by line segments named edges.
Here is some common terminology used when working with Graphs:
-
Vertex - A vertex, also called a “node”, is a data object that can have zero or more adjacent vertices.
-
Edge - An edge is a connection between two nodes.
-
Neighbor - The neighbors of a node are its adjacent nodes, i.e., are connected via an edge.
-
Degree - The degree of a vertex is the number of edges connected to that vertex.
Directed vs Undirected
Undirected Graphs
An Undirected Graph is a graph where each edge is undirected or bi-directional. This means that the undirected graph does not move in any direction.
For example, in the graph below, Node C is connected to Node A, Node E and Node B. There are no “directions” given to point to specific vertices. The connection is bi-directional.
The undirected graph we are looking at has 6 vertices and 7 undirected edges.
Vertices/Nodes = {a,b,c,d,e,f}
Edges = {(a,c),(a,d),(b,c),(b,f),(c,e),(d,e),(e,f)}
Directed Graphs (Digraph)
A Directed Graph also called a Digraph is a graph where every edge is directed.
Unlike an undirected graph, a Digraph has direction. Each node is directed at another node with a specific requirement of what node should be referenced next.
Compare the visual below with the undirected graph above. Can you see the difference? The Digraph has arrows pointing to specific nodes.
The directed graph above has six vertices and eight directed edges
Vertices = {a,b,c,d,e,f}
Edges = {(a,c),(b,c),(b,f),(c,e),(d,a),(d,e)(e,c)(e,f)}
Complete vs Connected vs Disconnected
There are many different types of graphs. This depends on how connected the graphs are to other node/vertices.
The three different types are completed, connected, and disconnected.
Complete Graphs
A complete graph is when all nodes are connected to all other nodes.
Take a close look at each of the vertices in the graph above. Do you notice that each vertex is actually connected to every other node on the graph? That is what makes it a complete graph.
Connected
A connected graph is graph that has all of vertices/nodes have at least one edge.
In the visual above, this looks a lot more than what you are used to seeing. If you look closely at the different vertices of the graph, you will see that each node is connected to at least one other node or vertices. A Tree is a form of a connected graph. We will talk more about that in a bit.
Disconnected
A disconnected graph is a graph where some vertices may not have edges.
In the above visual, the disconnected graph shows that some nodes may not always be connected to other nodes or vertices of the graph. It is complelty possible to have standalone nodes or edges (also known as islands) in a graph data structure.
References
- Graphs Read full article