|
文章目录
1.邻接矩阵2.图的创建3.图的基本操作3.1 LocateVex3.2 FirstAdjVex3.3 NextAdjVex3.4 showMatrix
4.图的遍历4.1 深度优先遍历4.2 广度优先遍历
5.测试代码参考资料
1.邻接矩阵
用两个数组分别存储：数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。 其形式描述如下：
// ----- 图的数组（邻接矩阵）存储表示 ----- //
// 常量定义
# define INFINITY -1 // 最大权重，表示不邻接关系
# define MAX_VERTEX_NUM 10 // 最大顶点个数
typedef int VRType; // 顶点间的关系类型，如0/1表示邻接否
typedef char InfoType; // 弧段的信息类型
typedef char VertexType; // 顶点信息类型
typedef enum { DG, DN, UDG, UDN } GraphKind; // 有向图、有向网、 无向图、无向网
// 图的邻接矩阵存储结构定义
typedef struct ArcCell { // 弧/边的基本结构
VRType adj; // VRType是顶点的关系类型，对无权图用1或0表示是否相邻，对带权图（网）用权值
InfoType *info; // 该弧段相关信息的指针
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct { // 图的基本结构
VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量
AdjMatrix arcs; // 邻接矩阵
int vexnum, arcnum; // 当前节点、边二点数目
GraphKind kind; // 图的种类
}MGraph;
2.图的创建
无向网（带权值的无向图）
//构造无向网UDN
void createUDN(MGraph& G) {
int incInfo; //表示有无弧上信息，0表示弧不含任何信息
cin >> G.vexnum >> G.arcnum >> incInfo;
int i, j;
for (i = 0; i > G.vexs[i]; // 输入顶点的信息
for (i = 0; i INFINITY,NULL }; // 初始化邻接矩阵
}
for (i = 0; i
int IncInfo; //IncInfo为0表示各个边不存储信息
cin >> G.vexnum >> G.arcnum >> IncInfo;
int i, j;
for (i = 0; i > G.vexs[i]; //输入各个顶点的数据
for (i = 0; i -1,NULL };
//初始化邻接矩阵，一般是初始化为0，
//但是这里我与前面UDN一致是为了通用一些查找函数
}
// 输入邻接的点来构造邻接边
for (i = 0; i
int i;
for (i = 0; i
if (G.arcs[index][i].adj != -1) break;
}
if (i == G.vexnum) return -1; // 没有临界点
else return i;
}
3.3 NextAdjVex
int NextAdjVex(MGraph G, VertexType v, VertexType u); // 返回G中顶点v相对于u的下一邻接点
int NextAdjVex(MGraph G, VertexType v, VertexType u) {
int indexV = LocateVex(G, v);
int indexU = LocateVex(G, u);
int index;
for (index = indexU + 1; index
for (int j = 0; j
if (!visited[i]) DFS(G, i, visited); // 对尚未访问的顶点i调用DFS，
// 因为图G可能不是连通图
}
}
// 从图中第v个顶点开始进行深度优先遍历
void DFS(MGraph G, int v, int* visited) {
visited[v] = 1; //先访问顶点v
cout
// 按照广度优先非递归遍历图G，使用辅助队列Q和访问标志数组visited。
int* visited = new int[G.vexnum];
queue Q;
int i;
for (i = 0; i //访问顶点i
visited[i] = 1;
cout
if (!visited[w]) { // w为u的尚未访问的邻接顶点
visited[w] = 1;
cout // 弧/边的基本结构
VRType adj; // VRType是顶点的关系类型，对无权图用1或0表示是否相邻，对带权图（网）用权值
InfoType *info; // 该弧段相关信息的指针，一般不需要
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct { // 图的基本结构
VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量
AdjMatrix arcs; // 邻接矩阵
int vexnum, arcnum; // 当前节点、边二点数目
GraphKind kind; // 图的种类
}MGraph;
// 图的基本操作
int LocateVex(MGraph G, VertexType u); // 返回顶点u在图中的位置
int FirstAdjVex(MGraph G, VertexType u); // 返回图G中u的第一个邻接节点
int NextAdjVex(MGraph G, VertexType v, VertexType u); // 返回G中顶点v相对于u的下一邻接点
//构造无向网UDN
void createUDN(MGraph& G); //创建无向网
void createUDG(MGraph& G); //创建无向网
// 图的深度优先遍历
void DFSTraverse(MGraph G);
// 从图中第v个顶点开始,递归进行深度优先遍历图G
void DFS(MGraph G, int v, int* visited);
// 图的广度优先遍历
void BFSTraverse(MGraph G);
// 打印图的邻接矩阵
void showMatrix(MGraph G);
int main() {
MGraph G;
G.kind = UDN;
createUDN(G);
printf("无向网的邻接矩阵:\n");
showMatrix(G);
printf("顶点F的第一个邻接点:");
int index = FirstAdjVex(G, "F");
cout |