Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

# Questions tagged [graph-traversal]

Questions about graph traversal algorithms such as BFS and DFS.

424 questions
Filter by
Sorted by
Tagged with
83 views

### Are reversed reverse preorder traversals equivalent to a postorder traversal?

I was viewing the solutions of other Leetcode users for the classic "post-order traversal of a binary tree" question, when to my surprise, I found a ton of users simply finding the reverse ...
• 123
39 views

### Walk from vertex u to vertex v on complete graph, formula for number of walks of length k

Complete graph with n vertices. Walk from vertex u to vertex v of length k. I don't understand how the number of walks between the two of length k is $n^{k-1}$ I've tried this formula on an example ...
10 views

### Approach for flattening a 3-d cube given cuts

Take a cube. Cut seven of its edges. Consider a graph whose vertices are the centers of the faces of the cube. If two faces share a common edge, then the graph also has an edge connecting the two ...
• 305
23 views

### Using an undirected graph to represent an ordered pair?

Set theory depends on a set membership function $\epsilon$ which is a class of ordered pairs. Is it possible to construct the ordered pair from an undirected graph of unordered pairs? Alternatively, ...
• 175
363 views

### What role is the set, S playing in Dijkstra's algorithm given in the book CLRS?

I'm looking at Dijkstra's algorithm for single source shortest paths in a graph $G$ from a vertex $s$ from Introduction to Algorithms by Cormen et al. The $w$ parameter is the weight function such ...
• 305
28 views

### Make maze connected by removing internal walls

Recently I've stumbled upon a strange graph problem. Here is a brief description. Given $n\times m$ matrix with $2n + 1$ rows such that each row contains $2m + 1$ characters "+", "-&...
1 vote
113 views

### Min weighted path in a graph, but you could die

The min-path problem is mostly motivated by a graph with cities as vertices and roads between them as edges. Each edge has a weight which could be the length of the road or the time it takes to cross ...
• 305
45 views

### Algorithm to find for each vertex, a vetrex that it can reach with the lowest cost in a graph

We have a directed graph $G=(V,E)$ and each vertex $v\in V$ has a cost: $price(v)$. Our mission is to find an algorithm that runs in time $\mathcal{O}(|E|+|V|)$ that finds $\forall v\in V$ the minimal ...
• 103
37 views

### Finding a circle within a circle

Let $G=(V,E)$ be undirected, and let $s,t\in V$ and $C\subseteq E$ be a circle that contains $s$ and $t$. Assuming $s$ and $t$ are on the circle $C$, we are given a set of edges $F\subseteq E$ which ...
1 vote
26 views

### Node domination in constrained path search

It's possible to modify a graph search algorithm such as Dijkstra's or A* to allow for non-additive objectives or constraints. Is there a standard treatment for these algorithms to reduce unnecessary ...
• 222
13 views

### A DFS update without re-running DFS after adding and removing an edge

Given an undirected graph $G=(V,E)$ I perform a DFS run on it, and among other information I get the visit time $s(\cdot )$ and the exit time $f(\cdot )$ per each node and the parent of each node. ...
13 views

### Detect the actual edges of circle in directed graph [duplicate]

Okay so , I know how bellman -ford can detect a negative circle. My question is : how to actually find the edges participating in this circle. I searched and found some stuff that seem to work in the ...
• 191
47 views

### How can we process these types of queries on trees?

CAN SOMEONE FIND A BETTER (MORE DESCRIPTIVE) NAME FOR THIS QUESTION, THANKS I recently thought of this interesting Tree problem: Given a tree with $N$ nodes, let $val_i$ = the "value" for ...
87 views

### Archaeological Consistency: Graph Problem

So, I have an issue with the following problem (CS 161 Stanford 2013, Problem Set 2): Suppose that you have found a collection of historical records indicating the relative order in which various ...
• 163
341 views

### modify dfs to find longest path

Let $G = (V, E)$ be a directed acyclic graph. Let every node $v \in V$ have an additional field $v_d$. For each vertex $v \in V$, we need to store in $v_d$ the length of the longest path in $G$ that ...
• 25
1 vote
78 views

• 123
106 views

### Is the best known algorithm for the shortest path problem for an undirected and unweighted graph $O(E)$ or $O(E+V)$?

I'm a bit confused by Wikipedia's tables of algorithms for the shortest path problem. For an unweighted graph with $E$ edges and $V$ vertices, it gives the best algorithm as breadth-first search, with ...
• 934
489 views

### find a path to visit every node in graph not necessarily once

I meet a problem but when I google, there are all Hamiltonian Path Problem: How to find a path to visit every node in directed graph(not necessarily once)? This problem is different from Hamiltonian ...
• 123
1 vote
44 views

### Given graph G and vertices v and w can you non-deterministically walk the "least Hamiltonian path" from v to w, if it exists?

My understanding of non-deterministic algorithms is that they're "as lucky as you want". ...you can think of the algorithm as being able to make a guess at any point it wants, and a space ...
1 vote
42 views

### Number of paths starting from a given edge using adjacency matrix

I want to write the algorithm that takes the adgacency matrix of a directed connected graph without any cycles, then for each edge computes the number of paths starting from that edge. Also note that ...
166 views

### Stack without duplicates

I was thinking about the implementation of a DFS on graphs, and particularly about space complexity. The DFS algorithm can be implemented with a stack data structure. When a vertex $v$ is met during ...
• 7,154
Given an unweighted, undirected graph $G=(V,E)$ without loops or multiedges, and vertices $v,w$, one can use breadth-first search to check if $v$, $w$ are connected, and in particular the algorithm ...
Recently I encountered an interesting problem while studying discrete mathematics: Give the pseudo code to judge whether a poset $(S,\preceq)$ is a lattice, and analyze the time complexity of the ...