Skip to content

Simple, small sized implementation of select algorithms in C++

License

Notifications You must be signed in to change notification settings

kienme/Algorithms

Repository files navigation

Algorithms

Simple, small sized implementation of select algorithms in C++

1. Breadth First Search (BFS)

Used for traversing a graph

Algorithm

G is the adjacency matrix representing the graph.
'visited' array marks nodes as visited.

bfs(v):

  1. Mark 'v' as visited and print it
  2. For each node in G connected to 'v' and unvisited, mark node as visited and add it to the queue
  3. For each node 't' in the queue call bfs(t)

Wikipedia

2. Depth First Search (DFS)

Used for traversing a graph

Algorithm

G is the adjacency matrix representing the graph.
'visited' array marks nodes as visited.

dfs(v):

  1. Mark 'v' as visited and print it
  2. For each node 't' in G connected to 'v' and unvisited, mark node as visited and call dfs(t)

Wikipedia

3. Dijkstra's Algorithm

Used to find shortest path from a source to all other nodes

Algorithm

G is the adjacency matrix representing the graph (999 represents ∞).
'v' is the source node from which shortest distance is computed.
'visited' array marks nodes as visited.
'dist' holds shortest distances from the source node.

  1. Update distance array with distances from the source node (with values from the graph)
  2. Mark source node as visited
  3. Find nearest unvisited node 'u' from source
  4. For every node 'k' in the graph, check if distance from source to 'k' is less than sum of distances from source to 'u' and 'u' to 'k'
  5. If not, update distance to the new minimum
  6. Repeat from step 3 until all nodes are marked as visited

Wikipedia

4. Floyd-Warshall Algorithm

Used to find shortest paths for all pairs of nodes

Algorithm

G is the adjacency matrix representing the graph (999 represents ∞).
'dist' matrix holds the shortest distance values.

  1. Initialize dist with G
  2. Consider each node 'i' in the graph as an intermediate node
  3. For every pair of vertices 'j' and 'k', check if distance from 'j' to 'k' is shorter than sum of distances from 'j' to 'i' and 'i' to 'k'
  4. If not, update dist with the minimum value

Wikipedia

5. Kruskal's Algorithm

Used to find minimum spanning tree

Algorithm

G is the adjacency matrix representing the graph (999 represents ∞).
'parent' is used to keep track of connected nodes and check for loops.

  1. Find the shortest edge in the graph. Call the nodes 'u' and 'v'
  2. Check if 'u' and 'v' are connected by a common parent
  3. If not, select the edge, update the cost, and set 'u' as parent of 'v'
  4. Repeat from step 1 till n-1 edges are found (n is number of nodes in the graph)

Wikipedia

6. N-Queen's Problem

For a given NxN chess board, find the ways in which N queens can be placed so that no two queens share the same row, column or diagonal

Algorithm (Backtracking)

'col' array holds the column numbers(of successive rows) where queen can be placed.

nq(N, k):

  1. For given row 'k', check each column if queen can be placed
  2. If yes, update col and call nq(N, k+1)
  3. If last row has been reached, display 'col'
  4. Repeat step 1 for each row

Wikipedia

7. Prim's Algorithm

Used to find minimum spanning tree

Algorithm

G is the adjacency matrix representing the graph (999 represents ∞).
'visited' array marks nodes as visited.

  1. Mark first node as visited
  2. Find the nearest unvisited node from any of the visited nodes
  3. Mark it as visited
  4. Repeat from step 2 till all nodes are visited

Wikipedia

8. Subset Sum Problem

For a given set of integers, check if there exists a subset of it such that the sum of its integers equals a given value M

Algorithm

M is the value of the sum
'val' array holds the given integer set in ascending order, along with a large integer as the last element. This is to avoid checking for end of array
'selected' marks elements that are to be taken

sumofsub(sum, k):

  1. Mark element k as selected, and check if including it gives M
  2. If yes, display selected items
  3. Else, if including current and next element can give M, call sumofsub(sum+val[k], k+1)
  4. Check if leaving out current element can give M, call sumofsub(sum, k+1)

Wikipedia

9. Travelling Salesman Problem

For a given a list of cities and the distances between each pair of cities, find the shortest possible route that visits each city exactly once and returns to the origin city

Algorithm (Brute Force)

'tour_brute' and 'cost_brute' represent the final tour and cost respectively.
'v' array holds the route that is currently being tested.

tsp_brute(cur):

  1. If last node has been reached, find cost of current route
  2. If this cost is the smallest so far, copy 'v' to 'tour_brute'
  3. If not last node, for each of the remaining nodes:
    a. swap with current node in 'v'
    b. call tsp_brute(cur+1)
    c. restore values by swapping back

Wikipedia

About

Simple, small sized implementation of select algorithms in C++

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages