例:用邻接表和逆邻接表的形式描述下面的 有向图 v210 3V4 邻接表 逆邻接表 图的邻接链表存储表示 数 typedef struct Arct/弧结点类型 据 int adver InfoType "info 构 struct Are *nextarc: JAreNode; 之 typedef struct Vnode&∥/顶点向量类型 VertexType data AreNode *firstarc vNode; typedef struct( 22 Vnode vertices VerNum; int vernum, arenum; Graph Kind kind;) ALGraph;
11 数 据 结 构 之 图 21 例: 用邻接表和逆邻接表的形式描述下面的 有向图 1 2 3 4 邻接表 V1 V2 V3 V4 1 2 3 1 ^ ^ ^ ^ 0 1 2 3 逆邻接表 V1 V2 V3 V4 2 3 1 ^ ^ ^ 0 0 1 2 3 ^ 数 据 结 构 之 图 22 ¾ 图的邻接链表存储表示 typedef struct Arc{ //弧结点类型 int adjvex ; InfoType *info; struct Arc *nextarc; }ArcNode; typedef struct Vnode{ // 顶点向量类型 VertexType data; ArcNode *firstarc; }Vnode; typedef struct{ Vnode vertices[VerNum]; int vernum, arcnum; GraphKind kind; } ALGraph;
有向图的十字链表表示 在十字链表中,对应于有向图中每一条弧有 个结点,对应每个顶点也有一个结点 结 顶点结点 tailvex headvex h Datal firstin firstout 十字链表可以看成邻接矩阵的链式存储 000 >用C语言描述的十字链表 #define MAX VERTEX NUM 20 sx typedef struct ArcBox( 据 int tailvex, headvex;∥该弧的尾和头顶点的位置 构 struct Are Box *hlink,tink;/弧头及弧尾相同的弧的链域 info ∥该弧相关信息的指针 r Typedef stuct VexNodel Are Box * firstin, *firstout;/分别指向该顶点第一条入弧和出弧 24 Typedef struct Ⅴ exNode xlist MAX VERTEX NUM;表头向量 Int vexnum. arenum: 有向图的当前顶点数和弧数 ALGraph
12 数 据 结 构 之 图 23 ¾ 有向图的十字链表表示 ¾ 在十字链表中，对应于有向图中每一条弧有一 个结点，对应每个顶点也有一个结点。 ¾ 十字链表可以看成邻接矩阵的链式存储 tailvex headvex hlink tlink 弧结点 Data firstin firstout 顶点结点 V1 V2 V3 V4 V1 V2 ^ V3 V4 0 1 ^ 0 2 ^ ^ 2 3 ^ ^ 3 0 ^ ^ 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 数 据 结 构 之 图 24 ¾ 用C语言描述的十字链表： #define MAX_VERTEX_NUM 20 typdef struct ArcBox{ int tailvex, headvex; //该弧的尾和头顶点的位置 struct ArcBox *hlink, *tlink; //弧头及弧尾相同的弧的链域 InfoType *info; //该弧相关信息的指针 }ArcBox; Typedef stuct VexNode{ VertexType data; ArcBox *firstin, *firstout; //分别指向该顶点第一条入弧和出弧 }VexNode; Typedef struct{ VexNode xlist[MAX_VERTEX_NUM]; //表头向量 int vexnum, arcnum; //有向图的当前顶点数和弧数 }ALGraph;