Which cycle detection within a directed graph are more efficient than O(n^2)? [closed]
Tarjan’s strongly connected components algorithm has O(|E| + |V|) time complexity. For other algorithms, see Strongly connected components on Wikipedia.
graph-theory
Use Dijkstra’s to find a Minimum Spanning Tree?
The answer is no. To see why, let’s first articulate the question like so: Q: For a connected, undirected, weighted graph G = (V, E, w) with only nonnegative edge weights, does the predecessor subgraph produced by Dijkstra’s Algorithm form a minimum spanning tree of G? (Note that undirected graphs are a special class of … Read more
Vertex cover vs dominating set
I found some graphs on Wikipedia’s Dominating Set article that illustrate this difference. These examples show dominating sets (in red) that aren’t vertex covers, the opposite of what you asked later on in your question. The edges in (V-D) prevent them from being vertex covers.
What is an efficient algorithm for counting the number of triangles in a graph? [closed]
You will need depth first search. The algorithm will be: 1) For the current node ask all unvisited adjacent nodes 2) for each of those nodes run depth two check to see if a node at depth 2 is your current node from step one 3) mark current node as visited 4) on make each … Read more
‘Head First’ Style Data Structures & Algorithms Book? [closed]
The Algorithm Design Manual by Steve Skiena isn’t exactly a barrel of laughs, but it’s relatively light on the deeper mathematics and contains lots of what he calls “War Stories”, which are illustrative examples from real world situations where algorithm work really paid off (or, sometimes, totally failed). He’s also got his audio and video … Read more
Construct adjacency matrix in MATLAB
If you notice, there is a distinct pattern to the adjacency matrices you are creating. Specifically, they are symmetric and banded. You can take advantage of this fact to easily create your matrices using the diag function (or the spdiags function if you want to make a sparse matrix). Here is how you can create … Read more
What options are available for the layout of directed or undirected graphs in .NET?
Graph# is also another option. I haven’t used it personally, but I’ve been meaning to get around to looking over it.
What is the difference between breadth first searching and level order traversal?
For a ‘proper’ tree (see below), it’s the same thing, at least by most definitions. Like Wikipedia, for example: Breadth-first See also: Breadth-first search Trees can also be traversed in level-order, … … a breadth-first (level-order) traversal … Well, at least level-order traversal is the same as breadth-first traversal. There are many reasons to traverse … Read more
How to serialize a graph structure?
How do you represent your graph in memory? Basically you have two (good) options: an adjacency list representation an adjacency matrix representation in which the adjacency list representation is best used for a sparse graph, and a matrix representation for the dense graphs. If you used suchs representations then you could serialize those representations instead. … Read more
Find all chordless cycles in an undirected graph
Assign numbers to nodes from 1 to n. Pick the node number 1. Call it ‘A’. Enumerate pairs of links coming out of ‘A’. Pick one. Let’s call the adjacent nodes ‘B’ and ‘C’ with B less than C. If B and C are connected, then output the cycle ABC, return to step 3 and … Read more