由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在存储区中的物理位置来表示元素之间的关系，即图没有顺序映像的存储结构。
数组表示法
用数组分别表示存储数据元素（顶点）的信息和数据元素之间的关系（边或者弧）的信息
#define INFINITY INT_MAX //最大值
#define MAX_VERTEX_NUM 20 //最大顶点个数
typedef enum {DG,DN,UDG,UDM} GraphKind; //{有向图，有向网，无向图，无向网}
typedef struct ArcCell
{
VRType adj; //VRType是顶点关系类型，对无权图，用0/1
//表示相邻与否，对带权图则为权值类型
InfoType *info;//该弧相关信息的指针
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
sypedef struct
{
VertexTypd vex[MAX_VERTEX_NUM]; //顶点向量
AdjMatrix arcs; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和弧数
GraphKind kind; //图的种类标志
}MGraph;
若考虑无向图的邻接矩阵的对称性，则可采用压缩存储的方式只存入矩阵的下三角（或上三角）元素。
用邻接矩阵构造图：
Status CreateGraph( MGraph &G ) {
// 采用数组(邻接矩阵)表示法，构造图G。
scanf(&G.kind); // 自定义输入函数，读入一个随机值
switch (G.kind) {
case DG: return CreateDG(G); // 构造有向图G
case DN: return CreateDN(G); // 构造有向网G
case UDG: return CreateUDG(G); // 构造无向图G
case UDN: return CreateUDN(G); // 构造无向网G，算法7.2
default : return ERROR;
}
} // CreateGraph
Status CreateUDN(MGraph &G) {
// 采用数组（邻接矩阵）表示法，构造无向网G。
int i,j,k,w;
VertexType v1,v2;
printf("G.vexnum :" ); scanf("%d",&G.vexnum);
printf("G.arcnum :"); scanf("%d",&G.arcnum);
getchar(); /*** 加上此句getchar()!!! ***/
// scanf("%d,%d,%d",&G.vexnum, &G.arcnum, &IncInfo);
for (i=0; i的权值
// if (IncInfo) scanf(G.arcs[i][j].info); // 输入弧含有相关信息
G.arcs[j][i].adj = G.arcs[i][j].adj; // 置的对称弧
}
return OK;
} // CreateUDN
邻接矩阵使用方便，操作简单，但是容易浪费存储空间，如果不是稠密图，动态存储将是更好的选择。
C语言实现：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//邻接矩阵
int G[100][100];
int add1 (int i,int j,int w)
{
G[i][j] = w;
return 0;
}
int main()
{
int i,n;
//建图
scanf ("%d",&n);
for (i = 0;i < n;i++)
{
int a,b,w;
//输入起点、终点、权重
scanf ("%d%d%d",&a,&b,&w);
add1 (a,b,w);
//无向图加上
add1 (b,a,w);
}
return 0;
}
邻接表表示法
邻接表是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧。）每个结点由3个域组成，其中邻接点域指示与顶点vi邻接的点在图中的位置，链域指示下一条边或弧的结点；数据域存储和边或弧相关的信息，如权值等。
每个链表上附设一个表头结点。在表头结点中，除了设有链域只想链表中第一个结点之外，还设有存储顶点vi的名或其他有关信息的数据域。
#define MAX_VERTEX_NUM 20 //最大顶点个数
typedef struct ArcNode
{
int adjvex; //该弧所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条弧的指针
InfoType *info;//该弧相关信息的指针
}ArcNode;
typedef struct VNode
{
VertexType data; //顶点信息
ArcNode *firstarc; //指向第一条依附该顶点的弧的指针
}VNode，AdjList[MAX_VERTEX_NUM];
sypedef struct
{
AdjList vertices;
int vexnum,arcnum; //图的当前顶点数和弧数
int kind; //图的种类标志
}ALGraph;
若无向图中有n个顶点，e条边，则它的邻接表需n个头结点和2e个表结点。显然，在边稀疏(e << (n(n-1))/2)的情况下，用邻接表表示图比邻接矩阵节省存储空间。
邻接表可以根据邻接的是入点还是出点分为邻接表和逆邻接表，两者各有各的优势，如果经常访问下一个结点，统计出度，邻接表将有优势；如果经常访问上一个结点，统计入度，逆邻接表将有优势。
C语言实现：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//邻接表
struct dot
{
int d;
int w;
struct dot *next;
};
struct hed
{
int v;
struct dot *next;
}head[100];
int add2(int i,int j,int w)
{
struct dot * p;
struct dot * t = new dot;
t->d = j;
t->w = w;
t->next = NULL;
if (head[i].next == NULL)
{
head[i].next = t;
return 0;
}
p = head[i].next;
while (p->next != NULL)
p = p->next;
p->next = t;
return 0;
}
int main()
{
int i,n;
memset (head,0,sizeof (head));
//建图
scanf ("%d",&n);
for (i = 0;i < n;i++)
{
int a,b,w;
//输入起点、终点、权重
scanf ("%d%d%d",&a,&b,&w);
add2 (a,b,w);
//无向图加上
add2 (b,a,w);
}
return 0;
}
建立邻接表的时间复杂度为O（n+e）。
十字链表
十字链表是有向图的另一种存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。
存储表示：
#define MAX_VERTEX_NUM 20 //最大顶点个数
typedef struct ArcBox
{
int tailvex,headvex; //该弧的尾和头顶点的位置
struct ArcBox *hlink,*tlink; //分别为弧头相同和弧尾相同的弧的链域
InfoType *info; //该弧相关信息的指针
}ArcNode;
typedef struct VexNode
{
VertexType data; //顶点信息
ArcNode *firstin，*firstout; //指向第一条依附该顶点的弧的指针
}VexNode;
sypedef struct
{
VexNode xlist[MAX_VERTEX_NUM]; //表头向量
int vexnum,arcnum; //图的当前顶点数和弧数
}OLGraph;
用十字链表建图：
Status CreateDG(OLGraph &G) {
// 采用十字链表存储表示，构造有向图G（G.kind=DG）。
//scanf(&G.vexnum, &G.arcnum, &IncInfo);
int i,j,k;
char v1,v2;
int IncInfo=0;
struct ArcBox *p;
scanfInit(); // 输入初始化
scanf(&G.vexnum, &G.arcnum, &IncInfo); // 自定义输入函数
for (i=0; itailvex=i;
p->headvex=j;
p->hlink=G.xlist[j].firstin;
p->tlink=G.xlist[j].firstout;
G.xlist[j].firstin = G.xlist[i].firstout = p;
// 完成在入弧和出弧链头的插入
//if (IncInfo) Input(*p->info); // 输入弧含有相关信息，此略!!!
}
return OK;
} // CreateDG
C语言实现：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//十字链表
struct dot
{
int d;
int w;
struct dot *next;
};
struct hed
{
int v;
struct dot *to;
struct dot *next;
}head[100];
int add3(int i,int j,int w)
{
struct dot * p;
struct dot * t = new dot;
t->d = j;
t->w = w;
t->next = NULL;
//正邻接表构建
if (head[i].next == NULL)
{
head[i].next = t;
}else
{
p = head[i].next;
while (p->next != NULL)
p = p->next;
p->next = t;
}
//逆邻接表打十字
if (head[i].to == NULL)
{
head[i].to = t;
return 0;
}else
{
p = head[i].to;
while (p->next != NULL)
p = p->next;
p->next = t;
}
return 0;
}
int main()
{
int i,n;
memset (head,0,sizeof (head));
//建图
scanf ("%d",&n);
for (i = 0;i < n;i++)
{
int a,b,w;
//输入起点、终点、权重
scanf ("%d%d%d",&a,&b,&w);
add3 (a,b,w);
}
return 0;
}
十字链表中和了邻接表和逆邻接表的优势。
邻接多重表
邻接多重表示无向图的另一种链式存储结构。虽然邻接表是无向图的一种很有效的存储结构，在邻接表中容易求得顶点和边的各种信息。但是在邻接表中每一条边（vi,vj）有两个结点，分别周四第i个和第j个链表中，这些给某些图的操作带来了不便。如对已被搜索过的边作标记或删除一条边等。如果一个结点能表示一条边的两个点的数据结构比较适宜。
因此，邻接多重表诞生了。他的核心就是用一个结点代表了一条边。
#define MAX_VERTEX_NUM 20 //最大顶点个数
typedef emnu{unvisited,visited} VisitIf
;
typedef struct EBox
{
VisitIf mark; //访问标记
int ivex,jvex; //该边依附的两个顶点的位置
struct EBox *ilink,*jlink; //分别为指向依附这两个顶点的下一条边
InfoType *info; //该弧相关信息的指针
}ArcNode;
typedef struct VexBox
{
VertexType data; //顶点信息
EBox *firstedge; //指向第一条依附该顶点的弧的指针
}VexBox;
sypedef struct
{
VexBox adjmulist[MAX_VERTEX_NUM];
int vexnum,arcnum; //无向图的当前顶点数和弧数
}AMLGraph;
C语言实现：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//邻接多重表（无向图）
struct dot
{
int i,j;
int w;
struct dot *inext;
struct dot *jnext;
};
struct hed
{
int v;
struct dot *next;
}head[100];
int add4(int i,int j,int w)
{
struct dot *t = new dot;
struct dot *p = NULL,*tp = NULL;
t->i = i;
t->j = j;
t->w = w;
t->inext = NULL;
t->jnext = NULL;
if (head[i].next == NULL)
{
head[i].next = t;
}else
{
p = head[i].next;
while (p != NULL)
{
tp = p;
if (p->i == i)
p = p->inext;
else
p = p->jnext;
}
if (tp->i == i)
tp->inext = t;
else
tp->jnext = t;
}
if (head[j].next == NULL)
{
head[j].next = t;
}else
{
p = head[j].next;
while (p != NULL)
{
tp = p;
if (p->i == j)
p = p->inext;
else
p = p->jnext;
}
if (tp->i == j)
tp->inext = t;
else
tp->jnext = t;
}
return 0;
}
int main()
{
int i,n;
memset (head,0,sizeof (head));
//建图
scanf ("%d",&n);
for (i = 0;i < n;i++)
{
int a,b,w;
//输入起点、终点、权重
scanf ("%d%d%d",&a,&b,&w);
add4 (a,b,w);
}
return 0;
}
