图-图的表示方法

图的表示法

邻接矩阵表示法-表示顶点间邻接关系的矩阵
- 无向图的邻接矩阵

（1）无向图的邻接矩阵式对称矩阵，可以压缩存储；有n个结点的无向图需要的存储空间为n(n+1)/2

（2）无向图的中，顶点v_i的度是邻接矩阵中的第i行元素之和

- 有向图的邻接矩阵

　　（1）有向图的邻接矩阵不一定对称，有n个顶点的有向图需要存储空间为n²

　　（2）有向图中：顶点v_i的出度是邻接矩阵中第i行元素之和，顶点v_i的出度是邻接矩阵中第i列元素之和

- 网的邻接矩阵（网是带权的图）

邻接矩阵的数据类型定义

1 #define MaxVertexNum 100    //顶点数目最大值
2 typedef char VertexType;    //顶点数据类型
3 typedef int EdgeType;    //带权图中边上权值的数据类型,如果仅表示表示边存在与否，可以定义为0，1的枚举类型
4 typedef struct
5 {
6     VertexType Vex[MaxVertexNum];    //顶点表
7     EdgeType Edge[MaxVertexNum][MaxVertexNum];    //邻接矩阵边表
8     int vexnum, arcnum;    //图的当前顶点和弧数
9 }MGraph;

邻接表表示法
- 处理
  - 图中顶点用一个一维数组存储。顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该结点的边信息
  - 图中每个顶点v_i的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图中称为顶点v_i的边表，有向图则称为顶点v_i作为弧尾的出边表
- 无向图的邻接表

- 有向图的邻接表

- 网的邻接表
  - 对于带权值的网图，可以在边表结点定义中在增加一个weight的数据域，存储权值即可

邻接表的数据类型定义

 1 #define MaxVertexNum 100 //顶点数目的最大值
 2 typedef char VertexType;
 3 typedef int EdgeType;
 4 typedef struct ArcNode    //边表结点
 5 {
 6     int adjVex;        //该弧所指向的顶点的位置
 7     struct ArcNode *next;        //指向下一条弧的指针
 8     //infoType info        //带权图的权值
 9 }ArcNode;
10 typedef struct VNode    //顶点表结点
11 {
12     VertexType data;    //顶点的信息
13     ArcNode *first;        //指向第一条依附该顶点的弧的指针
14 }VNode, AdjList[MaxVertexNum];
15 typedef struct
16 {
17     AdjList    vertices;    //邻接表
18     int vernum, arcnum;        //图的顶点数和弧数
19 }ALGraph;            //ALGraph是以邻接表存储的图的类型