graph-algorithm Questions
9
Solved
Among n persons,a "celebrity" is defined as someone
who is known by everyone but does not know anyone. The
problem is to identify the celebrity, if one exists, by asking the
question only of the fo...
Cimon asked 23/4, 2015 at 5:27
6
Solved
In the recursive DFS, we can detect a cycle by coloring the nodes as WHITE, GRAY and BLACK as explained here.
A cycle exists if a GRAY node is encountered during the DFS search.
My question is: W...
Faber asked 30/9, 2017 at 19:0
9
Solved
What does relaxation of an edge mean in the context of graph theory ? I came across this while studying up on Dijkstra's algorithm for single source shortest path.
Warfore asked 8/10, 2012 at 13:8
4
Solved
I know that one can detect cycles in direct graphs using DFS and BFS. I want to know whether we can detect cycles in directed graphs using Union-Find or not?
If yes, then how? and
If we can't, th...
Tourney asked 12/4, 2020 at 6:39
2
I am looking for the name of the following problem: traveling salesman problem (visit each city exactly once) but without returning to the start city and with visiting a given city at the end. In o...
Relict asked 10/12, 2013 at 17:47
2
Solved
I am referring to Skienna's Book on Algorithms.
The problem of testing whether a graph G contains a Hamiltonian path is NP-hard, where a Hamiltonian path P is a path that visits each vertex exactl...
Hiles asked 20/4, 2013 at 20:26
4
My goal is to find the shortest path (lowest cost) between given cities (vertices) connected with roads (edges).
Each road and each city has charge (cost) that has to be paid before entering that r...
Ytterbia asked 4/12, 2016 at 14:21
5
I need to find connected components for a huge dataset. (Graph being Undirected)
One obvious choice is MapReduce. But i'm a newbie to MapReduce and am quiet short of time to pick it up and to code...
Maclaine asked 20/5, 2012 at 21:30
4
Solved
I would like to know what is the problem name for TSP w/o considering the way of going back to starting point and what is the algorithm to solve this.
I looked into Shortest path problem but that i...
Premature asked 18/7, 2011 at 13:55
11
If you have a graph, and need to find the diameter of it (which is the maximum distance between two nodes), how can you do it in O(log v * (v + e)) complexity.
Wikipedia says you can do this using...
Boabdil asked 26/3, 2013 at 20:1
4
Solved
I have a list of objects (undirected edges) like below:
pairs = [
pair:["a2", "a5"],
pair:["a3", "a6"],
pair:["a4", "a5"],
pair:["a7", "a9"]
];
I need to find all components (connected nod...
Claresta asked 20/2, 2014 at 7:11
5
Solved
I'm looking for an efficient algorithm that is able to find an as random as possible Hamiltonian path in a bidirectional N*M grid.
Does anyone know where I can find, or how to go about constructin...
Checkbook asked 10/9, 2011 at 10:57
10
Solved
Given n nodes, if every node is connected to every other node (except itself) the number of connections will be n*(n-1)/2
How does one prove this ?
This is not a homework question. I have been aw...
Primogeniture asked 5/12, 2012 at 19:3
3
Solved
In an undirected random graph of 8 vertices, the probability of an edge being present between a pair of vertices in 1/2. What is the expected number of unordered cycles of length 3?
Here's how I th...
Quetzalcoatl asked 10/2, 2013 at 18:28
2
Solved
I tried to implement the Dijkstra's shortest path algorithm in JavaScript, and tested it with multiple examples.
I am using this graph to see how it would behave:
If I want to find the shortest pa...
Corycorybant asked 6/3, 2021 at 12:40
3
The time complexity for Dijkstra Algorithm using an array is O(V^2) and if priority queue is implemented, we can further improve the complexity to O(E log V). But what about its space complexity? I...
Alanealanine asked 14/6, 2018 at 11:24
2
I am trying to program a pathfinder on the worlds oceans. I have used an A* algorithm on a cell mesh containing land and water cells previously. But I think that a better solution will be to have c...
Wirework asked 3/7, 2014 at 13:29
2
I am trying to order an array of 3D coordinates by their order along a path. A sample:
points = np.array([[ 0.81127451, 0.22794118, 0.52009804],
[ 0.62986425, 0.4546003 , 0.12971342],
[ 0.506666...
Squashy asked 28/8, 2016 at 20:19
4
Solved
I've been using a little python script I wrote to manage debt amongst my roommates. It works, but there are some missing features, one of which is simplifying unnecessarily complicated debt structu...
Leyba asked 30/3, 2013 at 20:31
4
Solved
I am attempting to solve a coding challenge however my solution is not very performant, I'm looking for advice or suggestions on how I can improve my algorithm.
The puzzle is as follows:
You are g...
Cynewulf asked 6/9, 2021 at 13:58
5
Solved
I have an unweighted, connected graph. I want to find a connected subgraph that definitely includes a certain set of nodes, and as few extras as possible. How could this be accomplished?
Just in c...
Darrickdarrill asked 20/10, 2010 at 7:52
3
Solved
I know that Bellman-Ford Algorithm works for directed graphs. Will it will work for an undirected graph? It seems that with an undirected graph, it will not be able to detect cycles because paralle...
Thetis asked 9/2, 2013 at 5:54
7
Solved
What I need is a JavaScript implementation of pure mathematical graphs. To be clear I DON'T mean graph visualization libraries like sigma.js or d3.js.
The library I'm looking for would imple...
Glick asked 23/1, 2013 at 15:41
2
Solved
I am trying to implement a reasonably fast version of Floyd-Warshall algorithm in Rust. This algorithm finds a shortest paths between all vertices in a directed weighted graph.
The main part of the...
Sensual asked 20/11, 2021 at 21:35
16
Solved
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 w...
Azole asked 2/11, 2014 at 18:24
1 Next >
© 2022 - 2025 — McMap. All rights reserved.