Coding Musings

Trying to share some code ideas

logo

Month: January 2018

Testing for Unconnected Components in a Graph

Testing for Unconnected Components in an Undirected Graph

With a graph structure it is possible that parts of the graph will not be connected to each other.  An example of this would be with social networks, not all users are friends with other users.

The code will find the total number of connected components of the graph, or graph parts in an undirected graph.

See code below.

Read More

Finding an Exit from a Maze

Finding an Exit from a Maze using undirected graphs.

We can think of a maze as a rectangular grid of cells with paths between adjacent cells. If we want to find if there is a path from a given cell to a given exit from the maze, where the exit is represented by a cell, you can represent the maze as an undirected graph.

The nodes of the graph are cells of the maze, and two nodes are connected an undirected edge if they are adjacent and there is no wall between them. Therefore we can surmise we just need to see if a path, series of edges connecting the nodes, to determine if the two nodes are connected.

See code below.

Read More

Powered by WordPress & Theme by Anders Norén