邻接表

#include<bits/stdc++.h>
#define maxvertexnum 100    /* 最大顶点数设为100 */ 
typedef int vertex;         /* 用顶点下标表示顶点,为整型 */ 
typedef int weighttype;        /* 边的权值设为整型 */ 
typedef char datatype;        /* 顶点存储的数据类型设为字符型 */ /* 边的定义 */
typedef struct enode *ptrtoenode;
struct enode{     
    vertex v1, v2;      /* 有向边<v1, v2> */     
    weighttype weight;  /* 权重 */ 
};
typedef ptrtoenode edge; /* 邻接点的定义 */ 
typedef struct adjvnode *ptrtoadjvnode;
struct adjvnode{     
    vertex adjv;        /* 邻接点下标 */     
    weighttype weight;  /* 边权重 */     
    ptrtoadjvnode next;    /*指向下一个邻接点的指针*/ 
};
 /* 顶点表头结点的定义 */ 
typedef struct vnode{     
     ptrtoadjvnode firstedge;/* 边表头指针 */     
     datatype data;            /* 存顶点的数据 */     /* 注意：很多情况下，顶点无数据，此时data可以不用出现 */ 
} adjlist[maxvertexnum];
/* adjlist是邻接表类型 */ 
/* 图结点的定义 */ 
typedef struct gnode *ptrtognode; 
struct gnode{       
    int nv;     /* 顶点数 */     
    int ne;     /* 边数   */     
    adjlist g;  /* 邻接表 */ 
};
typedef ptrtognode lgraph; /* 以邻接表方式存储的图类型 */

lgraph creategraph( int vertexnum ) { 
    /* 初始化一个有vertexnum个顶点但没有边的图 */     
    vertex v;     
    lgraph graph;          
    graph = (lgraph)malloc( sizeof(struct gnode) ); /* 建立图 */     
    graph->nv = vertexnum;     
    graph->ne = 0;     /* 初始化邻接表头指针 */     
    /* 注意：这里默认顶点编号从0开始，到(graph->nv - 1) */        
    for (v=0; v<graph->nv; v++)         
        graph->g[v].firstedge = null;                  
    return graph;  
}
void insertedge( lgraph graph, edge e ) {     
    ptrtoadjvnode newnode;/* 插入边 <v1, v2> */     
    /* 为v2建立新的邻接点 */     
    newnode = (ptrtoadjvnode)malloc(sizeof(struct adjvnode));     
    newnode->adjv = e->v2;     
    newnode->weight = e->weight;     
    /* 将v2插入v1的表头 */     
    newnode->next = graph->g[e->v1].firstedge;     
    graph->g[e->v1].firstedge = newnode;  
    /* 若是无向图，还要插入边 <v2, v1> */     
    /* 为v1建立新的邻接点 */     
    newnode = (ptrtoadjvnode)malloc(sizeof(struct adjvnode));     
    newnode->adjv = e->v1;     
    newnode->weight = e->weight; 
    /* 将v1插入v2的表头 */     
    newnode->next = graph->g[e->v2].firstedge;     
    graph->g[e->v2].firstedge = newnode; 
}

lgraph buildgraph() {     
    lgraph graph;     
    edge e;     
    vertex v;     
    int nv, i;          
    scanf("%d", &nv);   
    /* 读入顶点个数 */     
    graph = creategraph(nv); 
    /* 初始化有nv个顶点但没有边的图 */           
    scanf("%d", &(graph->ne));   
    /* 读入边数 */     
    if ( graph->ne != 0 ) { 
        /* 如果有边 */          
        e = (edge)malloc( sizeof(struct enode) ); 
        /* 建立边结点 */         
        /* 读入边，格式为"起点 终点 权重"，插入邻接矩阵 */         
        for (i=0; i<graph->ne; i++) {             
            scanf("%d %d %d", &e->v1, &e->v2, &e->weight);             
            /* 注意：如果权重不是整型，weight的读入格式要改 */             
            insertedge( graph, e );         
        }     
    }      
    /* 如果顶点有数据的话，读入数据 */     
    for (v=0; v<graph->nv; v++)          
        scanf(" %c", &(graph->g[v].data));     
    return graph; 
}