Given an undirected graph with N vertices and M edges I need to find the number of cycles in the graph. But there is a constraint.

Here is an example of it: Consider this graph with 6 vertices and 7 edge pairs :- A-B , B-C , C-F , A-D , D-E , E-F , B-E.

Here is the image for better understanding :

Then here 2 cycles should be counted that are A-B-E-D-A and B-C-F-E-B but not A-B-C-F-E-D-A

So I need to find the count of the total cycles in the graph.

I think you are looking for a cycle basis of your graph. You do that by finding any spanning tree of the graph (for example a DFS or BFS tree). The non-tree edges of the graph represent a cycle basis: If you connect the endpoints by the unique path through the tree, you get an element of the basis.

So if the graph is connected, the number of basis elements is `m - n + 1`

(m = number of edges, n = number of nodes). If it's not connected, just decompose it into connected components and sum up the number of basis elements of the components. You get something like `m - n + c`

where c is the number of connected components. Thus, if you're not interested in the actual cycles and only in their count, you just need to find the number of connected components. You can use DFS or BFS for that as well.

Similar Questions

I can only make an undirected graph. no idea on how i can make a directed one. Any idea?

How would I convert a simple directed graph to a simple undirected one? Is this possible?

Given a weighted undirected graph with n vertices, I face the problem of finding a path of minimum weight that connects each of the vertices in a line. At first, I thought this is the problem of findi

i have to Find the longest path in a directed cyclic graph from a source s to a destination f. Assume no positive weight cycles exists even though no positive weight cycles exist, cycles of 0 or negat

I have an adjancency matrix am of a 5 node undirected graph where am(i,j) = 1 means node i is connected to node j. I generated all possible versions of this 5-node graph by the following code: import

I'm looking for an algorithm that given a graph it returns all the minimal cycles in it. To make clear what I want, I need the algorithm to return exactly the following cycles from this graph: (1,3,

Single Source shortest Path Dijkstra's - directed and undirected - works only for positive edge weights - cycles ?? Bellman Ford - directed - no cycles should exist All source shortest path Floyd Wa

I need a working algorithm for finding all simple cycles in an undirected graph. I know the cost can be exponential and the problem is NP-complete, but I am going to use it in a small graph (up to 20-

I came across this interesting problem of counting number of cycles in a digraph. For detecting a cycle in graph we can use DFS, but in order to detect number of cycles, DFS wont be of much use, as s

Good morning. My friend gave me an interesting graph problem which goes as below. Given a simple graph in which two cycles share at most one vertex, how to label edges with non negative real number su

Given a graph undirected G = (V,E) and a set of nodes P. I need to find a cycle (not the shortest length cycle) containing these nodes? How do I find this cycle?

I went back to the drawing board on a post I had written earlier concerning a StackOverflowException while trying to serialize an EF STE object graph... After failing to successfully adjust the stac

There's an undirected graph with weights on edges (weights are non-negative integers and their sum isn't big, most are 0). I need to divide it into some number of subgraphs (let's say graph of 20 node

I'm working with a very large undirected graph (a social network from a telecomunication company). I'm applying a clustering algorithm on this graph to find it’s most relevant communities. The proble

While solving a question of one of the online coding sites, I encountered this problem. Is there any algorithm to find the number of linear spanning trees in a given undirected graph such that each no

Background: As you can see below, there is an undirected graph on the left of the figure. Vertices are represented by S1,S2 ... S6, and edges are represented by line segments between vertices. Every e

I need a functions thats find a cycle in an undirected graph (boost) and returns its vertices and edges. It needs only return the vertices/edges of one cycle in the graph. My question is - what is the

graph { 0--1; 0--2; 0--1; } In the above the parallel edges between 0 and 1 is drawn as single edge when jpg is generated using dot command. Is it possible to avoid this?

I am trying to construct an algorithm that returns the nodes of a path that make up ONE cycle in an undirected graph (if there is one). What I have so far is performing DFS on the graph until I reach

I'm trying to determine the cycles in a directed graph using Tarjan's algorithm, presented in his research paper Enumeration of the elementary circuits of a directed graph from Septermber 1972. I'm

I have a graph that has values on nodes value = A/B/C values = { A , B , C } Aim: Connected nodes must have same values post settling : Example : Pre settling : node1 = { A, B } node2 = { A, B,

I'm very confused on how to solve this problem using Python. Please do NOT solve it for me as I'm learning Python and getting full soultions won't help. Say that I have the follwing input: 1 0,4 3 2 1

I am drawing a graph which keep on refreshing Algo Pmin = starting point of drawing graph line pmax = ending point of drawing graph line THpixel = Total Horizontal pixel; TVpixel = Total Vertical pixe

I am watching a lecture on negative cycles at this link At time 5:00, the instructor describes a case where it is assumed that no cycles exist. Then he says that any path won't contain a cycle, becaus

Consider an undirected graph. There are n vertices and m edges. All the edges have a weight associated with it. I want to device an algorithm that will take a source vertex 's', a sink vertex 't' and

I am working on a huge optical networks project where the networks are represented as undirected graphs where cycles may exist. At some point i want to find all minimum hop paths between two nodes in

We are given an undirected graph G = (V, E) and two vertices s, t ∈ V . We consider simple paths between s and t. A path is simple if every vertex is visited at most once. Are the following in P or NP

I was trying to solve a problem on an online judge. Given an undirected graph of n vertices(<=50000), initially with no edges, we are then given m edges(<100000), and we have been asked to outpu

I have a total undirected graph where nodes represent points on points on a plane, and edges are approximate euclidean distances between the points. I would like to embed this graph in a two dimensi

As noted in the documentation, Gradle uses a directed acyclic graph (DAG) to build a dependency graph. From my understanding, having separate cycles for evaluation and execution is a major feature for

I have an undirected graph with Vertex V and Edge E. I am looking for an algorithm to identify all the cycle bases in that graph. I think Tarjans algorithm is a good start. But the reference I have i

I have a document collection with size 1000, they all have 1 feature, a vector with 5 elements. The total sum of the 5 elements equals 100. So for example I can have a document with feature: [10,15,40

I want to generate all the Hamiltonian Cycles of a complete undirected graph (permutations of a set where loops and reverses count as duplicates, and are left out). For example, permutations of {1,2,3

I would like an algorithm or pointers to further research on how to find a fixed length path between two nodes in a weighted undirected graph.

I have a graph G containing N nodes and E edges.Each edge is undirectional.The goal is to find the no. of crucial nodes. A node which makes the graph disconnected when it is removed is called a crucia

I am very stuck with the looping structure for my graph to work out Eulers tour. This is the graph I am drawing, remember it's undirected, so a journey from N1 to N4 is the same as a journey from N4 t

Here is an excise: Let G be a weighted directed graph with n vertices and m edges, where all edges have positive weight. A directed cycle is a directed path that starts and ends at the same vertex an

We have the following input for the algorithm: A graph G with no cycles (aka a spanning-tree) where each node has an associated weight. I want to find an independent set S such that: No two elements

I'm making a line graph with numeric values, and the customer would like a line that shows the Total. I tried adding a data series called Total, and while that works, it alphabetizes Total in with

Prim's and Kruskal's algorithms are used to find the minimum spanning tree of a graph that is connected and undirected. Why can't they be used on a graph that is directed?

My problem should be pretty simple, given a graph (BGL adjacency_list) is there a simple algorithm to remove cycles? My first attempt was to use the DFS visitor to detect an edge that'd close the cycl

I am running QNX, I used a function to get clock cycles per second, uint64_t clockPerSec = getCPS(); uint64_t currentClockCycle = getCurrentCycle(); functions uint64_t getCPS() { return (~(uint64_t)

I was going through lecture of Minimum Spanning Tree, It says we are supposed to find connected acyclic subgraph graph in a Undirected graphs. My question is that How can a connected undirected graph

If there is a sketch (on paper) of a graph, or DAG or even a binarized image of a street-map -- is there any optical recognition system that can analyse the map or graph and then compute the shortest

If I would want to find maximum flow in undirected graph, how could I do this? On Wikipedia page http://en.wikipedia.org/wiki/Maximum_flow_problem it says that algorithms require directed graphs (I wo

I've created a 3D Volume mesh using Cgal's documentation and I was succesfully able to visualize my c3t3 (Complex 3 in triangulation 3) object. The mesh is composed of several connected components the

For below given matrix,how it can be represented as undirected weighted graph G(V,E,W) where V is set of vertices,E is set of edges and W is set of weights. 4 2 3 1 4 2 2 3 1 4 2 3 3 1 4 1 2 3 1 4 4

I'm currently working on an interesting graph problem, I can't find any algorithms or other stackoverflow questions which mention anything like this. If I have a graph (undirected, cyclic) and a list

I have a directed graph in my PostgreSQL database, there can be multiple paths between nodes and cycles: create table edges (from int, to int); insert into edges values (0, 1), (1, 2), (2, 3),

Please see Image: http://i.stack.imgur.com/NPUmR.jpg I have an undirected graph which contains one or more connected sub graphs. The graph is defined by a set of ordered pairs of connected vertices. T