文档介绍：零基础学数据结构第10章图
图的定义与相关概念
5．连通图和强连通图
对于无向图G，如果从顶点vi到顶点vj存在路径中的顶点信息；另一个二维数组用来存储图中的顶点之间的关系，该二维数组被称为邻接矩阵。如果图是一个无权图，则邻接矩阵表示为：
对于带权图，有
图的存储结构
，两个图弧和边的集合分别为A={<a,b>,<a,d>,<b,c>,<c,a>,<c,b>,<d,c>}和E={(a,b),(a,c),(a,d),(b,c),(c,d)}。。
。
图的存储结构
图的邻接矩阵存储结构描述如下：
#define INFINITY 65535 /*65535被认为是一个无穷大的值*/
#define MaxSize 50 /*最大顶点个数*/
typedef enum{DG,DN,UG,UN}GraphKind; /*图的类型*/
typedef struct
{
VRType adj;/*对于无权图，用1表示相邻，0表示不相邻*/
InfoPtr *info; /*与弧或边的相关信息*/
}ArcNode,AdjMatrix[MaxSize][MaxSize];
typedef struct /*图的类型定义*/
{
VertexType vex[MaxSize]; /*用于存储顶点*/
AdjMatrix arc; /*邻接矩阵，存储边或弧的信息*/
int vexnum,arcnum; /*顶点数和边（弧）的数目*/
GraphKind kind; /*图的类型*/
}MGraph;
其中，数组vex用于存储图中的顶点信息，如’a’、’b’、’c’、’d’，arcs用于存储图中顶点信息。
图的存储结构
2．邻接矩阵应用举例
【例10_1】试编写一个算法，。
分析：主要考察图的邻接矩阵表示与算法实现。图的创建包括两个部分：一个是创建顶点，顶点信息可存储到一个向量（一维数组）中；一个是创建弧的信息，包括弧的相关顶点和权值，可存储到二维数组中，其中，二维数组的两个下标分别表示两个相关顶点在矩阵中的行号和列号，权值存入到数组中。
图的存储结构
邻接表
邻接表（adjacency list）是图的一种链式存储方式。采用邻接表表示图一般需要两个表结构：边表和表头结点表。
边表：在邻接表中，对图中的每个顶点都建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图来说是以顶点vi为尾的弧），这种链表称为边表，其中结点称为弧结点，弧结点由3个域组成：邻接点域（adjvex）、数据域（info）和指针域（nextarc）。其中，邻接点域表示与相应的表头顶点邻接点的位置，数据域存储与边或弧的信息，指针域用来指示下一个边或弧的结点。
图的存储结构
表头结点表：在每个链表前面设置一个头结点，除了设有存储各个顶点信息的数据域（data）外，还设有指向链表中第一个结点的链域（firstarc），我们把这种表称为表头结点表，相应地，结点称为表头结点。通常情况下，表头结点采用顺序存储结构实现，这样可以随机地访问任意顶点。
。
图的存储结构
。
。
图的存储结构
图的邻接表存储结构描述如下：
#define MaxSize 50 /*最大顶点个数*/
typedef enum{DG,DN,UG,UN}GraphKind; /*图的类型：有向图、有向网、无向图和无向网*/
typedef struct ArcNode /*边结点的类型定义*/
{
int adjvex; /*弧指向的顶点的位置*/
InfoPtr *info; /*与弧相关的信息*/
struct ArcNode *nextarc; /*指示下一个与该顶点相邻接的顶点*/
}ArcNode;
typedef struct VNode /*头结点的类