一、概念

　　图是由顶点的非空有限集合V（由N>0个顶点组成）与边的集合E（顶点之间的关系）构成。边没有方向的图成为无向图，反之为有向图

 　无向图:　有向图:

二、图的表示

　　常见的图的存储方法有两种：邻接矩阵存储法与邻接表存储法

　　1、邻接矩阵

　　　　邻 接矩阵存储法也称为数组存储方法，核心就是利用两个数组来存储一个图，一个一维数组用来存放图中的数据（顶点）:vertex[0,1,2...,n- 1]另外一个二维数组用来存储图中顶点之间的相互关系（边），称为邻接矩阵：A[i][j] = 1(当顶点i与顶点j有边) | 0（顶点i与顶点j无边）

举例：一中的有向图就可以表示为

数组：[0 , 1 , 2, 3]

邻接矩阵:

0 1 0 1

0 0 1 0

0 0 0 1

0 0 0 0

　　

　　邻接矩阵不适合存储边很少的图，可以用邻接表存储这类图

　　2、邻接表

　　邻接表存储法是一种顺序分配与链式分配相结合的存储的方法，由链表和顺序数组组成，数组用来存储顶点，链表用来存储边,对图中的每个顶点分别建立一个顶点，如果一个图有n个顶点那么就有n个链表，每个链表前边设置一个头结点，成为顶点结点，结构如图：

其中vertex存放顶点的数据信息，next指向顶点vertex上的第一条边。通常用一个数组统一管理顶点结点，并用该数组的下标表示顶点在图中的位置。

 

链表的每一个结点表示一条边，被称为边结点。

（边结点结构）adjvex指的是该边结点所代表的边的另外一个顶点（即该链表顶结点与该顶点构成了该条边），weight代表边权重（边长），如果图没有该项则省略，next指向下一个边结点（即该链表的顶点结点的下一条边）。

举例:一中的有向图可以表示为

数组:[0 ， 1， 2， 3]

邻接表:

除了以上两种存储图的方式外还有十字链表存储法，多重邻接表存储法等。

 

三、C描述

　邻接表用C语言可以描述为：

#define MAX_VERTEX_NUM 20// 定义边（链表中结点的类型）typedef struct ArcNode{int adjvex;struct ArcNode *next;infoType *weight;}ArcNode;// 定义顶点typedef struct VNode{VertexType data;ArcNode *firstarc; } VNode G[MAX_VERTEX_NUM];

　　如何用C创建一个图呢：

CreateGraph(int n , VNode G[]){  int i , e;  printf("Input the info of the vertex\n");  for(i=0;i
     
      next = NULL; p->adjvex = e; /*i结点的第一条边*/ if(G[i].fristarc == NULL) G[i].firstarc = p; /*下一条边*/ else q->next = p; q = p; scanf("%d" , &e); } } }