文章目录

一、邻接表二、代码实现    

一、邻接表

  邻接矩阵看上去是个不错的选择，首先是容易理解，第二是索引和编排都很舒服~但是我们也发现，对于边数相对顶点较少的图，这种结构无疑是存在对存储空间的极大浪费。因此我们可以考虑另外一种存储结构方式，例如把数组与链表结合一起来存储，这种方式在图结构也适用，我们称为邻接表(AdjacencyList)。

邻接表的处理方法是这样：

图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。图中每个顶点Vi的所有邻接点构成一个线性表，由于邻接点的个数不确定，所以我们选择用单链表来存储。

逆邻接表：   有向图由于有方向，邻接表我们是以顶点为弧尾来存储边表的，这样很容易就可以得到每个顶点的出度。但也有时为了便于确定顶点的入度或以顶点为弧头的弧，我们可以建立一个有向图的逆邻接表，即对每个顶点Vi都建立一个链接为Vi为弧头的表。

 

二、代码实现

adjListGraph.h

#ifndef __GRAPH__H #define __GRAPH__H /**/ #define MAX_VERTEX 100 typedef char vertexType; typedef int weightType; /*邻接表*/ /*边节点结构*/ typedef struct _edgeNode { vertexType vertex; /*顶点*/ weightType weight; /*权重*/ struct _edgeNode *next; } edgeNode_s, *edgeNode_p; /*数组0结构*/ typedef struct _vertexGraph { vertexType vertex; edgeNode_p fistNode; }vertexGraph[MAX_VERTEX], vertexGraph_s; typedef struct _adjListGraph { int numEdges, numVertex; /*顶点数与边数*/ vertexGraph graph; } adjListGraph_s, *adjListGraph_p; #endif

adjListGraph.c

#include <stdio.h> #include <stdlib.h> #include "graph.h" #include <string.h> #ifdef ADJLIST /*根据顶点返回在数组中的位置*/ int locateGraph(adjListGraph_p adjGraph, vertexType c) { int i; for (i = 0; i < adjGraph->numVertex; i++) { if (adjGraph->graph[i].vertex == c) return i; } return -1; } int printfGraph(adjListGraph_p adjGraph) { int i; edgeNode_p p1,p2; for(i = 0; i < adjGraph->numVertex; i ++) { printf("%c->", adjGraph->graph[i].vertex); p1 = adjGraph->graph[i].fistNode; while(p1) { p2 = p1->next; printf("%c(%d),", p1->vertex, p1->weight); p1 = p2; } printf("\n"); } return 0; } int crateAdjListGraph(adjListGraph_p adjGraph) { int i, j, k, w; vertexType x,y; edgeNode_p edgeNode; if (!adjGraph) return -1; printf("input numEages:"); scanf("%d", &(adjGraph->numEdges)); printf("input numVertex:"); scanf("%d", &(adjGraph->numVertex)); if (adjGraph->numVertex > MAX_VERTEX) return -1; for (i = 0; i < adjGraph->numVertex; i++) { printf("input vertex:"); adjGraph->graph[i].vertex = getchar(); while(adjGraph->graph[i].vertex == '\n') adjGraph->graph[i].vertex = getchar(); } for (k = 0; k < adjGraph->numEdges; k ++) { printf("input vertex and weight:\n"); x = getchar(); while(x == '\n') x = getchar(); y = getchar(); while(y == '\n') y = getchar(); scanf("%d", &w); #if 1 /*邻接表*/ i = locateGraph(adjGraph, x); //j = locateGraph(adjGraph, y); if (i == -1) { printf("input error\n"); k --; continue; } edgeNode = (edgeNode_p)malloc(sizeof(*edgeNode)); if (!edgeNode) return -2; edgeNode->weight = w; edgeNode->vertex = y; edgeNode->next = adjGraph->graph[i].fistNode; adjGraph->graph[i].fistNode = edgeNode; #elif /*逆邻接表*/ j = locateGraph(adjGraph, y); //j = locateGraph(adjGraph, y); if (j == -1) { printf("input error\n"); k --; continue; } edgeNode = (edgeNode_p)malloc(sizeof(*edgeNode)); if (!edgeNode) return -2; edgeNode->weight = w; edgeNode->vertex = x; edgeNode->next = adjGraph->graph[j].fistNode; adjGraph->graph[j].fistNode = edgeNode; #endif } return 0; } #endif

              关注公众号"小败日记"，搬砖过程遇到的问题，大家一起探讨，资源共享