如何用分支限界法求最大团问题#include <stdio.h？

Question

用分支限界法求最大团问题

#include <stdio.h>
#include <string.h>
#include<stdbool.h>

#define MAXN 10
#define MAXM 100

typedef struct node {
    int last;          // 最后加入的点
    int v[MAXN + 1];   // v[i]=1 表示顶点 i 已经在该集合中 v[i]=0 则相反
    int num;           // 顶点个数
} node;

typedef struct clique {
    int size;          // 最大团的大小
    int nodes[MAXN];   // 最大团中的顶点
} clique;

int ans = 1;
int n, a[MAXN + 1][MAXM + 1];
node* q[MAXM];

int cmp(const void *a, const void *b)
{
    int n1 = *(int*) a;
    int n2 = *(int*) b;
    if (n1 < n2)
        return -1;
    else if (n1 == n2)
        return 0;
    else
        return 1;
}

void bfs(node *head, clique *clq, int *cnt) {    // 分支界限算法
    for (int i = 0; i < MAXM; i++) {
        q[i] = NULL;
    }
    q[(*cnt)++] = head;

    while (*cnt > 0) {
        node *tem = q[0];     // 取队首
        ans = ans > tem->num ? ans : tem->num;
        if (ans == n) {
            break;
        }
        q[0] = q[--(*cnt)];
        q[*cnt] = NULL;

        int t = tem->last;
        for (int i = 1; i <= n; i++) {
            if (i == t) continue;
            if (a[t][i] == 1 && tem->v[i] == 0) {
                int j;
                for (j = 1; j <= n; j++) {
                    if (tem->v[j] == 1 && a[i][j] == 0){
                        break;
                    }
                }
                if (j > n) {
                    node *nod = (node*)malloc(sizeof(node));
                    memcpy(nod->v, tem->v, sizeof(int) * (MAXN + 1));
                    nod->last = i;
                    nod->v[i] = 1;
                    nod->num = tem->num + 1;
                    q[(*cnt)++] = nod;

                    // 修改2：将当前团加入集合 clq，并重新排序
                    if (ans == nod->num) {
                        memcpy(clq[*cnt - 1].nodes, nod->v, sizeof(int) * (MAXN + 1));
                        clq[*cnt - 1].size = nod->num;
                        qsort(clq, *cnt, sizeof(int), cmp);
                    }
                }
            }
        }
        free(tem);  // 释放结点
    }
}
int main() {
    printf("请输入顶点个数：");
    scanf("%d", &n);

    printf("输入邻接矩阵: \n");
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    for (int i = 1; i <= n; i++) {
        a[0][i] = a[i][0] = 1;  // 根节点与所有的点相连
    }

    node* head = (node*)malloc(sizeof(node));
    memset(head->v, 0, sizeof(head->v));
    head->last = 0;
    head->num = 0;
    int cnt = 0;

    clique clq[MAXM];   // 用来存储所有的最大团
    bfs(head, clq, &cnt);

    // 打印找到的最大团
    printf("最大团的顶点个数为：%d\n", ans);
    for (int i = 1; i <= n; i++) {
        if (clq[i - 1].size == ans) {
            printf("最大团 %d ：", i);
            for (int j = 1; j <= n; j++) {
                if (clq[i - 1].nodes[j] == 1) {
                    printf("%d ", j);  // 输出顶点编号
                }
            }
            printf("\n");
        }
    }

    // 释放内存
    for (int i = 0; i <cnt; i++) {
        free(q[i]);
    }

    return 0;
}

最大团的顶点个数对，但顶点输出的不对，为什么，该如何修改

Answer 1

• 你可以看下这个问题的回答https://ask.csdn.net/questions/775753
• 这篇博客也不错, 你可以看下标准函数库（#include）
• 除此之外, 这篇博客: 文章编辑器的设计与实现中的 #include <stdio.h> 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• 在使用函数库中的输入输出函数时，编译系统要求程序提供有关此函数的信息(例如对这些输入输出函数的声明和宏定义、全局量的定义等)，程序的第一行“#include <stdio.h>”的作用就是提供这些信息的。stdio.h是系统提供的一个文件名，stdio是“standard input & output”的缩写，文件后缀.h的意思是头文件(header file),因为这些文件都是放在程序各文件模块的开头的。输入输出函数的相关信息已事先放在stdio.h文件中。现在，用#include指令把这些信息调入供使用。[1]
  在程序中用到了系统提供的标准函数库中的输入输出函数时，要在程序开头写上一行：#include <stdio.h>或者#include “stdio.h”这样才能调用库函数。