Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

Questions about graph traversal algorithms such as BFS and DFS.

1
vote
1answer
49 views

Split graph in two parts, such that most nodes have even number of edges

We have given graph of at most $200$ nodes, we want to split the given graph in two parts, such that the number of nodes with even number of edges is maximized, note that the edges that are between ...
1
vote
1answer
27 views

Breadth First Search actually require specifically Queue instead of any other type of Collection?

As far as I know, Breadth-First-Search [BFS] theory traditionally requires a Queue to process a given level of a graph (i.e: wiki seems to assume so). But does BFS really actually require a Queue, ...
2
votes
2answers
33 views

How to graph search a LTL-generated Buchi automaton to generate valid execution paths

I have a set of tasks, and a LTL specification that describes which orders of the tasks are legal. I want to find a way to enumerate all permutations of the tasks that meet the specification. For ...
0
votes
0answers
27 views

How many roots are there in an undirected root

Given an undirected tree with 7 nodes how many roots would this tree have. My intuition tells me that because the tree is undirected it would either be 7 or 0. How would I solve this?
0
votes
0answers
12 views

Ordering the incident edges of each vertex to have a specified pre-order traversal

Input: You are given a graph $G(V, E)$ undirected, loop-less, no parallel edges, etc. and a label function $L: V \to \mathbb{N}$. Also, a sequence of $|V|$ natural numbers is given. Output: Is it ...
2
votes
2answers
37 views

Find out an algorithm that finds out if an undirected graph contains even length cycle or not using BFS?

I know how to find odd length cycles(a bipartite graph cannot have odd cycles) but I cannot manage to make an algorithm when considering even length cycles.
0
votes
1answer
34 views

When to terminate search for path in an infinite grid

I'm learning shortest path algorithms like Dijkstra's, BFS, etc. I understand on a 2D finite grid there are boundary conditions (i.e. size of the grid) that help terminate the algorithm and keep it in ...
1
vote
1answer
57 views

Different topologically sorted order based on DFS vertex ordering

The algorithm for topological sort, in CLRS goes as follows : call DFS(G) to compute finishing times v.f for each vertex v as each vertex is finished, insert it onto the front of a linked list return ...
0
votes
0answers
13 views

How to Compute Lowpt(v) in a DFS Tree, where Lowpt(v)={w| there exist a back_edge xw, such that x is a descendant of v}?

In computing Triconnected components of a graph using HopCropt and Tarjan algorithm, i.e https://sci-hub.tw/https://epubs.siam.org/doi/pdf/10.1137/0202012, they compute two additional values Lowpt1 ...
0
votes
0answers
25 views

Single source shortest Path Algorithm in dynamic graph

In case of dynamic graphs where edges are added only (all edges have positive weight). Goal: to keep track of the shortest path from the source to the goal node. Are their any specific conditions ...
2
votes
1answer
22 views

Is it possible to detect a simple negative-weight cycle of weight $N$ in polynomial time?

Given a directed graph and an integer $N$, is it possible to detect a simple negative-weight cycle whose edges sum to $N$ in polynomial time? I thought about modifying the Floyd-Warshall algorithm to ...
1
vote
1answer
10 views

How to get initial flow for TSP with missing edges

I need to solve a version of the traveling salesman problem with missing edges. I've decided to use simulated annealing. How do I generate a valid initial path effectively? I would use a greedy ...
0
votes
0answers
35 views

v.lowlink = min(v.lowlink, w.index) line in Tarjan Algorithm

Following the pseudo-code notation used in wikipedia. I understand the basics of the algorithm but I don't really understand this line. When exactly is it relevant? I only found one example, and it ...
0
votes
0answers
12 views

Finding a path between 2 points passing through N points

Given a graph/plane with N points each at a given coordinate how could I find a path between 2 points via N other points where each point is weighted on how likely it is to be passed through. ...
1
vote
1answer
48 views

Understanding time complexity of a while loop that will look over all vertices and edges

I need a little clarification on differing time complexities. My analysis for the below algorithm was $O(n +nm)$, but the correct analysis would be $O(n+m)$. I know that ...
0
votes
1answer
52 views

Removing vertices that belong to a given set from a graph

If I'm given a graph $G$ with the set of vertices $V$ and a set $B \subseteq V$, can I remove all the vertices $\in B$ from $G$, as well as all edges that connect any other vertex to a vertex $\in B$ ...
2
votes
0answers
107 views

How to traverse a graph in reverse dfs order

For kosaraju's algorithm to traverse the graph in reverse order the naive solution is to reconstruct the original input graph in reverse order and dfs on it. Is there any way I can avoid creating ...
0
votes
0answers
55 views

Longest-Path Layering algorithm

NOTES: there are a myriad of graph data structures, I use a spin-off of a directed adjacency hash. the code provide in this post is python3 on the premise that it ...
0
votes
0answers
35 views

The path with the highest sum of weights

Mr. Katsaros owns a rectangular olive grove divided into 5 rows and 4 columns. He notes down the amount of olives (pounds) possibly obtainable from each of 20 square sections. The picking starts from ...
0
votes
0answers
6 views

Joining split vertices

Suppose you have two sets of edges, where in one of the sets, an edge is split into two sub-edges, like in the depiction below. Each "o" is a vertex of the edges, which are drawn by "----". Set 1: o--...
0
votes
0answers
45 views

Multi agent graph traversal with edge discovery

Suppose we are given a set of agents (say $P_1 , \dotsc, P_M$), an undirected graph G(V,A) and a set of initial vertices on $G$ where each agent is located. Initially only the edges connected to these ...
1
vote
1answer
57 views

Printing all paths of a tree and sorting the weight of edges

Let $T=(V,E)$ be tree and each edge has a positive scalar weight. I need to print all paths in the tree and then sort the weight of edges in each paths. it needs $O(n^3\log(n))$ time. To solve this ...
2
votes
0answers
74 views

Algorithm to find nodes with given a distance

We have a map of a branching river without any islands (tree of confluences, see picture), there are piers on the river bank ( not necessarily on the confluences). We are given the distances between ...
0
votes
0answers
56 views

Time complexity proof of finding the $i$ object in binary search tree is $O(h+i)$ by inorder

I'm looking for time complexity proof of finding the $i$ object in binary search tree is $O(h+i)$ by inorder run. when $h$ is the height of the tree.
3
votes
1answer
119 views

Given an oriented graph, return true if paths have a specified length

I'm having trouble solving this exercise about graphs, I hope you can help me: Given a graph $G = (V,E)$, two sets of vertices $A \subseteq V$ and $B \subseteq V$ (represented as arrays), and an ...
2
votes
1answer
24 views

Prove that the depth of every vertex in a cycle is $\le \lfloor \frac{n}{2} \rfloor$ in a breadth first search?

Suppose I have an undirected graph that consists only of a cycle. Each vertex has a depth value that must be $1$ greater than its predecessor (i.e. if we reach vertex $F$ from vertex $C$ which has a ...
1
vote
1answer
54 views

Find a path that contains specific nodes without back and forward edges

I have a directed graph and and a set of nodes(set = [1,2,5,9,24...]). I want to find a path that contains all the set of nodes and this path dont contain back edges(cycles) and forward edges. For ...
0
votes
1answer
46 views

Find all sets of nodes that can be connected with a single path

** Edit: I just noticed my current algorithm is incorrect, as it only finds paths starting/ending at the given node. I'm trying to figure out a solution, but I'm a bit stuck. Say I have an ...
1
vote
0answers
24 views

Dynamic path planning and waypoint sorting

Good evening everyone, I have a question that I am having a bit of trouble formulating properly and thus it is making it complicated to look up literature on the subject. What I am looking for is a ...
1
vote
1answer
68 views

How to minimally extend a digraph such that all nodes are on a cycle?

Let's say we have a directed graph with $n$ nodes and $m$ edges. For each node we want to make path that will start from this node, possibly traverse some other nodes and finish in the same node, in ...
0
votes
0answers
53 views

BFS time complexity

I would like to express the time complexity of BFS as the number of nodes generated with respect to the branching factor $b$ and the depth of the goal $d$. I am assuming that nodes are goal tested at ...
1
vote
1answer
93 views

is it possible to determine using a single depth-first search, in O(V+E) time, whether a directed graph is singly connected?

I'm working on exercise 22.3-13 of CLRS (Intro to Algorithms 3rd edition): A directed graph $G = (V, E)$ is singly connected if the existence of a path from $u$ to $v$ implies that $G$ contains at ...
3
votes
2answers
596 views

What do we do instead of DFS on directed graphs?

All the example of DFS I've seen so far are for undirected graph. In a directed graph the basic DFS algorithm won't work because some vertex will be unreachable. The algorithm I'm talking about : ...
1
vote
1answer
24 views

Algorithm to select sets of objects while maximizing number of objects covered

If we have different objects, [A1, A2, A3, B1, B2, B3, B4, B5] Some calculations will be performed to find compatible objects. For example, lets assume following ...
2
votes
1answer
95 views

Conditional Shortest Path Through Weighted Cyclic Directed Graph

Vertices in my graph are composed of {name, category} where category is one of {red, grn, blu, ylw}. Edges in my graph are weighted and directed. In the visualization, the thick end of the edge ...
0
votes
1answer
220 views

Iterative DFS space complexity O(|E|)? Same vertex appears multiple times in stack?

I'm referring to a question already asked on stackoverflow: https://stackoverflow.com/questions/25988965/does-depth-first-search-create-redundancy However I'm not quite convinced by the answers ...
2
votes
3answers
129 views

Can a 3 Color DFS be used to identify cycles (not just detect them)?

Can a 3 color DFS be used to identify all cycles in a directed graph not just detect them? In other words if I have a directed graph with multiple cycles, can I run a function on them such that the ...
4
votes
0answers
63 views

Visiting all train stations

When I went to London, I wondered how to visit all the London Underground stations as fast as possible. Given a randomly-chosen start station, timetable of train arriving & departing of every ...
1
vote
1answer
140 views

Does a graph diameter equal to DFS tree depth?

given an unweighted graph, does the graph diameter equal to the maximum DFS tree depth? and the same about BFS? regarding both directed and undirected graphs. thanks :)
1
vote
1answer
160 views

About the 'trick' for finding the diameter of an graph in $O(n^2)$

The diameter of an undirected, unweighted graph can be found in $O(n^3)$ with e.g. the Floyd–Warshall algorithm. However, there is an idea how to improve the runtime: Pick a vertex $v$ Find $u$ such ...
2
votes
1answer
342 views

Mother vertex of a graph

I am trying to find all mother vertex in a directed graph. A mother vertex in a directed graph G = (V,E) is a vertex v such that all other vertices in G can be reached by a path from v. My Approach:...
1
vote
1answer
36 views

Finding optimum point that minimizes maximum distance

Does anyone know how I should approach this algorithm? It needs to have $O(n^3)$ complexity and I can only come up with an algorithm that has $O(n^4)$ complexity (of doing a n^2 min path from each ...
1
vote
1answer
290 views

Determine if a vertex is a part of a cycle in O(m+n) complexity

I am trying to apply BFS to the following problem, but I'm not sure how to do it Input: directed graph $G$ defined by the array of adjacency lists with n vertices and m edges, and a vertex $v$ in $...
2
votes
2answers
42 views

Reconstruct graph of N edges from a matrix of shortest pair distances (N*N) (i.e. result from Floyd-Warshall algorithm)

I want to reconstruct a graph when given the results of a Floyd-Warshall shortest pair distances matrix, similar to the problem being solved in this question: Is it possible to reconstruct graph if ...
1
vote
1answer
81 views

Any way to find a 3-vertex cycle in a graph using an incidence matrix in O(nm) time?

I have a graph with n edges and m vertices. This is an undirected graph. I need to find a 3 vertex cycle. Only 3. I'm confident I need to use an incidence matrix for this as this seems to be the ...
0
votes
0answers
27 views

Shortest cycle containing specific points

In an 2D grid we have to find a cycle starting from given point containing all the specified points(at most 10). And some points on the grid can not be used in path. please suggest some algorithm of ...
0
votes
1answer
72 views

How to deal with cost variation in a dynamic graph when applying Dijkstra

What are the methods to deal with variations in cost in a dynamic graph when applying Dijkstra? For instance, I select the shortest path in a graph, however, the weight of this path changed after I ...
0
votes
1answer
506 views

Longest path in directed graph cyclic graph where each node has one children

Consider given directed unweighted cyclic graph with $N$ nodes, and $N$ edges, and each node has at most one out-going children. Find the longest path. Example Consider the following graph, the path ...
1
vote
1answer
33 views

Storing nodes in state space search

I'm taking an introductory course in AI and we've been given the assignment to solve a puzzle using different search algorithms on a state space (BFS, DFS etc). I understand the theory and everything, ...
3
votes
2answers
316 views

Girth of Undirected Graph with Positive Integer Weights

Let $G = (V, E)$ be an undirected graph without self loops and with edge weights $w: E \to \mathbb{N}$. The girth $g(G)$ of $G$ is defined as the length of the shortest cycle in $G$, i.e. $g(G) := \...