目录
图的存储结构
- 图的逻辑结构：多对多
- 图没有顺序存储结构，但可以借助二维数组来表示元素间的关系
邻接矩阵（数组）表示法
有向图
- 无权图的邻接矩阵
若有向无权图G=(V，E)有n(n≧1)个顶点，则其邻接矩阵是n阶对称方阵
第i行：以结点Vi为尾的弧（出度边）
第j列：以结点Vj为头的弧（入度边）
- 带权图的邻接矩阵
无向图
- 无向无权图：对称矩阵
①顶点i的度 = 第i行(列)中1的个数
- 无向有权图
邻接矩阵的存储表示
用两个数组分别存储顶点表和邻接矩阵
#define MaxInt 32767 //表示极大值，即∞
#define MVNum 100 //最大顶点数
typedef char VerTexType; //设顶点的数据类型为字符型
typedef int ArcType; //假设边的权值类型为整型
typedef struct{
VerTexType vexs[MVNum]; //顶点表
ArcType arcs[MVNum][MVNum]; //邻接矩阵
int vexnum,arcnum; //图的当前点数和边数
}AMGraph; 采用邻接矩阵表示法创建无向图
①输入总顶点数和总边数
②依次输入点的信息存入顶点表中
③初始化邻接矩阵，使每个权值初始都是极大值
④构造邻接矩阵
Status CreateUDN(AMGraph &G){ //采用邻接矩阵表示法，创建无向网G
cin>>G.vexnum>>G.arcnum; //输入总顶点数，总边数
for(i=0;i < G.vexnum;++i)
cin>>G.vexs[i]; //依次输入点的信息
for(i=0;i < G.vexnum;++i)
for(j=0;j < G.vexnum;++j)
G.arcs[i][j] = MaxInt; //边的权值均置为极大值
for(k=0;k < G.arcnum;++k){ //构造邻接矩阵
cin>>v1>>v2>>w; //输入一条边所依附的顶点及边的权值
i = LocateVex(G,v1);
j = LocateVex(G.v2); //确定v1和v2在G中的位置
G.arcs[i][j] = w; //边<v1,v2>的权值置为w
G.arcs[j][i] = G.arcs[i][j];
}
return OK;
}
在图中查找顶点
int LocateVex(AMGraph G，VertexType u){
//图G中查找顶点u，存在则返回顶点表中的下标；否则返回-1
int i;
for(i=0;i < G.vexnum;++i)
if(u == G.vexs[i]) return i;
return -1;
}邻接矩阵表示法的优缺点
优点：①直观、方便、好理解
②方便检查任意一对顶点间是否存在边
③方便找任一顶点的所有“邻接点”（有边直接相连的顶点）
④方便计算任一顶点的“度”
缺点：①不便于增加和删除顶点
②浪费空间–存稀疏图（点很多而边很少）有大量无效元素
③浪费时间–统计稀疏图中一共有多少条边
邻接表（链式）表示法
无向图
- 线性链表存储
- 链表中的结点称为表结点，每个结点由三个域组成。其中邻接点域（adjvex）指示与顶点Vi邻
接的顶点在图中的位置（顶点编号），链域（nextarc）指向下一个与顶点Vi邻接的表结点，数据
域（info）存储和边或弧相关的信息，如权值。对于无权图，则可以省略此区域。
- 每个链表设一个表头结点（顶点结点），由两个域组成。链域(firstarc)指向链表中的第一个结
点,数据域(data)存储顶点名或其他信息
特点
①邻接表不唯一
②若无向图中有n个顶点，e条边，则其邻接表需n个头结点和2e个表结点。适宜存储稀疏图
③无向图中顶点Vi的度为第i个单链表中的结点数
有向图
①需要n+e个存储空间
②正邻接表中顶点Vi的出度为第i个单链表中的结点个数
③逆邻接表中顶点Vi的入度为整个单链表中邻接点域值是i-1的结点个数
图的邻接表存储表示算法
表头顶点（顶点结点）
typedef struct VNode{
VerTexType data; //顶点信息
ArcNode *firstarc; //指向第一条依附该顶点的边的指针
}VNode,AdjList[MVNum]; //AdjList表示邻接表类型图的结构定义
typedef struct{
AdjList vertices;
int vexnum,arcnum; //图的当前顶点数和弧数
}ALGraph;//邻接表表示的图算法思想
1.输入总顶点数和总边数
2.建立顶点表
①依次输入点的信息存入顶点表中
②使每个表头结点的指针域初始化为NULL
3.创建邻接表
①依次输入每条边依附的两个顶点
②确定两个顶点的序号i和j，建立边结点
③将此边结点分别插入到Vi和Vj对应的边链表的头部
采用邻接表表示法创建无向图 时间复杂度为O(n+e)
Status CreateUDG(ALGraph &G){ //采用邻接表表示法，创建无向图G
cin>>G.vexnum>>G.arcnum; //输入总顶点数和总边数
for(i=0;i < G.vexnum;++i){ //输入各点，构造表头结点表
cin>>G.vertices[i].data; //输入顶点值
G.vertices[i].firstarc = NULL; //初始化表头结点的指针域
}
for(k=0;k < G.arcnum;++k){ //输入各边，构造邻接表
cin>>v1>>v2; //输入一条边所依附的两个顶点
i = LocateVex(G,v1);
j = LocateVex(G.v2);
p1 = new ArcNode; //生成一个新的边结点*p1
p1 -> adjvex = j; //从i指向j,将p1的邻接点序号置为j
p1 -> nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc = p1; //将新结点*p1插入顶点Vi的边表的第一个
p2 = new ArcNode; //生成一个新的边结点*p2
p2 -> adjvex = i; //从j指向i,将p2的邻接点序号置为i
p2 -> nextarc = G.vertices[j].firstarc;
G.vertices[j].firstarc = p2; //将新结点*p2插入顶点Vj的边表的第一个
}
return OK;
}
邻接表特点：①方便找任一顶点的所有“邻接点”
②节约稀疏图的空间：无向图需要N个头指针+2e个结点（每个结点至少2个域）
③邻接表的表示不唯一
邻接矩阵的空间复杂度为O(n^2); 邻接表的空间复杂度为O(n+e)
邻接矩阵多用于稠密图；邻接表多用于稀疏图
十字链表
邻接多重表
①Data域：存储和顶点相关的信息
②指针域firstedge:指向依附于该顶点的第一条边所对应的表结点
③标志域mark:用以标示这条边是否被访问过
④ivex和jvex域：分别保存该边所依附的两个顶点在图中的位置
⑤info域：保存该边的相关信息
⑥指针域ilink:指向下一条依附于顶点ivex的边
⑦指针域jlink:指向下一条依附于顶点jvex的边
//无向图的邻接多重表存储表示
#define MAX_VERTEX_NUM 20
typedef enum{
unvisited,visited
}VisitIf;
typedef struct EBox{
VisitedIf mark; //访问标记
int ivex,jvex; //该边依附的两个顶点的位置
struct EBox *ilink,*jlink; //分别指向依附这两个顶点的下一条边
InfoType *info; //该边信息指针
}Ebox;
typedef struct VexBox{
VerTexType data;
EBox *firstedge; //指向第一条依附该顶点的边
}VexBox;
tyypedef struct{
VexBox adjmulist[MAX_VERTEX_NUM];
int vexnum,edgenum; //无向图的当前顶点数和边数
}AMLGraph;
抽象数据类型定义
ADT Graph{
数据对象V：具有相同特性的数据元素的集合，称为顶点集。
数据关系R：R={VR}
VR={<v,w>|<v,w>| v,wV∧p(v,w) ，<v,w>表示从v到w的弧，P(v,w)定义了弧<v,w>的信息 }
基本操作P：
Create_Graph() ： 图的创建操作。
初始条件：无。
操作结果：生成一个没有顶点的空图G。
GetVex(G, v) ： 求图中的顶点v的值。
初始条件：图G存在，v是图中的一个顶点。
操作结果：生成一个没有顶点的空图G。
… …
DFStraver(G,V)：从v出发对图G深度优先遍历。
初始条件：图G存在。
操作结果：对图G深度优先遍历，每个顶点访问且只访问一次。
BFStraver(G,V)：从v出发对图G广度优先遍历。
初始条件：图G存在。
操作结果：对图G广度优先遍历，每个顶点访问且只访问一次。
} ADT Graph 版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/83250.html
