All Questions
64 questions
2
votes
1
answer
73
views
Clique Connect: minimum spanning tree
Problem Statement
You are given a weighted undirected graph G with N vertices, numbered 1 to N. Initially, G has no edges.
You will perform M operations to add edges to G. The i-th operation (1≤i≤M) ...
- 140
0
votes
1
answer
60
views
Performance optimization of traveling salesman like issue
I need help optimizing the performance of this, which is essentially similar to the traveling salesman problem, with the addition that I want to make the graph complete first, with the weight of the ...
- 38.9k
2
votes
0
answers
194
views
Backtracking graph algorithms for a word puzzle in Python
Motivation
Recently, Buzzfeed released a browser-based puzzle game called "Pyramid Scheme." It is available at the following link. The puzzle in an initial state looks like this:
To solve ...
- 163
6
votes
1
answer
238
views
Python code to contract (shrink) a graph
To better understand a paragraph, I implemented the intent behind the paragraph. In this case, it was a formal definition of a graph contraction:
Suppose we have an undirected graph G and X ⊆ V(G). ...
- 68.9k
8
votes
1
answer
2k
views
Recursive and iterative implementation on Kosaraju algorithm
Kosaraju algorithm is mainly phrased as two recursive subroutines running postorder DFS twice to mark SCCs with linear time complexity O(V+E) below,
For each vertex \$u\$ of the graph, mark \$u\$ as ...
- 7,189
3
votes
2
answers
165
views
Finding Number of Objects in Image
I wrote a program that, given a 2D array representing pixels in a birds eye view image, it returns the number of Objects in the image.
Pixels that are connected in the up, down, left, and right ...
- 112k
5
votes
2
answers
13k
views
Constraint Programming: Map color problem
I've written some python code to solve the map coloring problem. In my code, I represent the problem using Territory and MapColor...
2
votes
0
answers
71
views
Dijkstra from scratch
I implemented the Dijkstra algorithm from scrath and wonder if I can save some code? The whole algorithm is here.
n is the number of nodes, and m the number of edges. 1 ≤ 𝑛 ≤ 10^4, 0 ≤ 𝑚 ≤ 10^5, 𝑢 ...
- 345
3
votes
0
answers
116
views
Modified Tarjan's algorithm for reporting the edges within the strongly connected component
As described in his paper, Tarjan's algorithm reports only the nodes of the strongly connected components. For my use, I would also like to also have the edge list of the components (so that I can run ...
- 537
4
votes
2
answers
2k
views
Floyd-Warshall Path Reconstruction
Below is the implementation for the Floyd-Warshall algorithm, which finds all-pairs shortest paths for a given weighted graph.
The function floyd_warshall takes a ...
- 34.7k
3
votes
0
answers
235
views
Breadth First Search Python Implementation
I have the below implementation of the BFS algorithm, in which I've used OrderedDict instead of a list or ...
- 10.7k
1
vote
0
answers
378
views
Directed graph and Dijkstra algorithm using heap
I have implemented directed graph and Dijkstra algorithm using heap in Python.
I first implemented an abstract base class WeightedGraph, of which ...
- 44k
3
votes
1
answer
450
views
friendship program using graph type python/algorithm
I have created a program but I feel the def common(friendships, person1, person2) function can be more efficient, if anyone has any good idea how I can improve it I ...
- 10.5k
4
votes
1
answer
805
views
Python implementation of Kahn's Algorithm
Please provide any suggestions on the below code for Kahn's algorithm. Can it be implemented in a better manner, or be improved:
...
- 35k
5
votes
1
answer
1k
views
Tarjan's Algorithm Python Implementation
I'm planning to use Tarjan's algorithm for a program in which I would be processing a file, converting the processed data to a dictionary, doing a topological sort on that dictionary (using this ...
- 68.9k