逆鄰接表：任一表頭結點下的邊結點的數量是圖中該結點入度的弧的數量，與鄰接表相反。圖的鄰接表，反映的是節點的出度鄰接情況，圖的逆鄰接表反映的是節點的入度鄰接情況。
C代碼：
//圖的鄰接表#include<stdio.h>#include<stdlib.h>#define MAX_VEX_NUM 20typedef char VertexType; //頂點類型設為字元型typedef enum {Directed_graph, Undirected_graph} GraphType;typedef enum {Adjacency_list,Inverse_adjacency_list} ListType;typedef struct ArcNode{ //表節點 VertexType adjvex; //鄰接點 struct ArcNode *nextarc; //指向下一條邊的指針} ArcNode;typedef struct VexNode{ //頭節點 VertexType vexdata; //頂點名稱 ArcNode *firstarc; //指向第一個依附該頂點的邊的指針} VexNode, AdjList[MAX_VEX_NUM];typedef struct{ AdjList vexs; //頂點集合,即vexs[MAX_VEX_NUM]，AdjLIst為結構數組 int vexnum; //圖的頂點數 int edgenum; //圖的邊數 GraphType graph_type; ListType list_type;} ALGraph;//函式聲明void Create_ALGraph(ALGraph *ALG);int Get_Index_Of_Vex(ALGraph *ALG,char vex);void Print_ALGraph(ALGraph ALG);void Insert_adjvex(ALGraph * ALG,int ADvex,char vex);//創建圖並初始化圖void Create_ALGraph(ALGraph *ALG){ int i; int v1,v2; char c1,c2; int graph_type; int list_type; printf("Please input graph graph_type Directed_graph(0) or Undirected_graph(1) :"); scanf("%d", &graph_type); if(graph_type==0){ ALG->graph_type=Directed_graph; printf("Please input list list_type Adjacency_list(0) or Inverse_adjacency_list(1) :"); scanf("%d",&list_type); if(list_type==0) ALG->list_type=Adjacency_list; else if(list_type==1) ALG->list_type=Inverse_adjacency_list; else{ printf("Please input correct list_type!\n"); return ; } } else if(graph_type==1) ALG->graph_type=Undirected_graph; else{ printf("Please input correct graph graph_type!\n"); return ; } printf("Please input vexmun : "); scanf("%d",&ALG->vexnum); printf("Please input edgenum : "); scanf("%d",&ALG->edgenum); getchar(); //頂點為字元型數據,以需要用getcgar()來接收換行符,也可用fflush(stdin)清空輸入快取區 for(i=0;i<ALG->vexnum;i++){ printf("Please input %dth vex(char):",(i+1)); scanf("%c",&(ALG->vexs[i].vexdata)); getchar(); ALG->vexs[i].firstarc=NULL; } if(ALG->graph_type==1){ for(i=0;i<ALG->edgenum;i++){ printf("Please input %dth edge v1(char) v2(char) : ",i+1); scanf("%c %c",&c1,&c2); getchar(); v1=Get_Index_Of_Vex(ALG,c1); //v1的位置 v2=Get_Index_Of_Vex(ALG,c2); //v2的位置 Insert_adjvex(ALG,v1,c2); Insert_adjvex(ALG,v2,c1); } } else{ if(ALG->list_type==0){ for(i=0;i<ALG->edgenum;i++){ printf("Please input %dth edge v1(char) v2(char) : ",i+1); scanf("%c %c",&c1,&c2); getchar(); v1=Get_Index_Of_Vex(ALG,c1); //v1的位置 v2=Get_Index_Of_Vex(ALG,c2); //v2的位置 Insert_adjvex(ALG,v1,c2); } } else{ for(i=0;i<ALG->edgenum;i++){ printf("Please input %dth edge v1(char) v2(char) : ",i+1); scanf("%c %c",&c1,&c2); getchar(); v1=Get_Index_Of_Vex(ALG,c1); //v1的位置 v2=Get_Index_Of_Vex(ALG,c2); //v2的位置 Insert_adjvex(ALG,v2,c1); } } }}//根據名稱得到指定頂點在頂點集合中的下標int Get_Index_Of_Vex(ALGraph *ALG,char vex){ int i; for(i=0;i<ALG->vexnum;i++) if(ALG->vexs[i].vexdata==vex) return i; return 0;}//列印鄰接表void Print_ALGraph(ALGraph ALG){ int i,j; ArcNode *first; if(ALG.graph_type==Directed_graph){ printf("Graph graph_type: Direct graph\n"); } else{ printf("Graph graph_type: Undirect graph\n"); } printf("Graph vertex number: %d\n",ALG.vexnum); printf("Graph edge number: %d\n",ALG.edgenum); printf("Vertex set:"); for(i=0;i<ALG.vexnum;i++) printf("%3c",ALG.vexs[i].vexdata); printf("\n"); if(ALG.graph_type==Undirected_graph||ALG.list_type==Adjacency_list) printf("Adjacency List:\n"); else if(ALG.list_type==Inverse_adjacency_list) printf("Inverse Adjacency List:\n"); for(i=0;i<ALG.vexnum;i++){ printf("V%d | %c",i,ALG.vexs[i].vexdata); if(ALG.vexs[i].firstarc!=NULL){ first=ALG.vexs[i].firstarc; while(first){ printf(" --> %c ",first->adjvex); first=first->nextarc; } } printf("\n"); }}//插入鄰接點void Insert_adjvex(ALGraph *ALG,int ADvex,char vex){ ArcNode *arc1,*arc2; arc1=(ArcNode *)malloc(sizeof(ArcNode)); arc1->adjvex=vex; arc1->nextarc=NULL; if(ALG->vexs[ADvex].firstarc==NULL){ ALG->vexs[ADvex].firstarc=arc1; } else{ arc2=ALG->vexs[ADvex].firstarc; while(arc2->nextarc){ arc2=arc2->nextarc; } arc2->nextarc=arc1; }}int main(){ ALGraph ALG; Create_ALGraph(&ALG); Print_ALGraph(ALG); return 0;}
