Skip to main content
Computer Science

Return to Question

deleted 6 characters in body
Source Link
kev
kev
  • 115
  • 5

I'm not a computer scientist, so please bear with me if I'm using misusing some terminology.

What I'm trying to do is to find the different components of an undirected graph.

I have an array of pairs that represent the edges of my graph, like so: [[1,3],[4,2],[2,1],[5,6],[100,20],[22,5]] and what I want to create out of this are arrays (or objects) containing the connected vertexes (the disjoint sets or components, like this (for the above example): [[1,2,3,4],[5,6,22],[20,100]]

My first approach was to convert the array of pairs into an adjacency list, using hashmaps/tables/sets or something in this line it can be done in O(n) time and additional space (n being the number of pairs). Then using BFS, I scan every vertex in the graph. Whenever the queue is empty, I have completed a component/disjoint set. If unvisited nodes are still in the graph, this is a new component/disjoint set. Until all the nodes are visited.

Now, I learned about the disjoint-set data structure.

My question: Using disjoint-set data structure how can I convert my array of pairs into the disjoint components of the graph I'm looking for? Any resources are also very much appreciated. I'm still learning and don't really know what I'm talking about.

What are the pros and cons of the first approach compared to the second approach.

Oh, BTW, if this is the wrong place to ask this question, please, advise!

Thanks in advance!

I'm not a computer scientist, so please bear with me if I'm using misusing some terminology.

What I'm trying to do is to find the different components of an undirected graph.

I have an array of pairs that represent the edges of my graph, like so: [[1,3],[4,2],[2,1],[5,6],[100,20],[22,5]] and what I want to create out of this are arrays (or objects) containing the connected vertexes (the disjoint sets or components, like this (for the above example): [[1,2,3,4],[5,6,22],[20,100]]

My first approach was to convert the array of pairs into an adjacency list, using hashmaps/tables/sets or something in this line it can be done in O(n) time and additional space (n being the number of pairs). Then using BFS, I scan every vertex in the graph. Whenever the queue is empty, I have completed a component/disjoint set. If unvisited nodes are still in the graph, this is a new component/disjoint set. Until all the nodes are visited.

Now, I learned about the disjoint-set data structure.

My question: Using disjoint-set data structure how can I convert my array of pairs into the disjoint components of the graph I'm looking for? Any resources are also very much appreciated. I'm still learning and don't really know what I'm talking about.

What are the pros and cons of the first approach compared to the second approach.

Oh, BTW, if this is the wrong place to ask this question, please, advise!

Thanks in advance!

I'm not a computer scientist, so please bear with me if I'm misusing some terminology.

What I'm trying to do is to find the different components of an undirected graph.

I have an array of pairs that represent the edges of my graph, like so: [[1,3],[4,2],[2,1],[5,6],[100,20],[22,5]] and what I want to create out of this are arrays (or objects) containing the connected vertexes (the disjoint sets or components, like this (for the above example): [[1,2,3,4],[5,6,22],[20,100]]

My first approach was to convert the array of pairs into an adjacency list, using hashmaps/tables/sets or something in this line it can be done in O(n) time and additional space (n being the number of pairs). Then using BFS, I scan every vertex in the graph. Whenever the queue is empty, I have completed a component/disjoint set. If unvisited nodes are still in the graph, this is a new component/disjoint set. Until all the nodes are visited.

Now, I learned about the disjoint-set data structure.

My question: Using disjoint-set data structure how can I convert my array of pairs into the disjoint components of the graph I'm looking for? Any resources are also very much appreciated. I'm still learning and don't really know what I'm talking about.

What are the pros and cons of the first approach compared to the second approach.

Oh, BTW, if this is the wrong place to ask this question, please, advise!

Thanks in advance!

Source Link
kev
kev
  • 115
  • 5

How to create disjoint sets out of an adjacency list

I'm not a computer scientist, so please bear with me if I'm using misusing some terminology.

What I'm trying to do is to find the different components of an undirected graph.

I have an array of pairs that represent the edges of my graph, like so: [[1,3],[4,2],[2,1],[5,6],[100,20],[22,5]] and what I want to create out of this are arrays (or objects) containing the connected vertexes (the disjoint sets or components, like this (for the above example): [[1,2,3,4],[5,6,22],[20,100]]

My first approach was to convert the array of pairs into an adjacency list, using hashmaps/tables/sets or something in this line it can be done in O(n) time and additional space (n being the number of pairs). Then using BFS, I scan every vertex in the graph. Whenever the queue is empty, I have completed a component/disjoint set. If unvisited nodes are still in the graph, this is a new component/disjoint set. Until all the nodes are visited.

Now, I learned about the disjoint-set data structure.

My question: Using disjoint-set data structure how can I convert my array of pairs into the disjoint components of the graph I'm looking for? Any resources are also very much appreciated. I'm still learning and don't really know what I'm talking about.

What are the pros and cons of the first approach compared to the second approach.

Oh, BTW, if this is the wrong place to ask this question, please, advise!

Thanks in advance!