★邻接表 》实现：为图中每个顶点建立一个单链表，第个单链表 中的结点表示依附于顶点V的边（有向图中指以V为 尾的弧) typedef struct node int adjvex; ∥邻接点域，存放与V邻接的点在表头数组中的位置 struct node*next,/链域，指示下一条边或弧 JD; adjvex next 表头接点： typedef struct tnode { int vexdata;/∥存放顶点信息 struct node *firstarc; /指示第一个邻接点 vexdata firstarc }TD; TD ga[M;/ga[0]不用
邻接表 ❖实现：为图中每个顶点建立一个单链表，第i个单链表 中的结点表示依附于顶点Vi的边（有向图中指以Vi为 尾的弧） typedef struct node { int adjvex; //邻接点域，存放与Vi邻接的点在表头数组中的位置 struct node *next; //链域，指示下一条边或弧 }JD; adjvex next 表头接点： typedef struct tnode { int vexdata; //存放顶点信息 struct node *firstarc; //指示第一个邻接点 }TD; TD ga[M]; //ga[0]不用 vexdata firstarc
例 a b vexdata firstarc adjvex next a 2 d 2 b 3 4 d vexdata firstarc adivex next 例 6 a c G2 5
例 G1 b d a c 例 a e c b d G2 1 2 3 4 a c d b vexdata firstarc 3 2 4 1 ^ ^ ^ ^ adjvex next 1 2 3 4 a c d b vexdata firstarc 4 2 1 2 ^ ^ ^ adjvex next 5 e 4 1 3 5 ^ 5 3 2 3 ^
特点 ●无向图中顶点V的度为第个单链表中的结点数 ●有向图中 ◆顶点的出度为第个单链表中的结点个数 ◆顶点V的入度为整个单链表中邻接点域值是的结点个数 ●逆邻接表：有向图中对每个结点建立以为头的弧的单链表 vexdata firstarc adjvex next a 2 b 3 d
❖特点 ⚫无向图中顶点Vi的度为第i个单链表中的结点数 ⚫有向图中 ◆顶点Vi的出度为第i个单链表中的结点个数 ◆顶点Vi的入度为整个单链表中邻接点域值是i的结点个数 ⚫逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表 例 G1 b d a c 1 2 3 4 a c d b vexdata firstarc 4 1 ^ 1 ^ ^ 3 ^ adjvex next
★有向图的十字连表表示法 弧结点： typedef struct arcnode {'int tailvex,headvex;/弧尾、弧头在表头数组中位置 struct arcnode*hlink;/指向弧头相同的下一条弧 struct arcnode *tlink: /指向弧尾相同的下一条弧 }AD; tailvex headvex hlink tlink 顶点结点： typedef struct dnode {int data,l∥存与项点有关信息 struct t arcnode*firstin;/指向以该顶点为弧头的第一个弧结点 struct arcnode*firstout;/指向以该顶点为弧尾的第一个弧结点 DD: data firstin firstout DDg[M;I/gO]不用
有向图的十字链表表示法 弧结点： typedef struct arcnode { int tailvex, headvex; //弧尾、弧头在表头数组中位置 struct arcnode *hlink；//指向弧头相同的下一条弧 struct arcnode *tlink; //指向弧尾相同的下一条弧 }AD; tailvex headvex hlink tlink 顶点结点： typedef struct dnode { int data; //存与顶点有关信息 struct arcnode *firstin；//指向以该顶点为弧头的第一个弧结点 struct arcnode *firstout; //指向以该顶点为弧尾的第一个弧结点 }DD; DD g[M]; //g[0]不用 data firstin firstout
例 12→13 31 34 -4142-43
例 b d a c a b c d 1 2 3 4 1 2 1 3 3 1 3 4 4 1 4 2 4 3 ^ ^ ^ ^ ^ ^ ^ ^