DS & A Series — Graphs, BFS, DFS: Implementation & Insights

  1. Trees — An undirected graph with no weighted edges. There are always N nodes with N-1 edges.
  2. Rooted Tree — A tree with a designated tree node, where every edge either points away from or points toward the root. Trees where the direction moves out from the root node, the tree is displaying arborescence. When the direction moves in towards the root node, the tree is displaying anti-arborescence.
  3. DAGS (Directed Acyclic Graph) — Directed graphs with no cycles. A type of DAG is a bipartite graph. Bipartite graphs are graphs whose vertices can be split into two groups U and V such that every edge connects U and V. This means that the graph is two colorable or does not have an odd length cycle.
  4. Complete Graph — A graph that has a unique edge between all vertices.

What are the types of problems that are represented/solved by graphs?

Graphs can be used to solve a whole host of problems, the study of graphs and their algorithms is called Graph theory. The types of problems solved with graphs are the following:

  1. Shortest Path — The shortest distance between two nodes on a graph. Does google maps ring a bell?
  2. Connectivity — If a path exists from one node to another.
  3. Strongly Connected Components — If a group of vertices are all connected with each other. Social groups can be represented through strongly connected components, what is a tightly knit group of friends but a bunch of vertices that have edges between each other? 😂
  4. Traveling Salesman Problem — Given a list of cities, what is the shortest path where you visit every city starting from a source and returning to that source?
  5. Bridges — Edges when removed increase the number of connected components.
  6. Articulation Points — Vertices when removed increase the number of connected components.
  7. Minimum Spanning Tree — Finds the minimal subtree that connects all vertices of a graph.
  8. Network Flow — Finds the max flow that you can send through a system by constructing a max-flow graph. Starts from a source node and moves towards a sink node.

Graph Implementation

  1. Constructor — The first thing to do is create a class called Graph and initialize it with an adjacency list or matrix. The adjacency list is usually either a map or an ‘object’ in JS and the matrix is an array of arrays. If you’re using a matrix you’re going to have to instantiate the graph with the number of nodes you wish to have in the graph.
Undirected Edge (Adjacency List)
Directed Edge (Adjacency Matrix)
Remove Vertex (Adjacency List)
Remove Matrix (Adjacency Matrix)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store