Stack Overflow
Stack Overflow

Questions tagged [strongly-connected-graph]

Strongly connected property for directed graph guarantees that for any two graph nodes a and b routes a to b and b to a are exist.

52 questions
17
votes
2 answers

How to find Strongly Connected Components in a Graph?

I am trying self-study Graph Theory, and now trying to understand how to find SCC in a graph. I have read several different questions/answers on SO (e.g., 1,2,3,4,5,6,7,8), but I cant find one with a complete step-by-step example I could follow.…
lucidgold
  • 4,432
  • 5
  • 31
  • 51
17
votes
9 answers

Algorithm to check if directed graph is strongly connected

I need to check if a directed graph is strongly connected, or, in other words, if all nodes can be reached by any other node (not necessarily through direct edge). One way of doing this is running a DFS and BFS on every node and see all others are…
Kazoom
  • 5,659
  • 16
  • 56
  • 69
5
votes
2 answers

Finding if a graph is still strongly connected after edge removal

A strongly connected digraph is a directed graph in which for each two vertices and , there is a directed path from to and a direct path from to . Let = (, ) be a strongly connected digraph, and let = (, ) ∈ be an edge in the graph. Design an…
Nicole
  • 85
  • 10
4
votes
1 answer

Custom output of edgelist in networkx

I am trying to implement tarjan's algorithm for practice. I decided to generate a random graph to give as input to the algorithm, adding one edge at a time. I generated the random graph and saved it in a file, as shown below from networkx import…
krishna
  • 405
  • 6
  • 25
2
votes
1 answer

Difference between a directed cycle and a strongly connected component

I have this graph. The SCCs in this Graph are {a, b, e}, {d, g}, and {c, d, h}. But the cycles in this graph are the same components, right? So what exactly is the difference between SCCs and directed cycles? Do they only differ in specific cases?
basti394
  • 179
  • 1
  • 1
  • 13
2
votes
1 answer

Find Strongly Connected Graph such that the difference between the maximum and minimum edges is minimum

Given a Directed Weighted Graph which is Strongly Connected. I need to find a strongly connected sub-graph out of this graph such that the difference between the maximum and minimum weight edges is minimum. To be more clearly, I need to get rid of…
UTL
  • 65
  • 7
2
votes
0 answers

Update strongly connected components as edges are added

Let G = (V, E) be a strongly connected directed graph. Start with the graph G' = (V, {}). We are given a list L of edges in E such that every edge in L we add to G' (in order) connects two strongly connected components. What's a fast algorithm to…
F Wheeling
  • 21
  • 1
2
votes
2 answers

Strongly Connected Components : Kosaraju algorithm

In Kosaraju algorithm I came across two possible implementations: 1) Search for strongly connected components in the reversed graph in the topological order of vertices in the original graph. 2) Search for strongly connected components in the…
Chaman Agrawal
  • 86
  • 2
  • 11
2
votes
2 answers

How to reduce a strongly connected component to one vertex?

From https://algs4.cs.princeton.edu/42digraph/ Reachable vertex in a digraph. Design a linear-time algorithm to determine whether a digraph has a vertex that is reachable from every other vertex. Kosaraju-Sharir algorithm gives us the strongly…
Abhijit Sarkar
  • 21,927
  • 20
  • 110
  • 219
2
votes
1 answer

How to extract an adjacency matrix of a giant component of a graph using R?

I would like to extract an adjacency matrix of a giant component of a graph using R. For example, I can create Erdos-Renyi g(n,p) n = 100 p = 1.5/n g = erdos.renyi.game(n, p) coords = layout.fruchterman.reingold(g) plot(g, layout=coords,…
user9307178
2
votes
1 answer

Finding the maximum number of nodes are strongly connected, given number of nodes and edges

"Given the number of nodes and the number of edges connecting these nodes, arrange these edges such that maximum number of nodes are strongly connected. Return the number of nodes that could be strongly connected." I am wondering if is there a…
ty_fam
  • 21
  • 1
1
vote
0 answers

Generate random directed connected graph using networkx?

Context While trying to generate a directed random connected graph in networkx, I am experiencing some difficulties combining the randomness with the "connected" property. I use the following parameters to specify the properties of the graph: size…
a.t.
  • 2,002
  • 3
  • 26
  • 66
1
vote
0 answers

Finding no. of strongly connected components - wrong answer by my code

I was trying to find no. of strongly connected components in a graph. I wrote the below algo but it is failing. The count variable stores the no.of connected components. Count variable is incremented: when any unvisited vertex is found (line 1 in…
Surbhi Jain
  • 369
  • 1
  • 11
1
vote
1 answer

"A connected graph is connected if and only if a depth first search starting from any node visits every other node"

I am reading Mark Weiss's book (2nd Edition) and I can't wrap my head around this thing. How is this even possible. If a graph is undirected then there must be a way to visit every node from everyone. From the image…
harrySherlock
  • 29
  • 3
1
vote
1 answer

Find a path from vertex s to vertex t with minimal number of color alternates

Let be a directed graph, and let be an edge-coloring in red and blue. Let s,t be vertices in G. Find a path from s to t (if exists) so that the number of color changes along this path is minimal. I have tried to do as follows: Let be the graph…
Ido
  • 397
  • 2
  • 7
  • 22
1
2 3 4