All Questions
64 questions
10
votes
1
answer
20k
views
Finding all paths from a given graph
I need to find all paths from a given graph. I can do that for now, however my recursive code is not efficient and my graphs are very complicated, hence I need a better algorithm.
...
- 103
9
votes
1
answer
8k
views
Prim's Algorithm using heapq module in python
Implementing Prim's with a \$O(m\log n)\$ run time using heaps, similar to Dijkstra heap implementation. Where \$n\$ is the number of nodes, and \$m\$ is the number of edges. Using the ...
- 105
8
votes
1
answer
4k
views
Flight combinations between two cities
I am trying to obtain all possible ways to go from a city A to a city B on a given day by plane, with a maximum of 2 stops.
I have as input a list of dictionaries:
...
- 183
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 ...
- 181
7
votes
2
answers
3k
views
Karger's min-cut algorithm implemented in python
I implemented Karger's algorithm with the function find_min_cut and it works, but I don't feel satisfied with the code I wrote.
...
user103312
7
votes
1
answer
8k
views
Find a triangle in a graph represented as an adjacency list
I have a graph represented as an adjacency list. I need to find a triangle in this graph. A triangle is a triple of vertices u, v...
user50833
7
votes
1
answer
2k
views
Topological sort
The algorithm works in steps:
Produce the graph in the form of an adjacency list
e.g. this graph
0 - - 2
\
1 -- 3
produces this adjacency list
...
- 179
7
votes
1
answer
2k
views
Topological Sort and Graphing in Python 3
I wrote a program for DFS traversal, topological sort, find all vertices, and has_cycle methods.
Can you please suggest more elegant and eloquent ways for this program?
(Perhaps better ways to ...
- 161
6
votes
1
answer
196
views
Longest carbon chain
My Code measures the longest path, not allowing cycles. For the example input below, the longest chain would be 4
Please can you review my code?
...
- 61
6
votes
2
answers
678
views
6
votes
2
answers
2k
views
Strongly connected component algorithm in Python 2.7
This is my implementation of Kosaraju's algorithm for detecting strongly connected components, post here for advice. Some special areas looking for advice,
Not sure if my current implementation for ...
- 3,493
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). ...
- 1,008
5
votes
1
answer
648
views
Social network broadcast message algorithm
Working on below problem and post problem and my current code. My idea is to always iterate from the minimal in-degree node which has not been visited before. Then based on this node to do a BFS. I am ...
- 3,493
5
votes
3
answers
7k
views
Pouring water between two jugs to get a certain amount in one of the jugs
I wrote a solution for a jug problem (given two jugs of water of different sizes find the steps needed to get specific amount of water in one of the jugs). I'm hoping for some input on my code. How ...
- 883
5
votes
2
answers
441
views
Dijkstra's Algorithm modified to take negative edge weights
In the following Python implementation I have used color coded vertices to implement the Dijkstra's Algorithm in order to take negative edge weights.
...
