# Questions tagged [graph-traversal]

Questions about graph traversal algorithms such as BFS and DFS.

20 questions
Filter by
Sorted by
Tagged with
5k views

### Finding the k-shortest path between two nodes

Given a weighted digraph $G=V,E$, and a weight function, $d(u,v)$, one can normally use Dijkstra's algorithm to obtain the shortest path. What I am interested in, is how to obtain the $2^{nd}$-...
41k views

### Algorithm to find diameter of a tree using BFS/DFS. Why does it work?

This link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u ...
2k views

### Shortest non intersecting path for a graph embedded in a euclidean plane (2D)

What algorithm would you use to find the shortest path of a graph, which is embedded in an euclidean plane, such that the path should not contain any self-intersections (in the embedding)? For ...
3k views

### Correctness of Strongly Connected Components algorithm for a directed graph

I have been reading up on algorithm for finding the strongly connected components in a directed graph $G=(V,E)$. It considers two DFS search and the second step is transposing the original graph $G^T$....
465 views

### Is it possible to reconstruct graph if we have given matrix of shortest pairs

I'm trying to reconstruct graph if we have given the result of floyd-warshall algorithm, more formally: Let's say we have given undirected weighted tree (graph without cycles) with $N$ nodes, such ...
54k views

### Graph searching: Breadth-first vs. depth-first

When searching graphs, there are two easy algorithms: breadth-first and depth-first (Usually done by adding all adjactent graph nodes to a queue (breadth-first) or stack (depth-first)). Now, are ...
17k views

### Why does DFS only yield tree and back edges on undirected, connected graphs?

Prove that if G is an undirected connected graph, then each of its edges is either in the depth-first search tree or is a back edge. Now, from intuition and in class lectures by Steven Skiena, I know ...
144 views

### What is the optimal solution to prove the reachbility of a node from the root?

I have a finite automaton with these properties: Contains cycles It's a directed graph All the states/nodes are initialy reachable from the initial state It has final states but I guess it isn't ...
4k views

### A Good Resource for Christofides' Heuristic

Is there an explanation Christofides's Heuristic for solving TSP which does not simply state the algorithm and go ahead to prove the bound? To be specific: (Disclaimer : I am an engineer who knows ...
685 views

### Finding the minimum number of calls in a tree

I was asked this question in an interview and struggled to answer it correctly in the time allotted. Nonetheless, I thought it was an interesting problem, and I hadn't seen it before. Suppose you ...
496 views

### How to evaluate relations in a DAG?

To begin with: what I know of computer science is what friends have told me and what I've read on Wikipedia. Please correct me if I'm using some term wrongly, or if there is something I can clarify. ...
3k views

### Minimum cost closed walk in a graph

Is there an efficient algorithm which gives the minimum cost closed walk in an undirected graph, which visits all vertices? Does this problem have a name? I tried to reduce this to similar problems (...
526 views

### Correctness of Algorithm for Computing Diameter of a Graph

I am a TA for an introductory CS course, and one question given to students was how to use BFS to determine the diameter of a graph. The students were told they wouldn't be graded for efficiency, so ...
77 views