1. /* 顶点类型应由用户定义 */
    2. typedef char VertexType;             
    4. /* 边上的权值类型应由用户定义 */
    5. typedef int EdgeType;                
    7. /* 最大顶点数，应由用户定义 */
    8. #define MAXVEX 100                   
    10. /* 用65535来代表∞ */infinity[ɪnˈfɪnəti]无穷大(的数)
    11. #define INFINITY 65535               
    13. typedef struct
    14. {
    15.     /* 顶点表 */
    16.     VertexType vexs[MAXVEX];         
    18.     /* 邻接矩阵，可看作边表 */
    19.     EdgeType arc[MAXVEX][MAXVEX];    
    21.     /* 图中当前的顶点数和边数 */
    22.     int numVertexes, numEdges;       
    23. } MGraph;
    1. /* 建立无向网图的邻接矩阵表示 */
    2. void CreateMGraph(MGraph *G)
    3. {
    4.     int i, j, k, w;
    6.     printf("输入顶点数和边数:\n");
    7.     /* 输入顶点数和边数 */
    8.     scanf("%d,%d", &(G->numVertexes), &(G->numEdges));    
    10.     /* 读入顶点信息，建立顶点表 */
    11.     for (i = 0; i < G->numVertexes; i++)              
    12.         scanf(&G->vexs[i]);
    14.     for (i = 0; i < G->numVertexes; i++)
    15.         for (j = 0; j <G->numVertexes; j++)
    16.             /* 邻接矩阵初始化 */
    17.             G->arc[i][j] = INFINITY;                  
    19.     /* 读入numEdges条边，建立邻接矩阵 */
    20.     for (k = 0; k < G->numEdges; k++)                 
    21.     {
    22.         printf("输入边(vi,vj)上的下标i，下标j和权w:\n");
    23.         /* 输入边(vi,vj)上的权w */
    24.         scanf("%d,%d,%d", &i, &j, &w);                
    26.         G->arc[i][j] = w;
    28.         /* 因为是无向图，矩阵对称 */
    29.         G->arc[j][i] = G->arc[i][j];                  
    30.     }
    31. }
    32. 从代码中也可以得到，n个顶点和e条边的无向网图的创建，时间复杂度为O(n+n2+e)，
    33. 其中对邻接矩阵G.arc的初始化耗费了O(n2)的时间。
    1. /* 顶点类型应由用户定义 */
    2. typedef char VertexType;          
    4. /* 边上的权值类型应由用户定义 */
    5. typedef int EdgeType;             
    7. /* 边表结点 */
    8. typedef struct EdgeNode           
    9. {
    10.     /* 邻接点域，存储该顶点对应的下标 */
    11.     EdgeType adjvex;                   
    13.     /* 用于存储权值，对于非网图可以不需要 */
    14.     EdgeType weight;              
    16.     /* 链域，指向下一个邻接点　 */
    17.     struct EdgeNode *next;        
    18. } EdgeNode;
    20. /* 顶点表结点 */
    21. typedef struct VertexNode         
    22. {
    23.     /* 顶点域，存储顶点信息 */
    24.     VertexType data;              
    26.     /* 边表头指针 */
    27.     EdgeNode *firstedge;          
    29. } VertexNode, AdjList[MAXVEX];
    30. //结构
    31. typedef struct
    32. {
    33.     AdjList adjList;//<=>VertexNode[] adjList;顶点表结点(结构体)类型的数组
    35.     /* 图中当前顶点数和边数 */
    36.     int numVertexes, numEdges;    
    38. } GraphAdjList;
    1. /* 建立图的邻接表结构 */
    2. void  CreateALGraph(GraphAdjList *G)
    3. {
    4.     int i, j, k;
    6.     EdgeNode *e;
    8.     printf("输入顶点数和边数:\n");
    9.     /* 输入顶点数和边数 */
    10.     scanf("%d,%d", &G->numVertexes, &G->numEdges);    
    12.     /* 读入顶点信息，建立顶点表 */
    13.     for (i = 0; i < G->numVertexes; i++)              
    14.     {
    15.         /* 输入顶点信息 */
    16.         scanf(&(G->adjList[i].data));                   
    18.         /* 将边表置为空表 */
    19.         G->adjList[i].firstedge = NULL;               
    20.     }
    22.     /* 建立边表 */
    23.     for (k = 0; k < G->numEdges; k++)                 
    24.     {
    25.         printf("输入边(vi,vj)上的顶点序号:\n");
    26.         /* 输入边(vi,vj)上的顶点序号 */
    27.         scanf("%d,%d", &i, &j);                       
    29.         /* 向内存申请空间， */
    30.         /* 生成边表结点 */
    31.         e = (EdgeNode *)malloc(sizeof(EdgeNode));     
    33.         /* 邻接序号为j */
    34.         e->adjvex = j;                                
    35.         /* 将e指针指向当前顶点指向的结点 *///注意：G->adjList[i].firstedge在上面被置空NULL
    36.         e->next = G->adjList[i].firstedge;            
    37.         /* 将当前顶点的指针指向e */
    38.         G->adjList[i].firstedge = e;                  
    40.         /* 向内存申请空间， */
    41.         /* 生成边表结点 */
    42.         e = (EdgeNode *)malloc(sizeof(EdgeNode));     
    44.         /* 邻接序号为i */
    45.         e->adjvex = i;                                
    46.         /* 将e指针指向当前顶点指向的结点 */
    47.         e->next = G->adjList[j].firstedge;            
    48.         /* 将当前顶点的指针指向e */
    49.         G->adjList[j].firstedge = e;                  
    50.     }
    51. }
    52. 本算法的时间复杂度，对于n个顶点e条边来说，很容易得出是O(n+e)。