how to code

all map

map of

struct

symmetry

array real

array

邻接表-链式存储

• 顶点的表示：顶点索引+出弧链表头指针+顶点数据

• 弧：弧头顶点索引+下一条弧指针+弧数据

• 逆邻接表：记录的是 入弧链表头指针 和 弧尾顶点索引

• struct Node{顶点索引；该顶点弧链表的头结点；顶点数据；}

• struct Arc{指向的顶点索引；指向下一条弧的指针；弧信息；}

• struct Map{顶点数组；}

顶点：  

顶点索引               出弧链表头指针                         顶点数据

    |                                  |                                           |

顶点索引      第一个出弧的指针(可以是NULL)         顶点数据

弧的表示方法：

弧头顶点索引                下一条弧指针                  弧数据

         |                                    |                                |

弧头顶点(指向的点)        一个点有多个弧              弧数据

                               每个弧保存下一条弧的指针

邻接矩阵用数组进行表达，相对来说比较简单。

邻接表和十字链表都是用链表表达，主要用于表示有向图。

邻接多重表则用于表示无向图。

领接矩阵：

自身不能到达自身，所以为0，以上是有向图，无向图的矩阵是对称的，所以克制抵只记录上或者下三角矩阵

数据结构用代码进行表示：

邻接表（记录出弧的链表的头指针）：逆-入弧

这样的数据结构方式如何通过数据结构的代码来实现呢？

可以把无向图中每一条连线当成有向图中的两条连线（去、回）

有向图中：

出度：一个顶点发出去的箭头数量

无向图中：

对于无向图来说，如果满足每一个顶点，都有通往其他顶点的连线（直接或间接）这样的图称为连通图。

在无向图中，如果任意顶点 与其他顶点都有连线，这样的图称为完全图。

1、图的存储结构

邻接表表示图需要的类：

顶点：  

顶点索引               出弧链表头指针                         顶点数据

    |                                  |                                           |

顶点索引      第一个出弧的指针(可以是NULL)         顶点数据

弧的表示方法：

弧头顶点索引                下一条弧指针                  弧数据

         |                                    |                                |

弧头顶点(指向的点)        一个点有多个弧              弧数据

                               每个弧保存下一条弧的指针

邻接表表达图：

顶点和图：

顶点保存点的索引和数据

图保存顶点数组和邻接矩阵

邻接矩阵方法：

图->数据

图的存储结构：

    邻接矩阵(数组)

    邻接表(链表)-->存储有向图

    十字链表(链表)-->存储有向图

    邻接多重表(链表) -->无向图

【图的存储结构】邻接矩阵（用数组表达）、邻接表（链表，有向图）、十字链表（链表，有向图）、邻接多重表（链表，用于表达无向图）

【权值】弧/边上的数据（比如两个城市之间的某条公路是300km）

1、邻接矩阵

• 顶点的表示：顶点索引+顶点数据

• 有弧的用1表示，没有弧的用0表示，自己和自己用0

• 

• int matrix[4][4];

• struct Node{顶点索引；顶点数据；}

• struct Map{顶点数组；邻接矩阵；}

2、邻接表-链式存储

• 顶点的表示：顶点索引+出弧链表头指针+顶点数据

• 弧：弧头顶点索引+下一条弧指针+弧数据

• 逆邻接表：记录的是 入弧链表头指针 和 弧尾顶点索引

• struct Node{顶点索引；该顶点弧链表的头结点；顶点数据；}

• struct Arc{指向的顶点索引；指向下一条弧的指针；弧信息；}

• struct Map{顶点数组；}
  

邻接表与逆邻接表:

顶点：顶点索引，出弧链表头指针，顶点数据；

弧：弧头顶点索引，吓一跳弧指针，弧数据

顶点结构体：包括顶点索引和顶点数据;

图的结构体：包括顶点数组和邻接矩阵

顶点结构体：包括顶点索引和顶点数据就行 图的结构体：包括顶点数组（记录顶点）和邻接矩阵（记录边，并且顶点和边的关系）就行 邻接表与逆邻接表：相对于弧的出入顶点说的，如果存储的是弧出顶点的就是邻接表，如果存储的是弧进顶点就是逆邻接表

邻接表--链式存储

邻接表--链式存储

邻接矩阵--数组存储