图的三种存储方式

之前总结过一次。详见本博客或者是另一篇。

不过呢。写起来。还是今天的简单易写（学长教的）。

测试数据my.txt.

邻接矩阵：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 100

const int INF = (1<<23);

int G[MAXN][MAXN];

int main(){
    //freopen("d:\\my.txt", "r", stdin);
    int n, m, i, j, u, v, w;

    scanf("%d %d", &n, &m);
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            G[i][j] = INF;

    for(i=0; i<m; i++){
        scanf("%d %d %d", &u, &v, &w);
        G[u][v] = G[v][u] = w;  //无向图
    }

    for(i=1; i<=n; i++){
        printf("与%d相关联的顶点有:\n", i);
        for(j=1; j<=n; j++)if(G[i][j] != INF){
            printf("%d ", j);
        }
        putchar('\n');
    }


    return 0;
}

边表：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXM 100    //最大边数
#define MAXN 10   //最大顶点数
struct node{
    int v, w;
    int next;
}g[MAXM];

int head[MAXN], t;

void Init(){
    t = 0;
    memset(head, -1, sizeof(head));
}

void add(int u, int v, int w){
    g[t].v = v;
    g[t].w = w;
    g[t].next = head[u];
    head[u] = t;
    t++;
}



int main(){
    //freopen("d:\\my.txt", "r", stdin);
    int n, m, i, j, u, v, w;
    scanf("%d %d", &n, &m);
    Init();


    for(i=0; i<m; i++){
        scanf("%d %d %d", &u, &v, &w);
        add(u, v, w);
        add(v, u, w);   //因为该图为无向图
    }

    for(i=1; i<=n; i++){
        printf("与%d相关联的顶点有:\n", i);
        for(j=head[i]; j != -1; j=g[j].next){
            printf("%d ", g[j].v);
        }
        putchar('\n');
    }

    return 0;
}

邻接表（动态）：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 100

struct node{
    int v, w;
    struct node *next;
}*head[MAXN];

void Init(){
    memset(head, 0, sizeof(head));
}

void add(int u, int v, int w){
    struct node *p = (struct node *)malloc(sizeof(struct node));
    p->v = v;
    p->w = w;
    p->next = head[u];
    head[u] = p;
}

int main(){
    //freopen("d:\\my.txt", "r", stdin);
    int n, m, i, u, v, w;
    scanf("%d %d", &n, &m);
    Init();
    for(i=0; i<m; i++){
        scanf("%d %d %d", &u, &v, &w);
        add(u, v, w);
        add(v, u, w);   //双向
    }

    for(i=1; i<=n; i++){
        printf("与%d相关联的顶点有:\n", i);
        struct node *p;
        for(p=head[i]; p != NULL; p = p->next){
            printf("%d ", p->v);
        }
        putchar('\n');
    }

    return 0;
}

邻接表（静态）：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 100
#define MAXM 10000

struct node{
    int v, w;
    struct node *next;
}*head[MAXN];

struct node mem[MAXM];
int t;

void Init(){
    t = 0;
    memset(head, 0, sizeof(head));
}

void add(int u, int v, int w){
    struct node *p = &mem[t++];
    p->v = v;
    p->w = w;
    p->next = head[u];
    head[u] = p;
}

int main(){
    freopen("d:\\my.txt", "r", stdin);
    int n, m, i, u, v, w;
    scanf("%d %d", &n, &m);
    Init();
    for(i=0; i<m; i++){
        scanf("%d %d %d", &u, &v, &w);
        add(u, v, w);
        add(v, u, w);   //双向
    }
    for(i=1; i<=n; i++){
        printf("与%d相关联的顶点有:\n", i);
        struct node *p;
        for(p=head[i]; p != NULL; p = p->next){
            printf("%d ", p->v);
        }
        putchar('\n');
    }
    return 0;
}

运行结果：