图的储存
最基本的图论。。。但是也不能松懈啊
有邻接矩阵,邻接链表。。。
1.1 无向图的数组表示
(1) 无权图的邻接矩阵
无向无权图G=(V,E)有n(n≧1)个顶点,其邻接矩阵是n阶对称方阵。其元素的定义如下:
(2) 带权图的邻接矩阵
无向带权图G=(V,E)的邻接矩阵元素的定义如下:
(3) 无向图邻接矩阵的特性
a) 邻接矩阵是对称方阵;
b) 对于顶点vi,其度数是第i行(或第i列)的非0元素的个数;
c) 无向图的边数是上(或下)三角形矩阵中非0元素个数。
1.2 有向图的数组表示
(1) 无权图的邻接矩阵
若有向无权图G=(V,E)有n(n≧1)个顶点,其邻接矩阵元素定义如下:
(2) 带权图的邻接矩阵
有向带权图G=(V,E)的邻接矩阵元素的定义如下:
(3) 有向图邻接矩阵的特性
- a) 对于顶点vi,第i行的非0元素的个数是其出度OD(vi);第i列的非0元素的个数是其入度ID(vi)。
- b) 邻接矩阵中非0元素的个数就是图的弧的数目。
2 邻接表
基本思想:对图的每个顶点建立一个单链表,存储该顶点所有邻接顶点及其相关信息。每一个单链表设一个表头结点。第i个单链表表示依附于顶点Vi的边(对有向图是以顶点Vi为头或尾的弧)。
2.1链表中的结点称为表结点,每个结点由三个域组成,如图所示。其中邻接点域(adjvex)指示与顶点Vi邻接的顶点在图中的位置(顶点编号),链域(nextarc)指向下一个与顶点Vi邻接的表结点,数据域(info)存储和边或弧相关的信息,如权值等。对于无权图,如果没有与边相关的其他信息,可省略此域。
每个链表设一个表头结点(称为顶点结点),由两个域组成,如图所示。链域(firstarc)指向链表中的第一个结点,数据域(data)存储顶点名或其他信息。
在图的邻接表中,所有顶点结点用一个向量以顺序结构形式存储,可以随机访问任意顶点的链表,该向量称为表头向量,向量的下标指示顶点的序号。
//图的邻接表存储表示 #define MAX_VERTEX_NUM 20 typedef struct ArcNode { int adjvex; //该弧所指向的顶点的位置 struct ArcNode *nextarc; //指向下一条弧 InfoType *info; //该弧相关信息的指针 }ArcNode; typedef struct VNode { VertexType data; //顶点信息 ArcNode *firstarc; //指向依附该顶点的第一条弧 }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum,arcnum; //图的当前顶点数和弧数 int kind; //图的种类标志 }ALGraph;
2.2 示例
用邻接表存储图时,对无向图,其邻接表是唯一的,对有向图,其邻接表有两种形式,如图所示。
3数组模拟链表
struct node { int u,w,v,next; }e[200010]; int st[MAXN]; void add(int x,int y,int z) { e[++tot].u=x; e[tot].v=y; e[tot].w=z; e[tot].next=st[x]; st[x]=tot; }