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.
0
votes
1answer
4 views
time complexity of BFS using graph reperesentation
I was wondering what is the time complexity of breadth first search if I use an adjacency matrix or adjacency list, or edge list.is it same as their space complexity?.
0
votes
2answers
46 views
Efficient algorithm for hashing subgraphs?
Is there an algorithm for hashing subgraphs (consisting of the nodes and edges) of a given graph? Similarly, the particular graph I am talking about is a molecular network, and the intent of hashing ...
0
votes
1answer
39 views
Picking stick resting on top of each other using Topological order
i have an assignment in algorithm and have to write a pseudo code for the problem which is like Given set of n sticks resting on top of each other in some configuration. A class Stick that has a ...
0
votes
0answers
27 views
Network flow- Ford Fulkerson Algorithm
To find the Maximum Flow in a graph,why doesn't it suffice to only saturate all augmenting paths with the minimum edge capacity in that path without considering the back-edges? I mean,what is the ...
1
vote
1answer
30 views
Multiple agent pathfinding - no crossing paths
i'm trying to make multiple agents move at the same time to a specified point on a 2d map and have an upper limit for the maximum distance one agent can move.
If possible, all agents should move the ...
0
votes
2answers
18 views
How is the memory required for adjacency list representation is O(V+E)?
How is this statement valid?
"For both directed and undirected graphs, the adjacency-list representation has the desirable property that the amount of memory it requires is O(V+E)."
source: ...
4
votes
1answer
69 views
Finding all shortest paths from source to all vertices in a digraph
We are given a directed graph G (possibly with cycles) with positive edge weights, and the minimum distance D[v] to every vertex v from a source s is also given (D is an array this way).
The problem ...
3
votes
2answers
36 views
All pairs maximally disjoint paths algorithm
Suppose that there are multiple source destination pairs in an undirected graph. I want to generate disjoint paths for multiple pairs. What would be the complexity of such problem? Is there any ...
2
votes
2answers
55 views
All pairs shortest path lengths for undirected weighted sparse graph
What is the best algorithm for finding the all pairs shortest path lengths for undirected weighted sparse graph? Specifically, the weights are the distances between the nodes (and therefore positive). ...
0
votes
1answer
31 views
How can I find all path of a graph(no loop) with a fix end node?
I want to find all path start with node a and end with node b.
Now my solution is that start from a to exec DFS and select path ends with b.
The complexity is O(egde + node), can it be optimized to ...
0
votes
0answers
23 views
All-Pairs Shortest Paths In a Weighted Digraph, With O(V) space and O(V) Query Time
This is an exercise problem from Robert Sedgewick's Algorithms In C, Part 5.
Both Dijkstra's Algorithm and Floyd's Algorithm calculates all-pairs shortest paths of a weighted digraph properly, ...
2
votes
2answers
59 views
When will Dijkstra's algorithm and Prim's algorithm produce different outputs?
I know the difference between Prim's and Dijkstra's algorithm. The former produces a MST while latter gives shortest path from source to all node. Mathematically, these aren't the same, so we ...
0
votes
1answer
34 views
Good data structure or database to represent objects and transitions between objects?
I'm having trouble choosing a data structure to use to help identify resources and transitions between resources. After the graph is defined, I'd like to run analysis on the transformation between ...
0
votes
0answers
39 views
Implementation of BFS
I have implemented Breadth First Search. The adjacency matrix(adj[][]) represents the relationship among different nodes and the nodes are stored in nodes[].
However, I do not get the required ...
3
votes
1answer
76 views
Maximum euler subgraph of arbitrary oriented multigraph
To be more precise in problem formulation, let me reformulate it as a "cities" game. Plays two players. Player 1 says some city name, say Moscow. Player 2 now must say some city name, starting with ...
