★邻接表 今实现:为图中每个顶点建立一个单链表,第个单链表 中的结点表示依附于顶点Ⅵ的边(有向图中指以V为 尾的弧) typedef struct node int adjvex;∥邻接点域,存放与ⅵ邻接的点在表头数组中的位置 struct node*next;∥链域,指示下一条边或弧 JD adivex next 表头接点: typedef struct tnode int vexdata;∥放顶点信息 struct node* firestar;∥指示第一个邻接点| vexdata firstarc TD TDgM];∥g[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
例 vexdata firstarc adjvex next GI 1234 abcd 4∧ vexdata firstarc adivex next 例(a(b 2 2 5 G2 12345 abcde 43433 2
例 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 ^
今特点 ●无向图中顶点Ⅵ的度为第个单链表中的结点数 0有向图中 ◆顶点Ⅵ的出度为第个单链表中的结点个数 ◆顶点Ⅵ的入度为整个单链表中邻接点域值是的结点个数 逆邻接表:有向图中对每个结点建立以Ⅵ为头的弧的单链表 例 vexdata firstarc adjvex next 4 GI 234 abcd 3
❖特点 ⚫无向图中顶点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*tink,∥指向弧尾相同的下一条弧 JAD tailvex headvex hlink tlink 顶点结点: typedef struct dnode int data;∥与顶点有关信息 struct arcnode* firstin;∥指向以该顶点为弧头的第一个弧结点 struct arcnode* firstout;/指向以该顶点为弧尾的第一个弧结点 JDD data firstin firstout DDgM;,∥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 ∧∧ 4 42 +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 ^ ^ ^ ^ ^ ^ ^ ^