6.2 图的存储及基本操作
6.2.1 邻接矩阵法
邻接矩阵存储无向图、有向图
#define MaxVertexNum 100 //顶点数目的最大值typedef struct{char Vex[MaxVertexNum]; //顶点表int Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵，边表int vexnum,arcnum; //图的当前顶点数和边数
}MGraph;
第i个结点的度 = 第i行（或第i列）的非零元素个数
第i个结点的出度 = 第i行的非零元素个数
第i个结点的入度 = 第i列的非零元素个数
第i个结点的度 = 第i行、第i列的非零元素个数之和
邻接矩阵法求顶点的度/出度/入度的时间复杂度为O(|V|)
邻接矩阵法存储带权图
#define MaxVertexNum 100 //顶点数目的最大值
#define INFINITY 2147483647; //表示“无穷”typedef char VertexType; //顶点数据类型
typedef int EdgeType; //边数据类型typedef struct{VertexType Vex[MaxVertexNum]; //顶点表EdgeType Edge[MaxVertexNum][MaxVertexNum]; //边的权值int vexnum,arcnum; //图的当前顶点数和弧数
}MGraph;
邻接矩阵法的性能分析
空间复杂度：O(|V|^2) ——只和顶点数相关，和实际的边数无关
适合用于存储稠密图
无向图的邻接矩阵是对称矩阵，可以压缩存储（只存储上三角区/下三角区）
邻接矩阵法的性质
6.2.2 邻接表法
邻接表法（顺序+链式存储）
#define MVNum 100 //最大顶点数typedef struct ArcNode{ //边/弧 int adjvex; //邻接点的位置 struct ArcNode *next; //指向下一个表结点的指针
}ArcNode;typedef struct VNode{ char data; //顶点信息 ArcNode *first; //第一条边/弧
}VNode, AdjList[MVNum]; //AdjList表示邻接表类型 typedef struct{ AdjList vertices; //头结点数组int vexnum, arcnum; //当前的顶点数和边数
}ALGraph;
| 邻接表 | 邻接矩阵 | |
| 空间复杂度 | 无向图 O(|V| + 2|E|) ；有向图O(|V| + |E|) | O(|V|^2 |
| 适合用于 | 存储稀疏图 | 存储稠密图 |
| 表示方式 | 不唯一 | 唯一 |
| 计算度/出度/入度 | 计算有向图的度、入度不方便，其余很方便 | 必须遍历对应行或列 |
| 找相邻的边 | 找有向图的入边不方便，其余很方便 | 必须遍历对应行或列 |
6.2.3 十字链表
十字链表存储有向图
#define MAX_VERTEX_NUM 20 //最大顶点数量typedef struct ArcBox{ //弧结点int tailvex, headvex; //弧尾，弧头顶点编号（一维数组下标）struct ArcBox *hlink, *tlink; //弧头相同、弧尾相同的下一条弧的链域InfoType info; //权值
}ArcBox;typedef struct VexNode{ //顶点结点VertexType data; //顶点数据域ArcBox *firstin, *firstout; //该顶点的第一条入弧和第一条出弧
}VexNode;typedef struct{ //有向图VexNode xlist[MAX_VERTEX_NUM]; //存储顶点的一维数组int vexnum, arcnum; //有向图的当前顶点数和弧数
}OLGraph;
十字链表法性能分析
空间复杂度：O(|V|+|E|)
顺着绿色线路找可以找到指定顶点的所有出边
顺着橙色线路找可以找到指定顶点的所有入边
注意：十字链表只用于存储有向图
6.2.4 邻接多重表
#define MAX_VERTEX_NUM 20 //最大顶点数量struct EBox{ //边结点int i,j; //该边依附的两个顶点的位置（一维数组下标）EBox *ilink,*jlink; //分别指向依附这两个顶点的下一条边InfoType info; //边的权值
};
struct VexBox{VertexType data;EBox *firstedge; //指向第一条依附该顶点的边
};
struct AMLGraph{VexBox adjmulist[MAX_VERTEX_NUM];int vexnum,edgenum; //无向图的当前顶点数和边数
};
空间复杂度：O(|V|+|E|)
删除边、删除节点等操 作很方便
注意：邻接多重表只适 用于存储无向图 
6.2.5 图的基本操作
- Adjacent(G,x,y):判断图G是否存在边<x, y>或(x, y)。(<>表示有向图，()表示无向图)
- Neighbors(G,x):列出图G中与结点x邻接的边。
- lnsertVertex(G,x):在图G中插入顶点x。
- DeleteVertex(G,x):从图G中删除顶点x。
- AddEdge(G,x,y):若无向边(x,y)或有向边<x, y>不存在，则向图G中添加该边。RemoveEdge(G,x,y):若无向边(x, y)或有向边<x, y>存在，则从图G中删除该边。
- FirstNeighbor(G,x):求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1。
- NextNeighbor(G,x,y):假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。
- Get_edge_value(G,x,y):获取图G中边(x, y)或<x, y>对应的权值。
- Set edge value(G,x,y,v):设置图G中边(x, y)或<x, y>对应的权值为v。
