Skip to main content
165 votes
Accepted

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

Allowed by whom? There is no Central Graph Administration that decides what you can and cannot do. You can define objects in any way that's convenient for you, as long as you're clear about what the ...
David Richerby's user avatar
47 votes
Accepted

Do any two spanning trees of a simple graph always have some common edges?

No, consider the complete graph $K_4$: It has the following edge-disjoint spanning trees:
Bjørn Kjos-Hanssen's user avatar
44 votes

Residual Graph in Maximum Flow

The intuition behing the residual graph in the Maximum flow problem is very well presented in this lecture. The explanation goes as follows. Suppose that we are trying to solve the maximum flow ...
Mario Cervera's user avatar
44 votes
Accepted

What are some real world applications of graphs?

Graphs are definitely one of the most important data structures, and are used very broadly Optimization problems Algorithms like Dijkstra's enable your navigation system / GPS to decide which roads ...
loopbackbee's user avatar
42 votes
Accepted

Assuming P = NP, how would one solve the graph coloring problem in polynomial time?

There are two cases: $P = NP$ non-constructively: this means we have derived a contradiction from the assumption that $P \neq NP$, and thus can conclude that $P = NP$ by the law of the excluded ...
Joey Eremondi's user avatar
39 votes

Example of a graph with negative weighed edges in which Dijkstra's algorithm does work

Take a look at the simplest possible example: Our graph has only two nodes: $s,t$, and a single edge between them. In this example, it won't matter what is the cost of this single edge (it can be ...
nir shahar's user avatar
  • 11.6k
38 votes
Accepted

Why are directed graphs important?

Recalling that a directed graph is a graph where the edges have an associated direction with them. Using a directed graph you can represent asymmetrical relationships between nodes, while in ...
dariodip's user avatar
  • 864
35 votes

Real life examples of negative weight edges in graphs

Distance between cities can't be negative, but if you are programming for an electric car, then a downhill road segment will regen, thus the energy used is negative. It is very important to take that ...
Pål GD's user avatar
  • 16.7k
33 votes
Accepted

Is there a difference between perfect, full and complete tree?

Yes, there is a difference between the three terms and the difference can be explained as: Full Binary Tree: A Binary Tree is full if every node has 0 or 2 children. Following are examples of a full ...
Lov Verma's user avatar
  • 456
29 votes
Accepted

Why are graphs represented as adjacency lists instead of adjacency sets?

In many algorithms we don't need to check whether two vertices are adjacent, like in search algorithms, DFS, BFS, Dijkstra's, and many other algorithms. In the cases where we only need to enumerate ...
Pål GD's user avatar
  • 16.7k
25 votes

What are some real world applications of graphs?

Pathfinding is arguably one of the most practical subareas of algorithms and graphs. I am sure you can find plenty of use cases from navigation, routing, logistics and computer games, all growing ...
Juho's user avatar
  • 22.6k
25 votes

Real life examples of *zero* weight edges in graphs

Of course. The weight can mean things that are irrelevant to the existence of an edge. Since you don't ask for a "list of say 6 or 7 real-life examples", I will just add one. Consider a ...
Pål GD's user avatar
  • 16.7k
24 votes

When are adjacency lists or matrices the better choice?

First of all note that sparse means that you have very few edges, and dense means many edges, or almost complete graph. In a complete graph you have $n(n-1)/2$ edges, where $n$ is the number of nodes. ...
fade2black's user avatar
  • 9,837
24 votes

Does the Minimum Spanning Tree include the TWO lowest cost edges?

For simple graphs*, it is true for the following reason: Kruskal’s algorithm is correct Kruskal’s algorithm works as follows: sort the edges by increasing weight repeat: pop the cheapest edge, if it ...
Pål GD's user avatar
  • 16.7k
23 votes

What is the meaning of 'breadth' in breadth first search?

Consider the data structure used to represent the search. In a BFS, you use a queue. If you come across an unseen node, you add it to the queue. The “frontier” is the set of all nodes in the search ...
Throckmorton's user avatar
21 votes

Is Group Theory useful in Computer Science in areas other than cryptography?

Algorithms for isomorphism problems such as graph isomorphism rely heavily on group theory. An unusual example of group theory applied to computer science is the famous proof of Barrington's theorem, ...
Aaron Rotenberg's user avatar
19 votes
Accepted

Treewidth of k x k square grid graphs

The treewidth (and pathwidth) of the $k\times k$ grid is exactly $k$. (And, more generally, the treewidth and pathwidth of the $k\times\ell$ grid is exactly $\min\,\{k,\ell\}$). For the example grid $...
David Richerby's user avatar
19 votes

How is the problem, {⟨G⟩|G has no triangle} in Logspace?

FOR x := 1 TO n DO FOR y := 1 TO n DO FOR z := 1 TO n DO IF E(x,y) && E(y,z) && E(z,x) THEN REJECT ACCEPT Each of the ...
David Richerby's user avatar
18 votes
Accepted

Clique vs Complete Graph

A complete graph is a graph with every possible edge; a clique is a graph or subgraph with every possible edge. That is, one might say that a graph "contains a clique" but it's much less common to say ...
David Richerby's user avatar
17 votes
Accepted

A* graph search time-complexity

These are basically two different perspectives or two different ways of viewing the running time. Both are valid (neither is incorrect), but $O(b^d)$ is arguably more useful in the settings that ...
D.W.'s user avatar
  • 161k
17 votes

social network graph problem

This is known as majority dynamics. Usually the assumption is that all nodes adopt the majority opinion simultaneously, and this is known as the synchronous model. For an arbitrary tie-breaking rule, ...
Yuval Filmus's user avatar
17 votes
Accepted

Finite state automata: final states

You seem to have a misunderstanding of generative models v.s. "recognizing" models. The grammar you have on the right generates words by applying rules, starting from the initial variable, and ...
Shaull's user avatar
  • 17.2k
17 votes
Accepted

How is the problem, {⟨G⟩|G has no triangle} in Logspace?

You don't need to first write all 3-tuples and then check, for each of them, whether it induces a triangle. You can just enumerate the 3-tuples one at a time and reject as soon as you find one that ...
Steven's user avatar
  • 29.5k
16 votes
Accepted

What's the Big O runtime of a DFS word search through a matrix?

The complexity will be $O(m*n*4^{s})$ where m is the no. of rows and n is the no. of columns in the 2D matrix and s is the length of the input string. When we start searching from a character we ...
Navjot Singh's user avatar
  • 1,215
16 votes
Accepted

Is there a simple argument why graph isomorphism is not NP-complete?

The type of argument you are looking for is as follows: If graph isomorphism were NP-complete, then some widely believed complexity assumption fails. There are at least two such arguments: Schöning ...
Yuval Filmus's user avatar
15 votes
Accepted

Incremental strongly connected components

To the best of my knowledge, the best algorithm for decremental strongly connected components is presented in [1] with $O(m \sqrt{n} \log n)$ total expected update time. [1] Decremental Single-...
Alexander Svozil's user avatar
15 votes

Is Group Theory useful in Computer Science in areas other than cryptography?

Group theory is indeed useful in algorithm design. For example, matrix multiplication is a fundamental problem for which such approaches have been used (see e.g., Cohn et al. [1] or these lecture ...
Juho's user avatar
  • 22.6k
15 votes
Accepted

How to define a similarity between two graphs?

One such metric which is very useful is the graph edit distance. In a nutshell, you are allowed a certain number of operations, each with a cost, such as edge insertion or edge deletion (depending on ...
integrator's user avatar
  • 1,110
15 votes
Accepted

In a directed acyclic graph, what do you call the nodes with in-degree zero?

I believe the common term for that is source. While a node with 0 out-degree is called a sink.
Russel's user avatar
  • 2,780
15 votes
Accepted

Can every spanning tree result from a depth-first search?

Consider a complete graph $K_n$. Then a depth-first search can only create a linear-path spanning tree, no matter what the edges processing order is.
Nathaniel's user avatar
  • 15.8k

Only top scored, non community-wiki answers of a minimum length are eligible