Connexe de Matrices

Composants Connexes

找连通分量（通过深度、广度搜索）

伪代码

//找连通分量
procédure ComposantesConnexes(Graphe g)
Début
    //Initialisation
    n ← nbSom(g)
    visite ← allocTab(n)
    pour chaque sommet s variant de 1 à n faire
        visite[s] ← faux
    finPour
    s ← 1
    nbSomVisite ← 0
    finParcours ← faux
    //Traitement
    Tantque non finParcours faire
        reParcoursProfondeur(s, visite, g, nbSomVisite, ....) //A modifier
        // itParcoursProfondeur(s, visite, g, nbSomVisite, ....) //A modifier
        // parcoursLargeur((s, visite, g, nbSomVisite, ....)) //A modifier

        Si nbsomVisite < n
            traiter("\n")
            s ← somSuivant(s, n, visite)
        Sinon
            finParcours ← Vrai
        FSi
    FinTq
    Visite ← libTab (tab)
Fin

C语言实现

// 分配布尔数组
int* allocTab(int n) {
    return (int*)malloc(n*sizeof(int));
}

// 释放布尔数组
void libTab(int* tab) {
    free(tab);
}

//Composantes connexes
//寻找连通分量
void trouverComposantesConnexes(MatAdj g) {
    int n = g.nbSom;
    int* visite = allocTab(n);
    int nbSomVisite = 0;
    int s = 0;
    int finParcours = 0;

    while (!finParcours) {
        // 选择 DFS 或 BFS
        reParcoursProfondeur_MA(s, visite, g, n , &nbSomVisite);
        // itParcoursProfondeur_MA(s, visite, g, n, &nbSomVisite);
        // itParcoursLargeur_MA(s, visite, g, n, &nbSomVisite);

        if (nbSomVisite < n) {
            printf("\n");
            s = somSuivant(s, n, visite);
        } else {
            finParcours = 1;
        }
    }

    libTab(visite);
}

测试代码

#include "Connexes.h"
int main() {
    int n = 5;
    MatAdj ma;
    ma.nbSom = n;
    ma.mat = (int **)malloc(n * sizeof(int *));
    for (int i = 0; i < n; i++) {
        ma.mat[i] = (int *)malloc(n * sizeof(int));
    }

    // 初始化矩阵（无向图不带自环）
    int adj[5][5] = {
                {0, 1, 0, 0, 0},
                {1, 0, 1, 0, 0},
                {0, 1, 0, 0, 0},
                {0, 0, 0, 0, 1},
                {0, 0, 0, 1, 0}
    };

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ma.mat[i][j] = adj[i][j];
        }
    }

    printMatAdj(ma);
    printf("Composant connexe:\n");
    trouverComposantesConnexes(ma);
}

ComposanteFortementConnexe

Kosaraju算法

Kosaraju算法可以求出有向图中的强连通分量个数，并且对分属于不同强连通分量的点进行标记。它的算法描述较为简单：

(1) 第一次对图G进行DFS遍历，并在遍历过程中，记录每一个点的退出顺序。以下图为例：

如果以1为起点遍历，访问结点的顺序如下：

结点第二次被访问即为退出之时，那么我们可以得到结点的退出顺序：

(2)倒转每一条边的方向，构造出一个反图G’。然后按照退出顺序的逆序对反图进行第二次DFS遍历。我们按1、4、2、3、5的逆序第二次DFS遍历：

每次遍历得到的那些点即属于同一个强连通分量。1、4属于同一个强连通分量，2、3、5属于另一个强连通分量。

伪代码

// 寻找下一个未访问的顶点，用于构建后缀序遍历（第一遍深度优先搜索）
fct somSuivant_PPG (s, n, visite)
Début
    Pour i variant de s + 1 à n - 1 faire
        Si non visite[i] alors
            Retourner i
        Finsi
    Ffinpour
    Retourner s
Fin

// 寻找下一个用于转置图深度优先搜索的顶点，基于后缀序列表L
fct somSuivant_PPTG (s, n, visite, L)
Début
    Pour i variant de s - 1 à 0 faire
        Si non visite[L[i]] alors
            Retourner i
        Finsi
    Ffinpour
    Retourner s
Fin

// 深度优先搜索后缀序遍历
procédure parcoursProfondeurSuffixe(s, visite, G, L, nbSomVisite)
Début
    Visite[s] ← vrai
    Pour chaque t ∈ Γ(s) dans G faire
        Si non visite[t] alors
            parcoursProfondeurSuffixe(t, visite, G, L, nbSomVisite)
        Finsi
    Finpour
    nbSomVisite ← nbSomVisite + 1
    L[nbSomVisite] ← s
Fin

//对图 G 的转置图进行深度优先遍历
procédure parcoursProfondeurTransposeG (s, visite, G, CFC, NumCFC, nbSomVisite)
Début
    Visite[s] ← vrai
    CFC[s] ← NumCFC
    nbSomVisite ← nbSomVisite + 1
    Pour chaque t prédécesseur de s dans G faire
        Si non visite[t] alors
            parcoursProfondeurTransposeG (t, visite, G, CFC, NumCFC, nbSomVisite)
        Finsi
    Finpour
FIN

procédure ComposanteFortementConnexe(G, CFC, nbCFC)
Début
    //initialisation
    n ← nbSom (G)
    visite ← allocTab (n)
    Pour s variant de 1 à n faire
        visite[s] ← faux
    Fpour
    nbSomVisite← 0
    finParcours ← faux
    s ← 1
    //Construction de la liste L des sommets en ordre suffixe de G
    Tantque (non finParcours) faire
        parcoursProfondeurSuffixe(s, visite, G, L, nbSomVisite)
        Si nbsomVisite < n alors
            s ←somSuivant_PPG(s, n, visite)
        Sinon
            finParcours ← Vrai
        FSi
    Fintq
    //Parcours en profondeur de tG
    // initialisation
    pour s variant de 1 à n faire
        visite[s] ← faux
    fpour
    nbCFC ← 0
    nbSomVisite← 0
    finParcours ← faux
    s ← n
    Tantque (non finParcours) faire
        nbCFC ← nbCFC + 1
        ParcoursProfondeurTransposeG(L[s], visite, G, CFC, nbCFC, nbSomVisite)
        Si nbsomVisite < n alors
            s ←somSuivant_PPTG(s, n, visite, L)
        Sinon
            finParcours ← Vrai
        FSi
    FinTq
    Visite ← libTab(n)
Fin
*/

C语言实现

// 寻找下一个未访问的顶点，用于构建后缀序遍历（第一遍深度优先搜索）
int somSuivant_PPG(int s, int n, int *visite) {
    for (int i = s + 1; i < n; i++) {
        if (!visite[i]) {
            return i;
        }
    }
    return s; // 如果没有找到未访问的顶点，返回当前顶点（理论上不应出现这种情况，除非逻辑错误）
}

// 寻找下一个用于转置图深度优先搜索的顶点，基于后缀序列表L
int somSuivant_PPTG(int s, int n, int *visite, int *L) {
    for (int i = s - 1; i >= 0; i--) {
        if (!visite[L[i]]) {
            return i;
        }
    }
    return s; // 如果没有找到合适的顶点，返回当前顶点（理论上不应出现这种情况，除非逻辑错误）
}


//Parcours en Profondeur en ordre Suffixe
//后序遍历（对图G进行DFS遍历，并在遍历过程中，记录每一个点的退出顺序）
// 深度优先搜索后缀序遍历
void parcoursProfondeurSuffixe(int s, int *visite, MatAdj G, int *L, int *nbSomVisite) {
    visite[s] = 1;
    for (int t = 0; t < G.nbSom; t++) {
        if (G.mat[s][t]==1 && !visite[t]) {
            parcoursProfondeurSuffixe(t, visite, G, L, nbSomVisite);
        }
    }
    L[(*nbSomVisite)++] = s;
}

//对图 G 的转置图进行深度优先遍历
void parcoursProfondeurTransposeG(int s, int *visite, MatAdj G, int *CFC, int NumCFC, int *nbSomVisite) {
    visite[s] = 1;
    CFC[s] = NumCFC;  // 记录强连通分量编号
    (*nbSomVisite)++;
    for (int t = 0; t < G.nbSom; t++) {
        if (G.mat[t][s]==1 && !visite[t]) {
            parcoursProfondeurTransposeG(t, visite, G, CFC, NumCFC, nbSomVisite);
        }
    }
}

void ComposanteFortementConnexe(MatAdj G, int *CFC, int *nbCFC) {
    int n = G.nbSom;
    int *visite = (int *)malloc(n * sizeof(int));
    int *L = (int *)malloc(n * sizeof(int));  // 用于记录后序遍历的顶点顺序
    int nbSomVisite = 0;
    int finParcours = 0;
    int s = 0;

    // 初始化访问数组
    for (int i = 0; i < n; i++) {
        visite[i] = 0;
    }

    // 构建后缀序顶点列表
    while (!finParcours) {
        parcoursProfondeurSuffixe(s, visite, G, L, &nbSomVisite);
        if (nbSomVisite<n) {
           s=somSuivant_PPG(s,n,visite);
        }else{
            finParcours = 1;
        }
    }

    // 重置访问数组
    for (int i = 0; i < n; i++) {
        visite[i] = 0;
    }

    *nbCFC = 0;
    nbSomVisite = 0;
    finParcours = 0;
    s = n-1;

    // 对转置图进行深度优先搜索
    while (!finParcours) {
        (*nbCFC)++;
        parcoursProfondeurTransposeG(L[s], visite, G, CFC, *nbCFC, &nbSomVisite);
        if (nbSomVisite<n) {
            s=somSuivant_PPTG(s,n,visite,L);
        }else{
            finParcours = 1;
        }
    }

    free(visite);
    free(L);
}

测试代码

#include "Connexes.h"
// 输出结果的测试函数
void printResults(int *CFC, int nbSom, int nbCFC) {
    // 先输出CFC数组
    printf("CFC= [");
    for (int i = 0; i < nbSom; i++) {
        printf("%d", CFC[i]);
        if (i < nbSom - 1) {
            printf(", ");
        }
    }
    printf("]\n");

    // 按CFC编号分组输出每个强连通分量包含的顶点
    for (int i = 1; i <= nbCFC; i++) {
        printf("CFC%d = {", i);
        int first = 1;
        for (int j = 0; j < nbSom; j++) {
            if (CFC[j] == i) {
                if (!first) {
                    printf(", ");
                }
                printf("%d", j + 1);
                first = 0;
            }
        }
        printf("}\n");
    }

    // 输出强连通分量的数量
    printf("nbCFC = %d\n", nbCFC);
}

int main() {
    // 示例图的初始化
    int n = 8;
    MatAdj ma;
    ma.nbSom = n;
    ma.mat = (int **)malloc(n * sizeof(int *));
    for (int i = 0; i < n; i++) {
        ma.mat[i] = (int *)malloc(n * sizeof(int));
    }
    
    int adj[8][8] = {
        {0, 0, 0, 0, 0, 1, 1, 1},  // 顶点 1 的出边 (1 → 6, 1 → 7, 1 → 8)
        {1, 0, 0, 1, 0, 0, 0, 0},  // 顶点 2 的出边 (2 → 1, 2 → 4)
        {0, 1, 0, 0, 0, 0, 0, 0},  // 顶点 3 的出边 (3 → 2)
        {0, 0, 1, 0, 1, 0, 0, 0},  // 顶点 4 的出边 (4 → 3, 4 → 5)
        {1, 0, 0, 0, 0, 0, 0, 0},  // 顶点 5 的出边 (5->1)
        {0, 0, 0, 0, 1, 0, 1, 0},  // 顶点 6 的出边 (6 → 5, 6 → 7)
        {0, 0, 0, 0, 0, 0, 0, 0},  // 顶点 7 没有出边
        {0, 0, 0, 0, 0, 1, 1, 0}   // 顶点 8 的出边 (8 → 6, 8 → 7)
    };

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ma.mat[i][j] = adj[i][j];
        }
    }

    int *CFC = (int *)malloc(ma.nbSom * sizeof(int));
    int nbCFC;

    ComposanteFortementConnexe(ma, CFC, &nbCFC);

    // for (int i=0;i<8;i++) {
    //     printf("%d ",CFC[i]);
    // }
    printResults(CFC, ma.nbSom, nbCFC);


    // 释放内存
    for (int i = 0; i < ma.nbSom; i++) {
        free(ma.mat[i]);
    }
    free(ma.mat);
    free(CFC);

    return 0;
}

//输出结果
CFC= [2, 1, 1, 1, 2, 2, 3, 2]
CFC1 = {2, 3, 4}
CFC2 = {1, 5, 6, 8}
CFC3 = {7}
nbCFC = 3