グラフに含まれる最大のクリーク(完全グラフ)を求める最大クリーク問題を解くプログラムを実現したいです.これはNP完全問題です.
隣接行列を使い、解きたいです。
c
1#include<stdio.h> 2 3#define N 100 4 5int a[N][N]={ 6}; 7 8int v[N]; 9 10 11for(j = 1; j <= N; j++){ 12 if( a[i][j] == 1 && v[j] == 0 ){ 13 //printf("%d->%d\n ", i, j); 14 15 } 16 } 17 18int main(void) 19 { 20 int i; 21 22 for(i = 0; i < N; i++){ 23 V[i] = 0; 24 } 25 } 26
全然できていませんがここまでしかわかりませんでした。
隣接行列は
{0,0,0,1,0,1,0,1,0,0,0,0,0,1,1,1,1,0,0,1,0,0,0,1,1,1,1,0,0,0},
{0,0,1,1,0,1,0,0,0,1,0,0,0,1,1,1,0,0,1,1,0,1,1,1,1,1,1,0,1,0},
{0,1,0,0,1,1,1,0,0,0,1,1,0,1,0,0,0,0,1,0,0,1,0,0,1,0,1,0,1,1},
{1,1,0,0,1,0,0,0,1,1,1,0,0,1,1,0,1,0,1,1,0,1,0,0,1,1,0,0,0,1},
{0,0,1,1,0,1,1,1,1,0,1,1,0,1,1,1,1,1,0,1,0,0,0,0,0,0,0,1,0,1},
{1,1,1,0,1,0,1,0,1,1,0,1,0,1,1,1,1,0,1,1,0,1,0,1,0,1,1,1,1,0},
{0,0,1,0,1,1,0,1,0,1,0,0,0,0,1,0,1,0,1,1,1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,1,0,1,1,0,0,0,1,0,0,1,0,0,0,0,0,1,1,1,0,0,0,0,1},
{0,0,0,1,1,1,0,1,0,0,0,1,0,0,1,1,0,1,0,0,0,1,0,0,0,1,0,0,1,0},
{0,1,0,1,0,1,1,1,0,0,1,0,1,1,1,1,0,1,0,0,1,1,0,0,1,1,1,0,1,1},
{0,0,1,1,1,0,0,0,0,1,0,1,1,1,0,1,0,1,0,0,0,0,0,0,0,1,1,1,1,0},
{0,0,1,0,1,1,0,0,1,0,1,0,1,0,0,1,1,1,1,0,1,1,0,1,0,0,1,1,0,1},
{0,0,0,0,0,0,0,0,0,1,1,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1,0,0,0,0},
{1,1,1,1,1,1,0,1,0,1,1,0,1,0,0,1,1,0,1,1,1,1,1,1,0,1,0,1,1,0},
{1,1,0,1,1,1,1,0,1,1,0,0,0,0,0,1,1,0,1,1,1,1,0,1,1,0,1,0,0,1},
{1,1,0,0,1,1,0,0,1,1,1,1,0,1,1,0,0,0,1,1,1,1,0,1,1,1,1,1,1,0},
{1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,1,0,1,0,1,0,0},
{0,0,0,0,1,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,1,1,0,0,0,0,1,1,0,0},
{0,1,1,1,0,1,1,0,0,0,0,1,1,1,1,1,0,0,0,1,1,1,0,1,1,1,1,0,1,0},
{1,1,0,1,1,1,1,0,0,0,0,0,1,1,1,1,1,0,1,0,0,1,0,0,0,1,1,1,0,1},
{0,0,0,0,0,0,1,0,0,1,0,1,1,1,1,1,1,1,1,0,0,0,1,1,0,1,1,0,0,0},
{0,1,1,1,0,1,0,0,1,1,0,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,0,1,1,0},
{0,1,0,0,0,0,1,1,0,0,0,0,1,1,0,0,1,0,0,0,1,0,0,1,1,1,1,1,0,0},
{1,1,0,0,0,1,1,1,0,0,0,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,0,0,1,1},
{1,1,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,0,1,0,0,1,1,1,0,1,1,1,1,0},
{1,1,0,1,0,1,0,0,1,1,1,0,1,1,0,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1},
{1,1,1,0,0,1,0,0,0,1,1,1,0,0,1,1,0,1,1,1,1,0,1,0,1,1,0,0,1,1},
{0,0,0,0,1,1,0,0,0,0,1,1,0,1,0,1,1,1,0,1,0,1,1,0,1,1,0,0,0,0},
{0,1,1,0,0,1,0,0,1,1,1,0,0,1,0,1,0,0,1,0,0,1,0,1,1,1,1,0,0,0},
{0,0,1,1,1,0,1,1,0,1,0,1,0,0,1,0,0,0,0,1,0,0,0,1,0,1,1,0,0,0}
で、N=30です。
あなたの回答
tips
プレビュー