图的定义
图是一种与线性表和树相比更复杂的数据结构，在图形结构中，结构之间的关系可以是任意的，图中任意两个元素之间都可能相关
图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V，E），其中G表示一个图，V是图G中顶点的集合，E是图中边的集合，顶点也就是树中的结点。
图的分类
无向边：若顶点vi到vj之间的边没有方向，则称这条边为无向边，用（vi，vj）表示。最多为n（n-1）/2条边。
有向边：若vi到vj之间有方向，称为有向边，则用<vi,vj>表示，最多有n（n-1）条
有向图的权
有些图或弧具有与它相关的数字，这种与图的边或弧相关的树叫做权（Weight）
这些权可以表示从一个顶点到另一个顶点的距离或耗费，这种带权的图通常称为网（Network）
子图
连通性
在无向图G中如果两个点之间有路径可以到达，则称这两个点是连通的。如果对于图中任意两个顶点都可以到达，则会称G为连通图。
邻接矩阵
图的邻接矩阵储存方法是用两个数组表示
一个一维数组存储图中顶点信息
一个二维数组（邻接矩阵）储存图中的边或者弧的信息
为1表示两个点是连通的
邻接矩阵
邻接矩阵储存的结构
typedef char VertexType; //定义顶点类型 typedef int EdgeType; //边上权值类型由用户定义 #define MAXVEX 100 //最大顶点数 #define INFINITY 65535 //表示两个顶点不连通 typedef srtuct{ VertexType vexs[MAXVEX]; //顶点表 EdgeType arc[MAXVEX][MAXVEX]; //边表 int numVertexes,numEdges; //图中当前的顶点数和边数 }MGraph;
领接表
图中顶点用一个一维数组储存，当然顶点也可以用单链表储存，不过数组可以较容易地读取顶点信息。另外对于顶点数组中，每个数据元素还需要储存指向第一个邻接点地指针，以便于查找该顶点的边信息。
邻接表的存储的结构
typedef char VertexType; //顶点类型 typedef int EdgeType; //边的权值 typedef struct EdgeNode{ int adjvex; //存储该顶点对应的下表 EdgeType weight; //用于储存权值，对于非网图不需要 struct EdgeNode *next; //链域，指向下一个邻接点 }EdgeNode;
邻接矩阵储存的结构
typedef struct VertexNode{ //顶点表结构，就一个信息和一个尾巴 VertexType data； //顶点域，存储顶点信息 EdgeNode *firstedge; //边表头指针 }VertexNode,AdjList[MAXVEX]; typedef struct{ AdjList adjList； //结构体数组 int numVertexes,numEdges; //图中当前顶点数和边数 }GraphAdjList;
