串鏈的表示法

基本介紹

• 1.矩陣表示法:
  若G(V,E)是含n個頂點的圖，表示圖G的矩陣為mat[n][n]

    存在邊的矩陣為mat[i][j]=1
    不存在邊的矩陣為mat[i][j]=0
  

• 無向圖

  

    無向圖的相鄰矩陣為對稱
  

• 有向圖

  

    有向圖的相鄰矩陣為非對稱
  

• 2.串鏈表示法:

• 無向圖

  

• 有向圖

  

程式範例

利用矩陣表示法轉換成串鏈表示法

印出矩陣表示法

void show(int arr[], int count) {
  for (int i = 0; i < count; i++) {
    for (int j = 0; j < count; j++) {
      printf("%d ", arr[i * count + j]);
    }
    printf("\n");
  }
}

設定初始化初值

void initialization(head_p point[], int visited[]) {
  for (int n = 0; n < count; n++) {
    visited[n] = FALSE;
    //visited[n]為判定追蹤時是否輸出過，此案例中用不到
    point[n] = (head_p)malloc(sizeof(head));
    point[n]->num = vi;
    point[n]->next = NULL;
  }
}

矩陣轉換為串鏈

有點冗長，有機會再把這段函式弄簡潔

void make_list(int count, int arr[], head_p point[]) {
  printf("\nAdjacency List\n");
  head_p soure[MAX];
  //sourse為儲存point初始位置，當point不斷存到next時，最後要有辦法回到初位
  for (int i = 0; i < count; i++) {
    soure[i] = point[i];
    root[i] = point[i];
    point[i]->num = i;
    point[i]->next = (head_p)malloc(sizeof(head));
    point[i] = point[i]->next;
    printf("\n%d", i);
    for (int j = 0; j < count; j++) {
      if (arr[i * count + j] == 1) {
        printf("->%d", j);
        point[i]->next = (head_p)malloc(sizeof(head));
        point[i]->num = j;
        point[i] = point[i]->next;
        point[i]->next = NULL;
      }
    }
    printf("\n");
    point[i] = soure[i];
  }
}

印出串鏈表示

void show_allData(int count, head_p point[], int visited[]) {
  for (int i = 0; i < count; i++) {
    printf("\n----------%d----------\n", i);
    printf("index=%d\tans=%d\n\n", i, visited[i]);
    while (point[i]->next != NULL) {
      printf("list[%d]->num=%d(%p)\n", i, point[i]->num, point[i]);
      point[i] = point[i]->next;
    }
  }
}

ans為visited值，目前用不到