깊이 우선 검색 구현 및 개선 가능성

Question

DFS을 내 마음에 코딩했으며 아이디어를 위해 텍스트 북이나 의사 코드를 언급하지 않았습니다. 불필요한 계산을하는 코드가 있다고 생각합니다. 내 알고리즘의 복잡성을 줄이기위한 아이디어가 있습니까?

vector<int>visited; 

bool isFound(vector<int>vec,int value) 
{ 
    if(std::find(vec.begin(),vec.end(),value)==vec.end()) 
     return false; 
    else 
     return true; 
} 

void dfs(int **graph,int numOfNodes,int node) 
{ 
    if(isFound(visited,node)==false) 
     visited.push_back(node); 
    vector<int>neighbours; 
    for(int i=0;i<numOfNodes;i++) 
     if(graph[node][i]==1) 
      neighbours.push_back(i); 

    for(int i=0;i<neighbours.size();i++) 
     if(isFound(visited,neighbours[i])==false) 
      dfs(graph,numOfNodes,neighbours[i]); 
} 

void depthFirstSearch(int **graph,int numOfNodes) 
{ 
    for(int i=0;i<numOfNodes;i++) 
     dfs(graph,numOfNodes,i); 
} 

PS : 나에게 좋은 품질 C++ 코드를 삽입하는 방법이 할 수 가르쳐 링크를 보내 주시기 바랍니다 누군가 없습니다. 구문 강조 표시를 시도했지만 제대로 작동하지 않았습니다.

Answer 1

귀하의 DFS는 O (n^2) 시간의 복잡성을 가지며 실제로는 좋지 않습니다 (O (n + m)에서 실행되어야 함).

if(std::find(vec.begin(),vec.end(),value)==vec.end()) 

이를 방지하기 위해, 당신은 부울 값의 배열에 방문 있었는지 기억할 수 : 벡터에서 검색하는 것은 그것의 길이에 비례 한 시간이 필요하기 때문에

이 라인은 구현을 유적.

DFS의 두 번째 문제점은 더 큰 그래프의 경우 스택 오버 플로우가 발생할 수 있다는 것입니다. 최악의 경우 재귀 깊이가 그래프의 정점 수와 같기 때문입니다. 이 문제에 대한 해결책은 간단합니다. std::list<int>을 스택으로 사용하십시오.

그래서, DFS가 더 많거나 적은 다음과 같아야 수행하는 코드는 :

// n is number of vertices in graph 
bool visited[n]; // in this array we save visited vertices 

std::list<int> stack; 
std::list<int> order; 

for(int i = 0; i < n; i++){ 
    if(!visited[i]){ 
    stack.push_back(i); 
    while(!stack.empty()){ 
     int top = stack.back(); 
     stack.pop_back(); 
     if(visited[top]) 
     continue; 

     visited[top] = true; 
     order.push_back(top); 
     for(all neighbours of top) 
     if(!visited[neighbour]) 
      stack.push_back(neighbour); 
    } 
    } 
}