그림 의 깊이 우선 달력 과 넓이 우선 달력 및 복잡 도 분석

여기에 그림 을 옮 겨 다 니 면서...
잔말 말고 바로 올 라 가 ~ ~ 먼저 그림 의 구조 유형:

typedef struct ANode{
    int  adjvex;            //  
    struct ANode *nextarc;  //    
    Elemtype weight;        //  
}ArcNode;

typedef struct VNode{
    Elemtype data;          //     
    ArcNode *firstarc;      //        
};

typedef struct{
    VNode adjlist[MAX];
    int n;int e;
}ArcGraph;

그림 생 성 (인접 링크):

void CreateAdj(ArcGraph *&G,int A[MAXV][MAXV],int n,int e){
    ArcNode *p;
    G=new ArcGraph;// G      
    for(int i=0;iadjlist[i].firstarc=NULL;
    for(int i=0;i=0;j--)
            if(A[i][j]!=0&&A[i][j]!=MAX)//         
            {
                p = new ArcNode;//    
                p->adjvex = j;//    
                p->weight = A[i][j];//    
                p->nextarc = G->adjlist[i].firstarc;//     
                G->adjlist[i].firstarc = p;
            }
    G->n=n;G->e=e;
}

포 출 두 가지 알고리즘

깊이 스 트 리밍 알고리즘 (재 귀)

재 귀 깊이 는 이 몇 단계 로 나 뉘 어 있 습 니 다. 먼저 방문 배열 = 0 을 초기 화한 다음 에 방문 배열 의 방문 정점 = 1 에 이 어 이 정점 의 인접 점 w 를 마지막 으로 순환 재 귀 하 는 while (w 존재) {if (w 접근 되 지 않 음) 재 귀 w 를 다음 인접 점 으로 이동 합 니 다}

int visitedDPS[MAX]={0};//      
void DFS(ArcGraph *G,int v){
    ArcNode *p;
    visitedDPS[v]=1;//    
    cout<adjlist[v].firstarc;//       
    while (p!=NULL)
    {
        if(visitedDPS[p->adjvex]==0)//       0
            DFS(G,p->adjvex);//    
        p=p->nextarc;//       
    }
}

넓이 우선 옮 겨 다 니 기

우선 방문 배열 = 0 을 초기 화하 고 정점 = 1 을 방문 합 니 다.

int visitedBFS[MAX]={0};//      

void BFS(ArcGraph *G,int v){
   ArcNode *p;
   queueque;//     
   //int visited[MAX];
   for(int i=0;in;i++)visitedBFS[i]=0;//       
   cout<adjvex        debug   segfault(     )
                        front            !!
        */
       int w=que.front();//            !!!!
       que.pop();//  w   
       p = G->adjlist[w].firstarc;//  w       
       while (p != NULL) {
           if (visitedBFS[p->adjvex] == 0)//         ，     
           {
               cout << p->adjvex<< " " ;
               visitedBFS[p->adjvex] = 1;
               que.push(p->adjvex);//    
           }
           p = p->nextarc;//        
       }
   }
}

여기 주 함수 호출

int main(){
    int A[5][5]={{ 0 , 8 ,MAX, 5 ,MAX},
                 {MAX, 0 , 3 ,MAX,MAX},
                 {MAX,MAX, 0 ,MAX, 6 },
                 {MAX,MAX, 9 , 0 ,MAX},
                 {MAX,MAX,MAX,MAX, 0 }};
    ArcGraph *G;
    int n=5,e=5;
    CreateAdj(G,A,n,e);
    cout<

깊이 우선 스 트 리밍 에서 재 귀 하 는 방법 을 사 용 했 습 니 다. 이 알고리즘 은 시간 복잡 도 는 O (n) 입 니 다.²),범위 우선 옮 겨 다 니 는 중 배열 을 표시 하 는 방법 을 사 용 했 습 니 다. 이 알고리즘 은 시간 복잡 도 는 O (n + e) 입 니 다.그 중에서 e 는 그림 속 의 개수 이다. 공간 복잡 도 에 있어 이들 의 저장 유형 은 모두 같 기 때문에 공간 복잡 도 는 같다. 두 개의 알고리즘 을 종합 적 으로 비교 하면 각각 장점 이 있 고 얻 은 결과 가 다 르 기 때문에 실제 사용 할 때 문제 의 실현 방법 을 고려 하여 두 가지 알고리즘 을 종합 적 으로 고려 해 야 한다.