邻接表：邻接表是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧）。每个结点有三个域组成，其中邻接点域指示与顶点vi邻接的点在途中的位置，链域指示下一条边或者弧的结点；数据域存储和边或者弧相关的信息，如权值等。每个链表上附设一个表头结点。在表头结点中，除了设置链域指向链表第一个结点之外，还设置有存储顶点vi的名。如下所示：

实现：

/**************************************
图的存储之邻接表
by Rowandjj
2014/6/23
**************************************/

#include<iostream>
using namespace std;

#define MAX_VERTEX_NUM 20//最大顶点数

typedef enum{DG,DN,AG,AN}GraphKind;//有向图、有向网、无向图、无向网
typedef struct _ARCNODE_//表节点(弧)
{
    int adjvex;//邻接点序号
    struct _ARCNODE_ *nextarc;//指向下一条弧
    int info;//信息(权值)  
}ArcNode;

typedef struct _VNODE_//头结点
{
    char data;//顶点名
    ArcNode *firstarc;//指向第一条弧
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct _ALGRAPH_//邻接表
{
    AdjList vertices;//邻接表
    int vexnum;//顶点数
    int arcnum;//弧数
    GraphKind kind;//图的种类
}ALGraph;

void (*VisitFunc)(char);  //全局函数指针 

bool visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */

void Visit(char p)
{
    cout<<p<<" ";
}
//-----------------操作-------------------------------------
int LocateVex(ALGraph G,char u);//若G中存在顶点u,则返回该顶点在图中位置;否则返回-1
bool CreateGraph(ALGraph* G);//采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图)
void DestroyGraph(ALGraph* G);//销毁图G
char GetVex(ALGraph G,int v);//通过序号v得到顶点名
bool PutVex(ALGraph* G,char v,char value);//对v赋新值value
int FirstAdjVex(ALGraph G,char v);//返回顶点v的第一个邻接顶点的序号
int NextAdjVex(ALGraph G,char v,char w);//返回v的(相对于w的)下一个邻接顶点的序号,若w是v的最后一个邻接点,则返回-1
void InsertVex(ALGraph* G,char v);//在图G中增添新顶点v(不增添与顶点相关的弧,留待InsertArc()去做)             
bool DeleteVex(ALGraph* G,char v);//删除G中顶点v及其相关的弧
bool InsertArc(ALGraph* G,char v,char w);//在G中增添弧<v,w>,若G是无向的,则还增添对称弧<w,v>
bool DeleteArc(ALGraph* G,char v,char w);//在G中删除弧<v,w>,若G是无向的,则还删除对称弧<w,v>
void DFSTravel(ALGraph* G,void (*Visit)(char));//深度优先
void DFS(ALGraph G,int v);
void BFSTravel(ALGraph G,void (*Visit)(char));//广度优先
void Display(ALGraph G);//打印图

//----------------辅助队列------------------------------------------
#define MAX_QUEUE_SIZE 20
typedef struct _QUEUENODE_
{
    int data;
    struct _QUEUENODE_ *next;
}QueueNode;
typedef struct _QUEUE_
{
    QueueNode *pHead;
    QueueNode *pTail;
    int size;
}Queue;

bool InitQueue(Queue *Q);
bool DestroyQueue(Queue *Q);
bool DeQueue(Queue *Q,int* e);
bool EnQueue(Queue *Q, int e);
bool QueueEmpty(Queue Q);
//------------------------------------------------------------------
bool InitQueue(Queue *Q)
{
    Q->pHead = Q->pTail = (QueueNode *)malloc(sizeof(QueueNode));
    if(!Q->pHead)
    {
        return false;
    }
    Q->pHead->next = NULL;
    Q->size = 0;
    return true;
}

bool EnQueue(Queue *Q, int e)
{
    QueueNode *node = (QueueNode*)malloc(sizeof(QueueNode));
    node->data = http://www.mamicode.com/e;>
测试：
考虑以下有向图：