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
11 views
Algorithm for determining number of discreet graphs in a dataset
I have a dataset that contains vertices and the other vertices that they are connected to. This data set represents an undirected graph. What I'm trying to determine is the number of discreet ...
0
votes
1answer
34 views
Topological sort of cyclic graph with minimum number of violated edges
I am looking for a way to perform a topological sorting on a given directed unweighted graph, that contains cycles. The result should not only contain the ordering of vertices, but also the set of ...
0
votes
0answers
32 views
DFS alphabetically ordered search
I'm trying to do a DFS Forest on this directed graph, and instead of the usual random node order, I'm doing it by alphabetical order (both in the adjacency list and in the algorithm itself). Letters ...
0
votes
1answer
34 views
Determine remaining subgraphs after removal of a node joining them
So I ran into this problem while attempting to implement a feature:
Suppose I have a random, undirected graph of nodes, some of which are connected to each other.
Let's call every group of nodes ...
0
votes
0answers
26 views
Directed Graph BFS without all nodes reachable
I'm doing a breadth-first search on a digraph. I'm lost at nodes c and f, and I'm not sure if and how they should be in the BF-tree or if you only go as far as reachable from the source node and don't ...
2
votes
2answers
36 views
Best way to find the most costly path in graph
I have a directed acyclic graph on which every vertex has a weight >= 0. There is a vertex who is the "start" of the graph and another vertex who is the "end" of the graph. The idea is to find the ...
-3
votes
1answer
32 views
Shortest Path for Courier Delivery following constraints? [closed]
I am new to algorithms and am following an algorithm course by a Stanford Professor from Courserera. What algorithm do I need to know to finish this task?
I have a source from where I have to start ...
2
votes
1answer
59 views
Optimization on Algorithm to check “Whether for a given directed graph there is only one way to sort the graph using topological sort or not”
My algorithm for this is :
First to calculate Indegree of every node , i.e. count of how many
edges are there for which this node is sink for them.
Now, will push only those in queue which have ...
0
votes
1answer
50 views
Counting the number of linear spanning trees in a given undirected graph
While solving a question of one of the online coding sites, I encountered this problem.
Is there any algorithm to find the number of linear spanning trees in a given undirected graph such that each ...
2
votes
1answer
36 views
Is there a minimum spanning tree in a non-planar graph?
Is there a minimum spanning tree in a non-planar graph? I have read about prim algorithm and triangle inequality and my graph doesn't satisfy the triangle inequality?
0
votes
1answer
27 views
How can an All-Pairs Shortest Path algorithm be optimized for an undirected symmetric graph?
How can an All-Pairs Shortest Path algorithm be optimized for an undirected symmetric graph?
I came across this question as a result of a misunderstanding of another question and I thought it might ...
2
votes
1answer
50 views
Why does BFS gives different running time for different node positions in same graph?
I have a line graph, which consists of 100 nodes, which are labeled from 0 to 99.
Which looks something like this:
0--1--2--3....98--99
And I use BFS, DFS, Dijkstra's algorithms to find the ...
0
votes
1answer
43 views
Efficiently find connected subgraphs (not necessarily induced) of a given order
Given a connected undirected vertex-labelled graph, an edge in the graph, and some number n ≥ 2, is there an efficient algorithm to find all the connected (but not necessarily induced) subgraphs of ...
0
votes
1answer
33 views
Assigning jobs to people using Maximum Flow, harder version
I am self studying max flow and there was this problem:
the original problem is
Suppose we have a list of jobs
{J1, J1,..., Jm}
and a list of people that have applied for them
{P1, P2, ...
5
votes
2answers
70 views
Java - Graph critical links
I have a graph in which i have two nodes (0 and 6) and i have to cut the least edges possible so that they aren´t connected. For example in this graph
Being the nodes 0 and 6 the least edges that i ...
