•  11-09-2019
  •  | 
  •  

문제 

int dfs(int graph[MAXNODES][MAXNODES],int visited[],int start) {
int stack[MAXNODES];
    int top=-1,i;
    visited[start]=1;
    stack[++top]=start;
    while(top!=-1)
    {
  start=stack[top];
        for(i=0;i<MAXNODES;i++) {
   if(graph[start][i]&&visited[i]==0) {
                stack[++top]=i;
                printf("%d-",i);
                visited[i]=1;
                break;
            }
        }
  if(i==MAXNODES)
            top--;
    }
    return 0;
}

위의 코드는 인접 매트릭스로 저장된 그래프의 DFS를 구현합니다. 제안을 요청합니다. 생성 된 그래프가 연결되어 있는지 여부를 알아야하는 변경 사항.

도움이 되었습니까?

해결책

내 참조 대답 밀접하게 연결된 구성 요소에 대한 이전 질문에.

DFS는 또한 i = 0에서 반복적으로 스캔을 시작하기 때문에 작성된대로 매우 비효율적입니다. 당신의 스택은 당신이 중단 된 곳을 기억하고 그곳에서 계속해야합니다. 재귀는 더 자연 스럽지만 통화 스택 크기를 묶은 경우 명백한 스택이 가장 좋습니다 (거대한 나무의 경우).

여기에 재귀 DF가 있습니다. DFS 트리를 저장하는 데 관심이 없다면, 이전에 도달 한 노드 대신 1 1에 1을 저장할 수 있습니다).

const unsigned MAXNODES=100;

/* predecessor must be 0-initialized by the caller; nodes graph[n] that are
 reached from start will have predecessor[n]=p+1, where graph[pred] is the
 predecessor via which n was reached from graph[start].
 predecessor[start]=MAXNODES+1 (this is the root of the tree; there is NO
 predecessor, but instead of 0, I put a positive value to show that it's
 reached).

 graph[a][b] is true iff there is a directed arc from a->b

 */

void dfs(bool graph[MAXNODES][MAXNODES],unsigned predecessor[]
         ,unsigned start,unsigned pred=MAXNODES) 
{
    if (predecessor[start]) return;
    predecessor[start]=pred+1;
    for (unsigned i=0;i<MAXNODES;++i)
        if (graph[start][i])
            dfs(graph,predecessor,i,start);
}

위에서 패턴 화 된 비수체 DFS는 다음과 같습니다. pred 그리고 i (일반적으로 재귀에서 변경할 수있는 모든 로컬 변수 및 매개 변수에 대한 스택 변수가 있습니다) :

void dfs_iter(bool graph[MAXNODES][MAXNODES],unsigned predecessor[]
              ,unsigned start)
{
    unsigned stack[MAXNODES]; // node indices
    unsigned n,pred;
    int top=0;
    stack[top]=start;
    for(;;) {
    recurse:
        // invariant: stack[top] is the next (maybe reached) node
        n=stack[top];
        if (!predecessor[n]) { // not started yet
            pred=top>0?stack[top-1]:MAXNODES;
            //show(n,pred);
            predecessor[n]=pred+1;
            // the first thing we can reach from n
            for (unsigned i=0;i<MAXNODES;++i)
                if (graph[n][i] && !predecessor[i]) {
                    stack[++top]=i; goto recurse; // push
                }
        }
        if (top>0) {
            pred=stack[top-1];
            // the next thing we can reach from pred after n
            for (unsigned i=n+1;i<MAXNODES;++i)
                if (graph[pred][i]) {
                    stack[top]=i; goto recurse; // replace top
                }
            --top;
        } else
            return;
    }
}

이것은 goto없이 구성 될 수 있지만 (그것은 단지 가장 큰 루프에 대한 명명 된 것입니다), 내 의견으로는 더 명확하지 않습니다.

어쨌든, 재귀적인 전화는 훨씬 간단합니다. 재귀적인 의사 코드가 있습니다 Tarjan의 강력하게 연결된 구성 요소 알고리즘 당신은 상당히 직접 녹음 할 수 있습니다. 비거주 적 (명시 적 스택)을 만드는 데 도움이 필요하면 물어보십시오.

다른 팁

한 노드에서 다음 노드로 이동하여 생성 된 가장자리를 저장해야합니다. 그런 다음 그래프의 모든 노드가 가장자리로 연결되어 있는지 확인할 수 있습니다.

Dijkstra의 알고리즘을 실행하십시오. 결국 대기열이 비어 있고 일부 정점이 색상이되지 않으면 그래프가 연결되지 않았습니다. 이는 선형 시간이 보장되며 DFS 접근법은 2 차의 최악의 사례 분석을 가지고 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top