데이터 구조 제6 장 학습 소결

4147 단어
이번 주 에 배 운 것 은 그림 입 니 다. 새로운 개념 이 므 로 먼저 그의 정의 와 기본 용 어 를 알 아야 합 니 다. 우 리 는 주로 용 어 를 말 합 니 다. 이 는 방향 도 와 무 방향 도, 인접 점, 출 도와 입 도, 경로 와 경로 의 길이, 연결 도 와 연결 분량 (여기 서 중점적으로 말 하 겠 습 니 다) 그림 에서 임 의 두 정점 이 V 집합 에 속 하 는 것 을 포함 하고 이에 국한 되 지 않 으 면 그림 은 연 결 된 것 입 니 다. 이른바 연결 분량 이 라 고 합 니 다.무방 향도 중의 큰 연결 서브 맵 을 가리킨다.방향 도 있 는 게 그 자체 야!!더 이상 틀 릴 수 없다)
그 다음 에 그림 의 저장 구 조 는 여기 서 주로 인접 행렬 과 인접 표 가 있 고 인접 행렬 은 주로 두 개의 그룹 이 있 으 며 정점 표 와 인접 행렬 이 있 으 며 가중치 가 있 으 면 행렬 에 해당 하 는 값 을 부여 해 야 한다.그 다음 에 인접 표 입 니 다. 여 기 는 지침 과 관련 되 고 구축 할 때 세 개의 구조 체 가 있 습 니 다. 저 는 개인 적 으로 지정 지침 이라는 것 을 잊 기 쉬 우 며 교과서 로 많이 돌아 가 야 합 니 다.
 
그림 을 옮 겨 다 니 는 데 는 주로 두 가지 알고리즘 인 BFS 와 DFS 가 있다.직접 코드 올 리 기:
void DFS_AM(AMGraph G, int v)
{  // G        
  cout << v << " ";  //   v   
  visited[v] = true;  
  for(w=0; w//        v      
     if((G.arcs[v][w]!=0)&& (!visited[w]))  
         DFS_AM(G, w); //w v    ,  w   ,     DFS_AM 
} 

void DFSTraverse(Graph G)
{  //    G        
  for(v=0; vv) 
     visited[v] = FALSE; //         
  for (v=G.vexnum-1; v>=0; --v) 
     if (!visited[v])  DFS(G, v);  //          DFS
}

BFS, 저 는 개인 적 으로 잘 모 르 니 교과 서 를 많이 봐 야 합 니 다.
void BFS(Graph &G, int j)
{//      
    visited[j] = true;
    queue<int> qu;
    qu.push(j);
    while(qu.size() != 0)
 {
        int mark = qu.front();
        qu.pop();
        cout<" ";
        for(int i=0; i)
  {
            if(G.edges[i][mark] == 1 && visited[i] == false)
   {
                visited[i] = true;
                qu.push(i);
            }
        }
    }
 }

 
그 다음 에 최소 생 성 트 리 는 두 가지 중요 한 방법 이 있 습 니 다. 하 나 는 최소 가중치 를 구성 할 수 있 는 변 의 정점 을 계속 찾 아 집합 U 에 보충 하 는 것 입 니 다.

좋은 웹페이지 즐겨찾기