アルゴリズム研究-24-

<典型的な資料構造>

<グラフ>

<グラフがなぜ重要なのか>

<図形に関する重要な数学知識>

<グラフィックインプリメンテーション:1。隣接行列>

＜隣接行列の実施＞

#include <stdio.h>
using namespace std;

const int MAX = 10;

bool isConnected(int myGraph[MAX][MAX], int x, int y){
  // x, y가 연결이 되어 있으면 true, 아니면 false
  // * 2차원 배열 넘길때 크기 적어주자
  
  return myGraph[x][y] == 1 ? true : false;
  
  
  // 조건 ? 값1 : 값2  -> true면 값1 출력
}

void getAdj(int myGraph[MAX][MAX], int n, int x){
  // 인접 정점   // n =총 정점 개수
  for(int i = 1; i<=n; i++){
    if(myGraph[x][i] == 1)
      printf("%d ", i);
  }
}

int main() {

  int n, m; // n-정점 개수   m-간선 개수
  
  int myGraph[MAX][MAX] = {0,};
  
  scanf("%d %d", &n, &m);
  
  for(int i = 0; i<m; i++){
    int a,b;
    scanf("%d %d", &a, &b); // a와b가 연결 됨
    
    myGraph[a][b] = 1;
    myGraph[b][a] = 1;
  }
  
  for(int i = 1; i<=n; i++){
    for(int j = 1; j<=n; j++){
      printf("%d ", myGraph[i][j]);
    }
    printf("\n");
  }
  
  // q1. 정점 x, y 연결 되어 있나?
  // q2. 정점 x와 연결이 되어 있는 모든 정점 출력
  
  printf("%d\n", isConnected(myGraph, 1,2));
  
  getAdj(myGraph, n, 2);
  
  

  return 0;
}

<グラフィックインプリメンテーション:2。隣接リスト>

<隣接リストの実装>

カプセル化により実現
＜ベースSTL＞

<ベクトル>

#include <stdio.h>
#include <vector>   // check!!

using namespace std;


int main() {
  
  vector <int> myArray(10);
  
  myArray[0] = 3;
  
  for(int i = 0; i<=9; i++)
    myArray[i] = i;
  
  myArray.push_back(10);  // 맨 끝에 한 칸 추가
  // 크기 조절이 가능!
  
  for(int i = 0; i<=10; i++)
    printf("%d ", myArray[i]);
  
  return 0;
}

vector <int> myArray(10,3) = 10칸을 모두 3으로 초기화

myArray.push_back(x) = 맨 마지막에 x를 추가

myArray.pop_back() = 맨 끝을 뺀다 / 공간도 사라진다

myArray.resize(x) = 크기를 x로 변경

myArray.size() = 현재 배열 크기 반환 / 원소가 있든 없든 모든 공간 크기



vector <int> myArray2() = 빈 공간의 배열 생성 (크기 0)

myArray2.resize(n, m) = n-1 인덱스 까지 늘리고 빈 공간은 m으로 모두 채운다

#include <stdio.h>
#include <vector>

using namespace std;

int main() {

  vector <int> arr;
  
  arr.push_back(1);
  arr.push_back(2);
  arr.push_back(3);
  
  printf("%d\n", arr.size());
  
  arr.pop_back();
  
  printf("%d\n", arr.size());
  
  arr.resize(10, 5);
  
  for(int i = 0; i < arr.size(); i++)
    printf("%d ", arr[i]);
  
  printf("\n");
  
  arr.resize(5, 3);
  
   for(int i = 0; i < arr.size(); i++)
    printf("%d ", arr[i]);
  
  printf("\n");
  

  return 0;
}

<隣接リスト実装コード>

#include <stdio.h>
#include <vector>

using namespace std;

int main() {

  // 1: 2 3 4
  // 2: 1 4
  // 3: 1 5
  // 4: 1 2 5
  // 5: 3 4
  
  vector <int> myGraph[10];
  // vector <int> 가 10개 생성
  
  // myGraph[x] = x와 인접한 모든 노드를 저장
  
  int n, m;  // 노드 수, 간선 수
  
  scanf("%d %d", &n, &m);
  
  for(int i = 0; i<m; i++){
    int a, b;
    scanf("%d %d", &a, &b); // a 와 b 가 인접!
    
    myGraph[a].push_back(b);
    myGraph[b].push_back(a);
  }
  
  
  for(int i = 1; i<=n; i++){
    printf("%d: ", i);
    
    for(int j = 0; j < myGraph[i].size(); j++){
      printf("%d", myGraph[i][j]);
    }
    
    printf("\n");
  }

  return 0;
}