PPT《《 数据结构》》

2 4

1 3 ? ? ? ? ? ? ? ? 7.2.1 数组表示法 邻接矩阵:表示顶点间相联关系的矩阵.定义:设G=(V,{E})是有n?1个顶点的图,G的邻接矩阵A是具有以下性质的n阶方阵: 例:

1 5

3 2

4 G2 ? ? ? ? ? ? ? ? ? ? 网的邻接矩阵可定义为: ? ? ? ? ? ? ? ? ? ? 例:

1 4

5 2

3 7

5 3

1 8

6 4

2 邻接矩阵类型定义: #define INFINITY INT_MAX#define MAX_VERTEX_NUM 20typedef enum{DG,DN,AG,AN} GraphKind;

typedef struct ArcCell{ VRType adj;

InfoType * info;

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]typedef struct{ VertexType vexs[MAX_VERTEX_NUM];

AdjMatrix arcs;

int vexnum,arcnum;

GraphKind kind;

}MGraph;

adjvex nextarc vexdata firstarc 邻接表的类型定义参见P163. 7.2.2 邻接表 实现:为图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点Vi的边(有向图中指以Vi为尾的弧). 例: G1 b d a c

1 2

3 4 a c d b vexdata firstarc

3 2

4 1 ^ ^ ^ ^ adjvex nextarc 例: a e c b d G2

1 2

3 4 a c d b vexdata firstarc

4 2

1 2 ^ ^ ^ adjvex nextarc

5 e

4 3

5 ^

1 5

3 2

3 ^ 例: G1 b d a c

1 2

3 4 a c d b vexdata firstarc

4 1 ^

1 ^ ^

3 ^ adjvex nextarc 逆邻接表:有向图中对每个结点建立以Vi为弧头的弧的单链表.