图的储存结构

图的储存结构：邻接矩阵，邻接表，十字链表，邻接多重表，边集数组
实现方式：矩阵，链表构成的数组*3，三元组

邻接矩阵（n个结点，构造n*n的矩阵，各点值可达为1，不可达为0）

当我们需要将权重赋在矩阵上时，各点值若可达，则为其权重；不可达则为∞（INT_MAX）；对角元为0

邻接表（n个结点，构造有n个首结点的数组，每个首结点拉出一条含该首结点所有可达结点的链表）


typedef struct node{
	int vex;
	int cost;//对应VNode到该点的权重
	struct node* next;
}ENode;
typedef struct{
	int vex;
	ENode* next;
}VNode;
typedef struct{
	VNode adjlist[N];
	int nv,ne;
}TGraph;

十字链表（有向图）

相比于邻接表，VNode多开了个指针域让你指向以该点为弧尾的第一个弧结点，便于同时求出度和入度，将原先的TNode变成有两个结点编号和两个指针域（一个指向弧头相同的下一条弧，一个指向弧尾相同的下一条弧）的Vex（弧结点）。


typedef struct vex{
	int headvex,tailvex;//弧头（尾）顶点编号
	int cost;
	struct vex* hlink,tlink;//指向弧头（尾）相同的下一条弧
}Vex;
typedef struct{
	int data;//存放顶点信息
	Vex* firstin;//以该点为弧头的第一个弧结点
        Vex* firstout;//以该点为弧尾的第一个弧结点
}VNode;
typedef struct{
	VNode orthlist[N];
	int nv,ne;
}OrthGraph;

邻接多重表（无向图）

相比于邻接表，VNode不变，将原先的TNode变成有两个结点编号和两个指针域（一个指向下一条依附）的Vex（弧结点）


typedef struct vex{
	int ivex,jvex;//依附于该边的两个顶点编号
	int cost;
	struct vex* ilink;//指向下一条依附于顶点ivex的边
        struct vex* jlink;//指向下一条依附于顶点jvex的边
}Vex;
typedef struct{
	int data;//存放顶点信息
	Vex* firstedge;//指向第一条依附于该顶点的边结点
}VNode;
typedef struct{
	VNode orthlist[N];
	int nv,ne;
}OrthGraph;

（TIPS_对比：十字链表注重对边的操作，而邻接多重表更注重对点的操作）

边集数组（类似于三元组）


typedef struct{
	int vex;
	int gno;//连通分量，用于kruskal算法
}TVex;
typedef struct{
	int va,vb;
	int cost;	
}TEdge;

typedef struct{
	TVex* pv;
	TEdge* pe;
	int nv,ne;
}TGraph;