串链的表示法

基本介绍

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值，目前用不到