Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.

4,985 questions
Filter by
Sorted by
Tagged with
60k views

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 ...
• 985
14k views

Is zero allowed as an edge's weight, in a weighted graph?

I am trying to write a script that generates random graphs and I need to know if an edge in a weighted graph can have the 0 value. actually it makes sense that 0 could be used as an edge's weight, ...
• 729
80k views

Why does Dijkstra's algorithm fail on a negative weighted graphs? [duplicate]

I know this is probably very basic, I just can't wrap my head around it. We recently studied about Dijkstra's algorithm for finding the shortest path between two vertices on a weighted graph. My ...
• 1,219
67k views

Longest path in an undirected tree with only one traversal

There is this standard algorithm for finding longest path in undirected trees using two depth-first searches: Start DFS from a random vertex $v$ and find the farthest vertex from it; say it is $v'$. ...
• 1,319
11k views

Do you get DFS if you change the queue to a stack in a BFS implementation?

Here is the standard pseudocode for breadth first search: ...
• 1,336
64k 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 ...
• 531
13k views

What are some real world applications of graphs?

Can you give some real world examples of what graphs algorithms people are actually using in applications? Given a complicated graphs, say social networks, what properties/quantity people want to ...
• 568
55k views

Algorithm that finds the number of simple paths from $s$ to $t$ in $G$

Can anyone suggest me a linear time algorithm that takes as input a directed acyclic graph $G=(V,E)$ and two vertices $s$ and $t$ and returns the number of simple paths from $s$ to $t$ in $G$. I have ...
• 919
772 views

Finding an $st$-path in a planar graph which is adjacent to the fewest number of faces

I am curious whether the following problems has been studied before, but wasn't able to find any papers about it: Given a planar graph $G$, and two vertices $s$ and $t$, find an $s$-$t$ path $P$ ...
• 391
9k views

Enumerate all non-isomorphic graphs of a certain size

I'd like to enumerate all undirected graphs of size $n$, but I only need one instance of each isomorphism class. In other words, I want to enumerate all non-isomorphic (undirected) graphs on $n$ ...
• 163k
43k views

Is Dijkstra's algorithm just BFS with a priority queue?

According to this page, Dijkstra's algorithm is just BFS with a priority queue. Is it really that simple? I think not.
13k views

How hard is counting the number of simple paths between two nodes in a directed graph?

There is an easy polynomial algorithm to decide whether there is a path between two nodes in a directed graph (just do a routine graph traversal with, say, depth-first-search). However it seems that, ...
• 1,389
995 views

Graph problem known to be $NP$-complete only under Cook reduction

The theory of NP-completeness was initially built on Cook (polynomial-time Turing) reductions. Later, Karp introduced polynomial-time many-to-one reductions. A Cook reduction is more powerful than a ...
44k views

The time complexity of finding the diameter of a graph

What is the time complexity of finding the diameter of a graph $G=(V,E)$? ${O}(|V|^2)$ ${O}(|V|^2+|V| \cdot |E|)$ ${O}(|V|^2\cdot |E|)$ ${O}(|V|\cdot |E|^2)$ The diameter of a ...
• 2,193
15k views

Retrieving the shortest path of a dynamic graph

I'm studying shortest paths in directed graphs currently. There are many efficient algorithms for finding the shortest path in a network, like dijkstra's or bellman-ford's. But what if the graph is ...