Graphs

Graphs

non-linear data structure that can be looked at as a collection of vertices (or nodes) potentially connected by line segments named edges.

Terminology

  1. Vertex : also called a “node”, a data object that can have zero or more adjacent vertices.
  2. Edge : a connection between two nodes.
  3. Neighbor : The neighbors of a node are its adjacent nodes.
  4. Degree : the number of edges connected to that vertex.

Undirected Graphs

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.

Directed Graphs (Digraph)

A Directed Graph also called a Digraph is a graph where every edge is directed.

image

Complete vs Connected vs Disconnected

  1. Complete Graphs: when all nodes are connected to all other nodes.
  2. Connected: has all of vertices/nodes have at least one edge.
  3. Disconnected: when some vertices may not have edges.

Acyclic vs Cyclic

cycle: is when a node can be traversed through and potentially end up back at itself.

  1. Acyclic Graph: a directed graph without cycles.
  2. Cyclic Graphs: is a graph that has cycles.

Weighted Graphs

A weighted graph is a graph with numbers assigned to its edges. These numbers are called weights.

examples of graphs in use:

  1. GPS and Mapping
  2. Driving Directions
  3. Social Networks
  4. Airline Traffic
  5. Netflix uses graphs for suggestions of products

 

Get back to EMAM’S HOMEPAGE

I have created this page as a part of my project using Github, Please visit my profile, I will be more than happy to hear from you all.                       © Emam Shararah 2021