Powered by
/src$ make
  • Home
  • About
  • Directory
  • Contact
  • Home
  • About
  • Directory
  • Contact

C++ Graph Connected Components and Cycles

4/13/2018

 

Introduction: Connected Components and Cycles

In previous blog posts, we've gone over graph theory, adjacency lists, adjacency matrixes, and BFS/DFS. We had another blog post on shortest paths in a graph. We also looked at maximum flow using the Ford Fulkerson Algorithm. 

Today, we'll look at connected components and cycles in a graph. The graph that we'll be playing with is below. 
Picture

Connected Components

A graph has some vertices, named nodes. It also has some edges, that connect nodes. But that doesn't mean that all nodes are reachable from all other nodes, and that everything is connected nicely. For example, we could have 10 nodes, but only 1 edge. That's still a valid graph. 

A "connected component" is a set of vertices/edges that are connected. (The vertices can reach each other through edges.) 

In our code, we'll represent connected components by labeling them with a number. We'll create an array that, for each node in the graph (the node being represented by the index in the array), holds the number for the connected component the node is in.

To find out which connected component each node is in, we'll do a DFS and label each node as we see it.

Note: There's a special case where a node in a connected component does not get reached by other nodes, but is still part of a connected component. For example, node 15 in our group can go to node 14, but no other node can get to 15. We have to make sure that if a node can reach another node that's already part of a connected component, (Basically, someone shows up late to class, the class has people getting together to form groups for a project, but the guy's friend already got them both a group.) 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
// Copyright srcmake 2018.
// C++ Graph Connected Components.

/* Algorithm:
    // 0. Read the graph into an adjacency list.
    // 1. Create an array for each node's component. Initialize it to -1. (This also acts as our "visited" array for DFS.)
    // 2. Create a counter variable (set to -1) for the number of component's we've seen.
    // 3. For each node in our graph...
        // 4. If this node's component is -1, then it hasn't been seen yet. So...
        // 5. Increment the counter by 1.
        // 6. Mark this node's component as counter. 
        // 7. Perform DFS on this node, and mark all of it's neighbor's components as counter.
        // 8. If the neighbor of a vertex already is part of a group (connected component), then this node joins it too.
*/


// The example graph: https://www.srcmake.com/uploads/5/3/9/0/5390645/connectedcomponents_1_orig.jpg

#include <iostream>
#include <vector>

using namespace std;

//////////////////////////////////////////////////////////////////////////////////////////////
vector< vector<int> > FormAdjList()
    {
    vector< vector<int> > adjList;
    
    // We have 10 vertices, so initialize 10 rows.
    const int n = 16;
    
    for(int i = 0; i < n; i++)
        {
        // Create a vector to represent a row, and add it to the adjList.
        vector<int> row;
        adjList.push_back(row);
        }
    
    adjList[0].push_back(4);
    adjList[1].push_back(4);
    adjList[2].push_back(7);
    adjList[3].push_back(1);
    adjList[4].push_back(3);
    adjList[5].push_back(9);
    adjList[6].push_back(12);
    adjList[7].push_back(8);
    adjList[8].push_back(14);
    adjList[9].push_back(5);
    adjList[10].push_back(12);
    adjList[11].push_back(2);
    adjList[12].push_back(10);
    adjList[13].push_back(2);
    adjList[14].push_back(7);
    adjList[15].push_back(14);
    
    return adjList;
    }
//////////////////////////////////////////////////////////////////////////////////////////////
    
    
///////////////////////////////////////////////////////////////////////////////////////////////
// Visit all nodes in a connected component. For each node seen, mark it with counter.
int AdjListDFSComponents(vector< vector<int> > &adjList, int &vertex, int counter, vector<int> &componentArray)
    {
    // 6. Mark this node's component as counter. 
    componentArray[vertex] = counter;
    
    // Is a neighbor already part of a group?
    // For example, node 15 is processed last, but it's part of a group since 14 is part of a group.
    int friendAlreadyGotThemAGroup = -1;
    
    // Look at this vertex's neighbors.
    for(int i = 0; i < adjList[vertex].size(); i++)
        {
        int neighbor = adjList[vertex][i];
        // Recursively call DFS on the neighbor, if it wasn't visited.
        if(componentArray[neighbor] == -1)
            {
            AdjListDFSComponents(adjList, neighbor, counter, componentArray);
            }
        // If this neighbor is part of a group, then this vertex will join that group.
        if(componentArray[neighbor] != -1) 
            {
            friendAlreadyGotThemAGroup = componentArray[neighbor];
            }
        }
        
    // 8. If the neighbor of a vertex already is part of a group (connected component), then this node joins it too.
    if(friendAlreadyGotThemAGroup != -1)
        { componentArray[vertex] = friendAlreadyGotThemAGroup; }
    
    }
//////////////////////////////////////////////////////////////////////////////////////////////


//////////////////////////////////////////////////////////////////////////////////////////////
int main()
    {
    cout << "Program started.\n";
    
    // 0. Read the graph into an adjacency list.
    vector< vector<int> > adjList = FormAdjList();
    int n = adjList.size();
    
    // 1. Create an array for each node's component. Initialize it to -1.
    vector<int> componentArray;
    for(int i = 0; i < n; i++)
        {
        componentArray.push_back(-1);
        }
    
    // 2. Create a counter variable (set to -1) for the number of component's we've seen.
    int counter = -1;
    
    // 3. For each node in our graph...
    for(int i = 0; i < n; i++)
        {
        // 4. If this node's component is -1, then it hasn't been seen yet. So...
        if(componentArray[i] != -1) 
            { continue; }
        
        
        // 5. Increment the counter by 1.
        counter += 1;
        
        // 7. Perform DFS on this node, and mark all of it's neighbor's components as counter.
        AdjListDFSComponents(adjList, i, counter, componentArray);
        }
        
    // Print the results.
    for(int i = 0; i < n; i++)
        {
        cout << "Node " << i << " belongs to component " << componentArray[i] << ".\n";
        }
    
    
    cout << "Program ended.\n";
    
    return 0;
    }
//////////////////////////////////////////////////////////////////////////////////////////////

Cycles

A cycle in a graph happens if it's possible to travel along the edges on a graph where you can revisit a previous node. For example, in our graph above, someone on node 4 can get to node 3, and from node 3 they can get to node 1, and then from node 1 they can get back to node 4. That's a cycle. 

The code to find a cycle is pretty simple. It's just a DFS or BFS, and if we ever "visit" a node that's already been visited before, then we've detected a cycle. 
​Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels. 

Twitter: @srcmake
Discord: srcmake#3644
Youtube: srcmake
Twitch: www.twitch.tv/srcmake
​Github: srcmake

Comments are closed.

    Author

    Hi, I'm srcmake. I play video games and develop software. 

    Pro-tip: Click the "DIRECTORY" button in the menu to find a list of blog posts.
    Metamask tip button
    License: All code and instructions are provided under the MIT License.

    Discord

    Chat with me.


    Youtube

    Watch my videos.


    Twitter

    Get the latest news.


    Twitch

    See the me code live.


    Github

    My latest projects.

Powered by Create your own unique website with customizable templates.