| 图的基本操作（无向图） | 您所在的位置：网站首页 › 火的图片怎么画呢简单的图画法 › 图的基本操作（无向图） |
图的基本操作（无向图）
|
图的定义
图（Graph）在是一种较线性表和树更为复杂的数据结构。 在线性表中，数据元素之间是被串起来的，只有线性关系，每个数据元素只有一个直接前驱和一个直接后继。 在图中的数据元素叫做顶点（Vertex），假定V是顶点的有穷非空集合；VR是两个顶点直接的关系的集合。若∈VR，则表示从v到w的一条弧（Arc），且称v为弧尾（Tail）或初始点，称w为弧头（Head）或终端点。 此时的图为有向图，即顶点之间的弧是有方向的。
如果∈VR，必有∈VR，即VR是对称的，则以无序对（v,w)来代替这两个有序对，表示v和w之间的一条边（Edge），边是没有方向的，此时的图称为无向图 如果图的弧或边具有与它相关的数字，则称这种与图的边或弧相关的数叫做权值（Weight），这种带权值的图成为网（Net）。带权值的有向图成为有向网 带权值的无向图称为无向网 用一维数组存储图中顶点的信息（顶点表），用二维数组存储图中边或弧的信息（邻接矩阵）。 在无向图和有向图中，若两顶点之间有边或弧，则二维数组中点为1，否则为0。 在无向网和有向网中，若两顶点之间有边或弧，则二维数组中的点为其权值，否则为∞。 当边数相对顶点数较少的图时，邻接矩阵这种结构会极大的浪费存储空间。于是我们使用一种把数组和链表相结合的存储方式——邻接表，用一个一维数组来存放顶点信息（顶点表），在将图中的每个顶点所有邻接点构成一个线性表，用单链表存储。 还有十字链表、邻接多重表和边集数组这三种存储结构，本文不着重说明。 本文重点讲解无向图的邻接矩阵基本操作 无向图的邻接矩阵基本操作首先定义和声明一下之后会用到的宏 无向图的数据元素的声明和队列的数据元素的声明（队列在广度优先遍历中会使用到） #include using namespace std; typedef char VertexType; typedef int EdgeType; typedef int status; typedef int QElemType; #define MAXVEX 20 //最大顶点个数设置为20 #define MAXSIZE 20 //设置队列的最大容量为20 #define ERROR 0 #define OK 1 bool Visited[MAXVEX]; //设置一个布尔变量，用于在两种遍历的时候标志顶点是否被访问过 typedef struct MGraph //无向图的数组表示法存储结构 { VertexType vexs[MAXVEX]; //顶点表 EdgeType arc[MAXVEX][MAXVEX]; //邻接矩阵 int vertexs_num; //顶点数 }MGraph; 创建无向图创建无向图所需要的信息是顶点信息和边关系 因为无向图的邻接矩阵是对称的，所以G.arc[i][j]=G.arc[j][i] void Create(MGraph& G) { //创建一个无向图 int i, j; cout cout cout if (G.arc[i][j] == 1 && !Visited[j] ) //如果两点之间有边并且第j+1个顶点没有被访问过 DFS(G, j); } } void DFSTraverse(MGraph G) { //深度优先遍历算法 int i; cout //初始化空队列 Q.base= (QElemType *)malloc(MAXSIZE *sizeof(QElemType)); if (Q.base == NULL) { cout //在队尾插入元素 if ((Q.rear + 1) % MAXSIZE == Q.front)//队列已满 return ERROR; Q.base[Q.rear] = e;//插入队尾 Q.rear = (Q.rear + 1) % MAXSIZE;//尾部指针后移，如果到最后则转到头部 return OK; } 元素出队 status pop(SqQueue &Q, QElemType & e) { //元素出队,并用e返回被删除的队头元素 if (Q.front == Q.rear)//队列空 return ERROR; e = Q.base[Q.front];//返回队头元素 Q.front = (Q.front + 1) % MAXSIZE;//队头指针后移，如到最后转到头部 return OK; } BFS void BFSTraverse(MGraph G) { //广度优先遍历算法 SqQueue Q; int i,j; QElemType k; int mark; //用于标记 cout Visited[i] = true; push(Q,G.vexs[i]); //该顶点入队 cout if (G.vexs[j] == k) mark = k; //将此时的队头元素标记 } for (j = 0; j Visited[j] = true; cout cout a; switch (a) { case 1: Create(G); break; case 2: Print(G); break; case 3: DFSTraverse(G); break; case 4: BFSTraverse(G); break; default: cout |
在树形结构中，数据元素之间有着很明显的层次关系，并且每一层的数据元素可能和下一层的多个元素相关，但是只能和上一层的一个元素相关。 这就和一对父母可以有多个孩子，但是一个孩子只能有一对亲生父母一样。 
但是实际上，在现实生活中，很多事物和人际关系都是十分复杂的，并非简单的一对一、一对多的关系。这个时候就可以用图这种数据结构来表示，在图的数据结构中，结点之间的关系可以是任意的，图中任意两个数据元素都是可能相关的。 
【本文地址】