Graph Algorithms are a sequence of well-defined steps that will solve a problem related to Graph Theory, where a Graph in this context is a collection of vertices ("nodes") and edges that connect these vertices.
1
vote
1answer
53 views
Minimum cops to catch all thieves in a given time
Given a Simple graph with N nodes and E edges. There are C thieves who can move on the graph with any speed (0 to infinite). We have to find the minimum number of cops required to catch all thieves in ...
0
votes
2answers
53 views
Complexity of a pattern algorithm
I have been trying to find an algorith to determine the complexity of a pattern with this coordinate system on the left and the possible lines on the right handside of the picture:
I am trying to ...
0
votes
1answer
31 views
Python Serializing/Deserializing a binary tree
I'm trying to implement a serializing/deserializing algorithm in python for binary trees.
Here's my code:
class Node:
count = 1
def __init__(self, value):
self.value = value
...
1
vote
1answer
55 views
Complexity of Prims using Array
The complexity of Prims Algorithm using Array and Adjacency List is:
V^2 + V + 2E + E = O(V^2)
But, I can't recall why E.
2
votes
1answer
168 views
How to set the parameters of Barabási model
I would like to use the Barabási–Albert (BA) Preferential Attachment model in order to generate graph with specified properties.
Numbers of vertices and edges: V(g)=20, E(g)=72, respectively. Vectors ...
8
votes
3answers
7k views
Why is depth-first search claimed to be space efficient?
In an algorithms course I'm taking, it's said that depth-first search (DFS) is far more space efficient than breadth-first search (BFS).
Why is that?
Although they are basically doing the same ...
1
vote
1answer
41 views
Bellman-Ford Algorithm Space Complexity
I have been searching about Bellman-Ford Algorithm's space complexity but on wikipedia Bellman-Ford Algorithm and it says space complexity is O(V). on this link it says O(V^2) . My question is; what ...
1
vote
1answer
60 views
Shortest paths with with a distance function that is dependent on shortest paths?
I would like to compute the shortest paths from every node to every other node in a directed graph.
The inital distance from every node to every adjacent node is given.
However my distance function ...
1
vote
2answers
15 views
Shortest way to find the focused point in an auto focus algorithm
I'm writing an algorithm for auto focus. For that I'm using a stepper motor which has 3318 steps for focus.
To find the focus, after every frame from the camera I'm taking the statistics and ...
0
votes
0answers
43 views
Implimention of A* algorithm for multiple goal of Maze
I have a maze which has multiple exit points. I have to find shortest path for nearest exit from start point. I am applying A* Shortest path algorithm with dynamic heuristic . for every cell, I am ...
-1
votes
0answers
27 views
Another dynamic programming (like fence painting )
I have a interest dynamic programming problem
We are writing a small tool for warehouse, which is calculating the minimum picking distance in minimum time.
We have N orders and M pickers. Each ...
0
votes
0answers
41 views
pythonw.exe has stopped working
I'm implementing Kosaraju’s two-pass algorithm that can calculate strongly connected components in a directed graph.
I can get the correct result with small input data, but when the input data is ...
1
vote
1answer
25 views
What is an algorithm to find the circuit with max weight in a directed graph?
First problem was that i couldn't find an algorithm that,given an directed graph as input, gives as output a list of all cycles present in the graph. (This problem should be NP-complete).
After ...
0
votes
0answers
33 views
Graph building algorithm given an infinite walk
I need help writing a resilient, mapping (graph building) algorithm. Here is the problem:
Imagine you have a text oriented virtual reality(TORG/MUD) where you can send movement commands (n, s, w, e, ...
4
votes
1answer
141 views
Dijkstra's Algorithm - complexity
I have a certain problem understanding the complexity of the Djisktra algorithm and hope someone can correct me.
For my example I took a complete graph with n vertices.
You pick a starting vertex, ...
-2
votes
4answers
1k views
Chess Checkmate Algorithm Complexity
I was wondering what the complexity of a graph search algorithm would be for determining a checkmate in chess in Big O notation.
1
vote
1answer
52 views
Directed weighted graph shortest path with obligatory nodes to pass
Hello i'm trying to find the best algorithm to solve this problem.
I have a a graph that i must find the shortest path between Start and End node specified but that must pass on specific user input ...
1
vote
1answer
20 views
What is the correct vertex order of Prim algorithm from this graph?
I want to know the vertex order of the Prim algorithm from this graph:
My answer is {a,c,b,e,f,g,d}, but others said {a,c,b,e,d,f,g} or {a,c,d,e,b,f,g}.
Which answer is correct?
8
votes
1answer
5k views
Efficiently find all connected induced subgraphs
Is there an efficient(*) algorithm to find all the connected (induced) subgraphs of a connected undirected vertex-labelled graph?
(*) I appreciate that, in the general case, any such algorithm may ...
0
votes
1answer
102 views
modification of dijkstras based on cost and quality
I have a graph with each edge having cost and quality. I need to modify the dijkstras to find the path with the highest quality - but if the quality of two path is the same, then the path with the ...
-1
votes
0answers
60 views
Travelling salesman (TSP) in java with different starting and end destinations visiting all the nodes exactly once
I am looking for recommendation on which algorithm makes sense for my problem. I'll have 50-100 places in the given city/state with latitude and longitude, the target is to find an optimal way from ...
8
votes
2answers
5k views
VF2 algorithm steps with example
Can someone explain the steps of the VF2 algorithm for graph isomorphism in simple words? I am learning this algorithm, but it is harsh without a working example. Can someone lead me the right ...
4
votes
1answer
54 views
Computing a company's shareholders ownership percentage
I have a graph that contains two types of nodes: Companies and Persons.
A Company node has a list of edges that represent Shareholders. A Shareholder has a percentage of shares and is either a ...
0
votes
0answers
44 views
Choosing a particular route for a shuttle vehicle upon demand
I'm trying to solve a problem where I have no idea what algorithm is to be used here to get the optimized answer. The problem is like this...
Consider there are 10 shuttle vehicles and 2 different ...
1
vote
2answers
60 views
Why do I get same results directly within same run in second time without run random function in it in Python?
I write a KargerMinCut function in which I have written a random function in Python, but I get the same result within the same run. If I restart the function, different results printed.
Here's the ...
0
votes
1answer
43 views
Finding right triangle coordinates in binary array
Say I have an MxN binary matrix. It is not necessarily sparse. I'm interested in finding the coordinates of the apexes of all of the right triangles in the array. By right triangle, I mean: pretend ...
1
vote
2answers
24 views
Longest Increasing Sub-sequence such that last-First element in LIS is maximum
How to find the difference between the last and first element of the longest increasing sub-sequence such that value of (last element - first element) in LIS is maximum ?
2
votes
5answers
6k views
What is time complexity of BFS depending on the representation of the graph?
I was wondering what is the time complexity of BFS, if I use:
an adjacency matrix
adjacency list
edge list
Is it same as their space complexity?
0
votes
1answer
130 views
Shortest path in a grid collecting coins [closed]
It's holiday season. A mall is empty except of air, money, and a very clever thief that is you.
The mall consists of n floors. Each floor can be represented as a rectangular 2D grid. All floors have ...
0
votes
1answer
30 views
CTCI 4.3: Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth
I'm solving this problem with Ruby, and I used a modified DFS algorithm to do it. The idea is that, every time DFS has to look at adjacent nodes, then it's looking at the children and therefore that's ...
18
votes
12answers
7k views
Check if the given string follows the given pattern
A friend of mine just had his interview at Google and got rejected because he couldn't give a solution to this question.
I have my own interview in a couple of days and can't seem to figure out a way ...
-3
votes
1answer
78 views
Floyd-Warshall algorithm - shortest path - save paths index to array
I'm implementing a Floyd-Warshall algorithm for symmetrical, undirected graph. At the moment, I have calculated the best path for each connection point. My problem is that I want to save index points ...
0
votes
4answers
49 views
defining a circle by algorithm
I've got a 100px*100px image
Gotta draw some filled circles with random position and radius.the problem is not the random stuff.
I just don't know the algorithm to define a circle with position(x,y) ...
1
vote
1answer
48 views
How many cells will have finite values
I encountered one programming question.
Consider I have N cells.These cells can have some integer value or expression.
There can be T number of iterations.In every iteration ,some cells can be ...
1
vote
1answer
39 views
How to solve this optimally?
I have a tree of n vertices n<=10^5 where each vertex has a score[i] and q queries q<=10^5
Each query has two parameters u and L, I need to find
sum(score[i]) for all i where lca(i,u)=u and ...
1
vote
1answer
25 views
Identifying paths between nodes on a graph, whilst finding potential loops
Lets say I have a graph like the following:
It is directed, and can also have cycles. If I wanted to find all the possible routes from node 0 to node 9, I have found that I could use a depth-first ...
1
vote
0answers
25 views
How to output the top $k$ “diverse” strings from a set of $n$ strings
Suppose I am given n strings of equal length. I want to output a subset of them of size k such that they are as diverse as possible, for example, if n=3 and k=2
Strings: AAABC, AAACB, XYZWR
I would ...
0
votes
0answers
22 views
best way to maximum utilization of print sheet by placing irregular shape
I am developing the maximum utilization of print sheet since long days. I have learnt many things about this but I am not getting any suitable algorithm or sample project that will help me to make ...
0
votes
3answers
44 views
Changing the value of a Boolean Function in Python
I want to set the default value of a boolean function to be False and want to change it to True only for certain values of the input in between the code. Is there a way to do it?
I'm trying to write ...
0
votes
0answers
20 views
Representing very large road network
I need to create a (very large) graph to represent a real world road network. In this road network, I have about 20M road junctions and 25M roads. Some roads are one-way. In order to support long ...
0
votes
0answers
46 views
Understanding the minmax algorithm of tic-tac-toe (without recursion)
I'm trying to write a minimax algorithm for a tic-tac-toe at Python.
I don't need help with the code, just with the algorithm... :-)
I'm trying to do it without recursion, and to understand it better ...
0
votes
1answer
1k views
Algorithm for minimum diameter spanning tree
Given a undirected and connected graph G, find a spanning tree whose diameter is the minimum.
3
votes
3answers
19k views
Time Complexity of the Kruskal Algorithm?
I am calculating time complexity for kruskal algorithm like this (Please see the algorithm in the Image Attached)
T(n) = O(1) + O(V) + O(E log E) + O(V log V)
= O(E log E) + O(V log V)
as |E| &...
0
votes
0answers
24 views
Weighted A* versus A*
With the A8 and weighted A*(without allowing re-expansion of states) algorithms, will weighted A* never expand more states than regular A*?
Can you explain, the difference in expansion please(...
3
votes
1answer
571 views
Dijkstra's shortest path algorithm won't work
I have a graph with positive edge weights and positive node weights. The length of a path is defined as the sum of all the edge weights along the path, plus the maximum node weight encountered along ...
-2
votes
1answer
22 views
PageRank - How is a link defined?
I am trying to learn more about the PageRank algorithm. I have a task to implement a wikipedia search engine implementation using PageRank. I wanted to know how a links are defined. So if Page A has a ...
1
vote
1answer
37 views
Optimal clusterization
There is a graph (E,V). For each edge (i,j), there is a payment P[i,j] which may be positive, zero, or negative. We divide the vertices by clusters. Each time two neighbour vertices v1 and v2 belong ...
1
vote
1answer
46 views
Space complexity of BFS
Here is a code snippet from BFS implementation-
public static void findShortestReach(LinkedList<Integer>[] adjList,int start,int nodes)
{
int[] level=new int[nodes]; //keeps track of ...
1
vote
1answer
55 views
Algorithm: How to re-arrange a time-range event (interval) list based on wether time events overlap, faster than O(n^2)?
Let's say I have an array of time ranges like so:
[
{ name: 'A', startTime: '10:15', endTime: '11:15'},
{ name: 'B', startTime: '10:45', endTime: '14:15'},
{ name: 'C', startTime: '15:35', ...
0
votes
2answers
92 views
How can we find maximum spanning tree in complete graph
Given an array of n positive integers, how can we find maximum spanning tree in complete graph, considering weight of edge (i, j) = gcd(a[i], a[j])?
I know one solution with complexity O(n^2), but n&...
