Graphs

A graph is a non-linear data structure; a collection of nodes that connected by edges.

• undirected: edges has no direction or bidirectional.
• Directed: edges have arrow directions
• completed: all nodes are connected to all other nodes.
• connected: all nodes have at one edge.
• disconnected: at least one node have no edge
• Acyclic: tree
• cyclic: start and end the same node

traversals:

• Breadth first: similar to the tree structure
• Depth first: traversal uses a stack to visit all sub nodes.

Real world Graph data structures:

• GPS and mapping
• social networks
• airline traffics
• some customer recommendation algorithms

Graph DS implementations cheatsheet:

A graph data structure (V, E) consists of:

• A collection of nodes or vertices (V)
• A collection of paths or edges (E)

You can manage the graph data structures using the common operations mentioned below.

• contains - It checks if a graph has a certain value.
• addNode - It adds vertices to the graphs.
• removeNode - It removes the vertices from the graphs.
• hasEdge - It checks if a path or a connection exists between any two vertices in a graph.
• addEdge - It adds paths or links between vertices in graphs.
• removeEdge - It removes the paths or connections between vertices in a graph.