Consider a set of points arranged on a grid of size N-by-M. I am trying to build the adjacency matrix such that neighboring points are connected. For example, in a 3x3 grid with a graph: 1-2-3 | ...

I am trying to implement a randomly generated maze using Prim's algorithm. I want my maze to look like this: however the mazes that I am generating from my program look like this: I'm current...

I've managed to create a random undirected weighted graph for testing with Dijkstra's algorithm, but how can I make it so each node has at least one edge that connects them to the graph? I'm using...

What does relaxation of an edge mean in the context of graph theory ? I came across this while studying up on Dijkstra's algorithm for single source shortest path.

I was reading up algorithms for finding the minimum spanning tree(in case of weighted graphs) and for finding if a graph has a hamiltonian path(which depends on the presence of a hamiltonian cycle)...

I have a weighted graph, no negative weights, and I would like to find the path from one node to another, trying to minimize the cost for the single step. I don't need to minimize the total cost of...

Predominantly DFS is used to find a cycle in graphs and not BFS. Any reasons? Both can find if a node has already been visited while traversing the tree/graph.

I tried to find a graph data structure to reuse in C# without any success. Of course, I can borrow from data structure books but I want it to be more commercially practical(?) Also I would ap...

Can somebody tell me why Dijkstra's algorithm for single source shortest path assumes that the edges must be non-negative. I am talking about only edges not the negative weight cycles.

I was wondering when one should use Prim's algorithm and when Kruskal's to find the minimum spanning tree? They both have easy logics, same worst cases, and only difference is implementation which ...

There is almost exactly the same question. But I still don't understand, how is this heuristic working and in what sequence vertexes are passed through. Also there is a picture in a book: That sh...

So my aunt plays this now popular mobile game, shown in the picture below. She got stuck on a certain level and asked me if I can solve it. Knowing that I'm not smart enough to find patterns or a s...

What is the most efficient way to generate a large (~ 300k vertices) random planar graph ("random" here means uniformly distributed)?

Here is an exercise in the Algorithm Design Manual. Consider the problem of determining whether a given undirected graph G = (V, E) contains a triangle or cycle of length 3. (a) Give an O(|V...

I don't need code, just an explanation. My textbook says level order: each node at level i is processed before any node at level i+1 My understanding of breadth first searching is that you exp...

I know that A* with admissible non consistent heuristic will not find optimal solution but I am struggling with finding example when will it happen. I can not find example because of this thought ...

Given a directed graph, I need to find the minimum set of vertices from which all other vertices can be reached. So the result of the function should be the smallest number of vertices, from whic...

I am trying to generate all directed graphs with a given number of nodes up to graph isomorphism so that I can feed them into another Python program. Here is a naive reference implementation using ...

I have some input like: [('A', 'B'),('C', 'D'),('D', 'C'),('C', 'D')]. I want to look for if the existence of a cycle in a directed graph represented by this edgeList. I read a discussion: https:/...

I'm trying to code the shortest path finder using Dijkstra's algorithm but it doesn't seem to be working. I can't figure out what the problem is. I'm working on Python 3.5 and following this video....

There is a set of users. A person can have multiple users, but ref1 and ref2 might be alike and can therefore link users together. ref1 and ref2 does not overlap, one value in ref1 does not exist i...

What would be the best way to implement approximate Disjoint Sets using SQL? Details I have a table of edges, stored as a two-column table of [vertex_a, vertex_b]. I need a table of distinct set...

Given a set of left nodes and right nodes, and edges between them (a bipartite graph), I need to support quick lookups from sets of left nodes to the subset of right nodes connected to anything on ...

I had an interview were I was asked a seemingly simple algorithm question: "Write an algorithm to return me all possible winning combinations for tic tac toe." I still can't figure out an efficient...

[Note: A fast solution was given in an answer however further improvement concerning speed is desirable.] Given is an undirected sparsely connected graph G with n vertices. I am looking for a fast ...