DFS를 사용한 SCC 계산

깊이 우선 검색을 사용하여 5 개의 가장 강력하게 연결된 구성 요소의 크기를 계산하기 위해 C에 프로그래밍 코드를 만들어야합니다. 프로그래밍을 위해 Ubuntu 12.04를 사용합니다. 나는 다음 코드를 보았고 터미널에 보여준 결과는 Segmentation Fault (core dumped)이었다. 이것은 graph[MaxVer][MaxVer][2]을 함수 호출에 넣었을 때 무슨 일이 일어나는지 보려고하는 동안이었다.DFS를 사용한 SCC 계산

CODE

#include "stdio.h" 
#include "stdlib.h" 
#define MaxVer 875714 

long int t=0; 
long int visited[MaxVer][2]={0}; 
long int s=NULL; 
long int leader[MaxVer]; 
long int time[MaxVer]; 
int count; 

main() 
{ 
    long int i,j,k; 
    long int Graph[MaxVer][MaxVer][2]={0}; 
    FILE *fp; 

    fp=fopen("SCC.txt","r"); 

    fscanf(fp,"%ld",&j); 
    for(i=1;i<=875714;i++) 
     while(i==j) 
     { 
      fscanf(fp,"%ld",&k); 
      Graph[i-1][k-1][0]=1; 
      fscanf(fp,"%ld",&j); 
     } 
    fclose(fp); 

    DFS_loop(Graph,0); 
    for(i=0;i<MaxVer;i++) 
     for(j=0;j<MaxVer;j++) 
      if(Graph[(time[i])][(time[j])][0]=1) 
       Graph[i][j][1]=1; 
    DFS_loop(Graph,1); 
} 

DFS_loop(long int graph[][][],long int i) 
{ 
    long int node; 
    for(node=MaxVer;node>0;node--) 
     if(!visited[node-1][i]) 
     { 
       s=node; 
       DFS(graph,i,node); 
       if(i==1&&count<5) 
        printf("%ld",t); 
     } 
} 

DFS (long int graph[][][],long int i,long int node) 
{ 
    long int node_2; 
    visited[node-1][i]=1; 
    leader[node-1]=s; 

    for(node_2=1;node_2<=MaxVer;node_2++) 
     if(graph[node_2-1][node-1][i]==1) 
      if(!visited[node_2-1][i]) 
      { 
       DFS(graph,i,node_2); 
       if(i==1&&count<5) 
       { 
        t++; 
        count++; 
       } 
      } 
    if(i==0) 
    { 
     t++; 
     time[t-1]=node; 
    } 
}

END

사람이 코드의 문제가 무엇인지 말해 줄 수 있을까요? DFS 및 DFS_loop 호출 중 컴파일하는 동안의 주 문제점이 발생합니다. 그것은 "배열 유형이 불완전한 요소 유형"이라고 말합니다. 그리고 네, 875714 개의 정점을 가진 파일로 입력이 주어 졌음을 알려드립니다. 입력의 예는 2 74657입니다. 여기서 2는 꼬리이고 74657은 지향 에지의 헤드입니다.

더 나은 프로그램을 제안 할 수있는 사람이 있으면 제공해 주시기 바랍니다.

출처

2013-03-03 Akshit

에 오신 것을 환영합니다! 코드에서 오류를 발견하도록 사람들에게 요청하는 것은 특히 생산적이지 않습니다. 디버거를 사용하여 (또는 인쇄 문을 추가하여) 문제를 격리 한 다음 [최소 테스트 케이스] (http://sscce.org)를 구성해야합니다. –

컴파일하지 않을 때 어떻게 디버깅합니까? – Akshit

첫 번째 단락에서 런타임 오류 인 seg 오류가 발생한다고 말합니다. 실행하려면 컴파일해야합니다 ... –

main() 전에 적절한 함수 프로토 타입을 확인하고 2 층과 3 차원의 크기를 지정 (사용 graph[MaxVer][MaxVer][] 대신 graph[][][]) 스택 오버플로

출처

2013-03-03 19:37:05

DFS를 사용한 SCC 계산

답변

관련 문제