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.
4
votes
1answer
40 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
26 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
42 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
21 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?
1
vote
1answer
123 views
Shortest path in a grid collecting coins [on hold]
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
24 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 ...
6
votes
1answer
5k views
Efficiently find all connected 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 ...
-3
votes
2answers
64 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
47 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
47 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
33 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
38 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
22 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
24 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
43 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
43 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
23 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
566 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 ...
1
vote
0answers
16 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?
-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
36 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
votes
0answers
20 views
Dinic's algorithm in O(mn)
Teacher told us that if we don't send flow through reverse edges in Dinic's algorithm, then it runs in O(mn). I didn't understand why this should be true, so I tried to find a proof but I couldn't ...
1
vote
1answer
43 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
53 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
84 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&...
0
votes
3answers
30 views
Why does Kruskal's algorithm find the minimum spanning tree if it's greedy?
Why does Kruskal's algorithm find the minimum spanning tree if it's greedy? Isn't a minimum spanning tree a global optimization problem? Isn't the point of being greedy is that there is a chance you ...
1
vote
1answer
20 views
Finding Min Distance From Start Node to Other Nodes in DFS Tree and Their Back Edges
The problem is this:
Find DFS and compute distance from start node to each of the other
nodes in the graph, assign each of the nodes v their distance from start node
Next find the min of each of the ...
3
votes
1answer
49 views
Assigning jobs to workers
There are N plumbers, and M jobs for them to do, where M > N in general.
If N > M then it's time for layoffs! :)
Properties of a job:
Each job should be performed in a certain time window which ...
1
vote
2answers
30 views
Do connected graphs with more than N-1 edges always contain connected graph with N-1 edges?
We know that:
If we have N vertices
To build a connected undirected graph, you'll need at least N-1 edges.
Let M be the set of possible connected undirected graphs with N-1 edges.
...
0
votes
0answers
7 views
Difference between GAS model and BSP model
I know Pregel's graph computation framework is based on BSP and GraphLab is based on GAS. What is the difference between BSP and GAS? and Advantage and disadvantage of each one?
1
vote
0answers
20 views
Partitioning with constraints of edge weighted graph
I have an edge weighted connected graph. It is not a directed one. My task is to remove a few edges so that the graph become divided into at least two half and the sum of weights of the removed edges ...
0
votes
0answers
29 views
How do I implement breadth first search for a graph using type string vectors?
okay, so I get the mechanics of what breadth first search is. The problem is, I cannot figure out what am I to use as an iterator for the adjacency list?
Here's a snippet of my class code:
class ...
3
votes
3answers
79 views
Shortest path in graph where cost depends on the history of traversing
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 road/...
0
votes
0answers
54 views
Unique Topological Sort for DAG with Multiple tsort Solutions
I have a DAG (directed acyclic graph) which has more than one valid topological sorting. I'm looking for a way to sort it topologically and always get the same, well defined result.
For example take ...
1
vote
1answer
54 views
Is there any algorithm to compute edit distance between two graphs including same nodes?
First, I know there has been a lot of works to compute the edit distance between two graphs. But most of the GED algorithms are applied in general cases.
Now considering my case, there are two graphs ...
1
vote
1answer
82 views
Shortest-path algorithm: multiple source, closest destination
Algorithms like the Bellman-Ford algorithm and Dijkstra's algorithm exist to find the shortest path from a single starting vertex on a graph to every other vertex. Their multiple source version can be ...
2
votes
2answers
472 views
Parsing an input file to create a directed graph C++
So I'm starting a project on directed graphs and topological sorting. I'm looking for the most efficient way to parse an input file of courses in the form:
COURSE_1 COURSE_2
where COURSE_1 is ...
0
votes
0answers
19 views
jGraphT library for java
I'm trying to run Dijkstra's algorithm on a graph. I need to read a graph modelling language (gml file into my Graph, Vertex and Edges Data structures).
The gml file is somewhat like this
graph
[
...
0
votes
1answer
229 views
Pseudocode for BFS(from The Algorithm Design, 2nd Ed.) confusion? [closed]
I need help with BFS pseudocode from The Algorithm Design Manual 2nd Edition, Skiena.
Line that says process vertex u as desired
and same thing but with edge(s) process edge (u, v) as desired
How ...
2
votes
1answer
140 views
Floyd-Warshall Algorithm that works with negative cycles [closed]
How can the Floyd-Warshall algorithm be modified to find the shortest path of any negative cost cycle of a directed graph that maintains O(V^3) time complexity?
2
votes
3answers
2k views
Depth first search list paths to all end nodes
Hi I have a tree in which I would like to get paths from the initial (root) node to all leaves.
I found several algortithms that list (all) apths betwenn any given two nodes within a graph (for ...
1
vote
1answer
82 views
Hungarian Algorithm - Arbitrary Choices
I've looked at several explanations of the Hungarian Algorithm for solving the Assignment Problem and the vast majority of these cover very simplistic cases.
The most understandable explanation I've ...
3
votes
2answers
2k views
Generate a scale-free network with a power-law degree distributions
I'm trying to generate couples of scale-free networks having:
degree distributions following power laws with the same exponent
the exact same number of nodes.
I need to build at least 60 of those ...
