数据结构 |
您所在的位置：网站首页 › 线性结构中数据元素之间的关系是 › 数据结构 |
数据结构
|
数据结构—图
图(Graph)是一种比线性表和树更为复杂的数据结构。 线性结构：是研究数据元素之间的一对一关系。在这种结构中，除第一个和最后一个元素外，任何一个元素都有唯一的一个直接前驱和直接后继。 树结构：是研究数据元素之间的一对多的关系。在这种结构中，每个元素对下(层)可以有0个或多个元素相联系，对上(层)只有唯一的一个元素相关，数据元素之间有明显的层次关系。 图结构：是研究数据元素之间的多对多的关系。在这种结构中，任意两个元素之间可能存在关系。即结点之间的关系可以是任意的，图中任意元素之间都可能相关。 （一）图的定义和术语 一个图(G)是由二个集合V和E构成的二元组，记为G=(V,E) 。其中：V是图中顶点(Vertex)的非空有限集合；E是图中边的有限集合。从数据结构的逻辑关系角度来看，图中任何一个顶点都有可能与图中其他顶点有关系，而图中所有定点都有可能与某一顶点有关系。将顶点集合为空的图称为空图。其形式化定义为：
G=(V ，E) V={v|vÎdata object} E={| v,wÎV∧p(v,w)} P(v,w)表示从顶点v到顶点w有一条直接通路。
弧(Arc) ：表示两个顶点v和w之间存在一个关系，用顶点偶对表示。通常根据图的顶点偶对将图分为有向图和无向图。 有向图(Digraph)：若图中每条边都是有方向的（图G的关系集合E(G)中，顶点偶对的v和w之间是有序的），称图G是有向图。在有向图中，若ÎE(G) ，表示从顶点v到顶点w有一条弧。 其中：v称为弧尾(tail)或始点(initial node)，w称为弧头(head)或终点(terminal node) 。
无向图(Undigraph)：若图中每条边都是无方向的（图G的关系集合E(G)中，顶点偶对的v和w之间是无序的）称图G是无向图。在无向图中，若"ÎE(G) ，有ÎE(G) ，即E(G)是对称，则用无序对(v,w) 表示v和w之间的一条边(Edge)，因此(v,w) 和(w,v)代表的是同一条边。
例1：设有有向图G1和无向图G2，形式化定义分别是： G1=(V1 ，E1) V1={a,b,c,d,e} E1={,, ,, ,,,} G2=(V2 ，E2) V2={a,b,c,d} E2={(a,b), (a,c), (a,d), (b,d), (b,c), (c,d)} 它们所对应的图如图所示。
完全无向图：对于无向图，若图中顶点数为n ，用e表示边的数目，则e Î[0，n(n-1)/2] 。具有n(n-1)/2条边的无向图称为完全无向图。完全无向图另外的定义是：对于无向图G=(V，E)，若"vi，vj ÎV ，当vi≠vj时，有(vi ,vj)ÎE，即图中任意两个不同的顶点间都有一条无向边，这样的无向图称为完全无向图。
完全有向图：对于有向图，若图中顶点数为n ，用e表示弧的数目，则eÎ[0，n(n-1)] 。具有n(n-1)条边的有向图称为完全有向图.完全有向图另外的定义是：对于有向图G=(V，E)，若"vi，vjÎV，当vi≠vj，有ÎE∧ÎE ，即图中任意两个不同的顶点间都有一条弧，这样的有向图称为完全有向图。
有很少边或弧的图（enumVertexes; i++) { if(g->vexs[i] == ch) { break; } } if(i >= g->numVertexes) { return -1; } return i; } //建立一个无向网图的邻接矩阵表示 void CreateGraph(Graph *g) { int i, j, k, w; printf("输入顶点数和边数:\n"); scanf("%d,%d", &(g->numVertexes), &(g->numEdges)); #ifdef DEBUG printf("%d %d\n", g->numVertexes, g->numEdges); #endif for(i = 0; i < g->numVertexes; i++) { g->vexs[i] = getchar(); while(g->vexs[i] == '\n') { g->vexs[i] = getchar(); } } #ifdef DEBUG for(i = 0; i < g->numVertexes; i++) { printf("%c ", g->vexs[i]); } printf("\n"); #endif for(i = 0; i < g->numEdges; i++) { for(j = 0; j < g->numEdges; j++) { g->arc[i][j] = INFINITY; //邻接矩阵初始化 } } for(k = 0; k < g->numEdges; k++) { char p, q; printf("输入边(vi,vj)上的下标i，下标j和权值:\n"); p = getchar(); while(p == '\n') { p = getchar(); } q = getchar(); while(q == '\n') { q = getchar(); } scanf("%d", &w); int m = -1; int n = -1; m = locates(g, p); n = locates(g, q); if(n == -1 || m == -1) { fprintf(stderr, "there is no this vertex.\n"); return; } //getchar(); g->arc[m][n] = w; g->arc[n][m] = g->arc[m][n]; //因为是无向图，矩阵对称 } } //打印图 void printGraph(Graph g) { int i, j; for(i = 0; i < g.numVertexes; i++) { for(j = 0; j < g.numVertexes; j++) { printf("%d ", g.arc[i][j]); } printf("\n"); } } int main(int argc, char **argv) { Graph g; //邻接矩阵创建图 CreateGraph(&g); printGraph(g); return 0; } 2.邻接链表表示法邻接矩阵是不错的一种图存储结构，但是，对于边数相对顶点较少的图，这种结构存在对存储空间的极大浪费。因此，找到一种数组与链表相结合的存储方法称为邻接表。 邻接表的处理方法是这样的： （1）图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过，数组可以较容易的读取顶点的信息，更加方便。 （2）图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以，用单链表存储，无向图称为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表。 例如，下图就是一个无向图的邻接表的结构。 从图中可以看出，顶点表的各个结点由data和firstedge两个域表示，data是数据域，存储顶点的信息，firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，next则存储指向边表中下一个结点的指针。 对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可。如下图所示。
对于邻接表结构，图的建立代码如下。 /* 邻接表表示的图结构 */ #include #include #define DEBUG #define MAXVEX 1000 //最大顶点数 typedef char VertexType; //顶点类型应由用户定义 typedef int EdgeType; //边上的权值类型应由用户定义 typedef struct EdgeNode //边表结点 { int adjvex; //邻接点域，存储该顶点对应的下标 EdgeType weigth; //用于存储权值，对于非网图可以不需要 struct EdgeNode *next; //链域，指向下一个邻接点 }EdgeNode; typedef struct VertexNode //顶点表结构 { VertexType data; //顶点域，存储顶点信息 EdgeNode *firstedge; //边表头指针 }VertexNode, AdjList[MAXVEX]; typedef struct { AdjList adjList; int numVertexes, numEdges; //图中当前顶点数和边数 }GraphList; int Locate(GraphList *g, char ch) { int i; for(i = 0; i < MAXVEX; i++) { if(ch == g->adjList[i].data) { break; } } if(i >= MAXVEX) { fprintf(stderr,"there is no vertex.\n"); return -1; } return i; } //建立图的邻接表结构 void CreateGraph(GraphList *g) { int i, j, k; EdgeNode *e; EdgeNode *f; printf("输入顶点数和边数:\n"); scanf("%d,%d", &g->numVertexes, &g->numEdges); #ifdef DEBUG printf("%d,%d\n", g->numVertexes, g->numEdges); #endif for(i = 0; i < g->numVertexes; i++) { printf("请输入顶点%d:\n", i); g->adjList[i].data = getchar(); //输入顶点信息 g->adjList[i].firstedge = NULL; //将边表置为空表 while(g->adjList[i].data == '\n') { g->adjList[i].data = getchar(); } } //建立边表 for(k = 0; k < g->numEdges; k++) { printf("输入边(vi,vj)上的顶点序号:\n"); char p, q; p = getchar(); while(p == '\n') { p = getchar(); } q = getchar(); while(q == '\n') { q = getchar(); } int m, n; m = Locate(g, p); n = Locate(g, q); if(m == -1 || n == -1) { return; } #ifdef DEBUG printf("p = %c\n", p); printf("q = %c\n", q); printf("m = %d\n", m); printf("n = %d\n", n); #endif //向内存申请空间，生成边表结点 e = (EdgeNode *)malloc(sizeof(EdgeNode)); if(e == NULL) { fprintf(stderr, "malloc() error.\n"); return; } //邻接序号为j e->adjvex = n; //将e指针指向当前顶点指向的结构 e->next = g->adjList[m].firstedge; //将当前顶点的指针指向e g->adjList[m].firstedge = e; f = (EdgeNode *)malloc(sizeof(EdgeNode)); if(f == NULL) { fprintf(stderr, "malloc() error.\n"); return; } f->adjvex = m; f->next = g->adjList[n].firstedge; g->adjList[n].firstedge = f; } } void printGraph(GraphList *g) { int i = 0; #ifdef DEBUG printf("printGraph() start.\n"); #endif while(g->adjList[i].firstedge != NULL && i < MAXVEX) { printf("顶点:%c ", g->adjList[i].data); EdgeNode *e = NULL; e = g->adjList[i].firstedge; while(e != NULL) { printf("%d ", e->adjvex); e = e->next; } i++; printf("\n"); } } int main(int argc, char **argv) { GraphList g; CreateGraph(&g); printGraph(&g); return 0; } 3.十字链表 对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才知道，反之，逆邻接表解决了入度却不了解出度 情况。下面介绍的这种有向图的存储方法： 十字链表，就是把邻接表和逆邻接表结合起来的。 重新定义顶点表结点结构，如下所示。 
重点需要解释虚线箭头的含义。它其实就是此图的逆邻接表的表示。对于v0来说，它有两个顶点v1和v2的入边。因此的firstin指向顶点v1的边表结点中headvex为0的结点，如上图圆圈1。接着由入边结点的headlink指向下一个入边顶点v2，如上图圆圈2。对于顶点v1，它有一个入边顶点v2，所以它的firstin指向顶点v2的边表结点中headvex为1的结点，如上图圆圈3。
十字链表的好处就是因为把邻接表和逆邻接表整合在一起，这样既容易找到以v为尾的弧，也容易找到以v为头的弧，因而比较容易求得顶点的出度和入度。
而且除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同的，因此，在有向图应用中，十字链表是非常好的数据结构模型。
这里就介绍以上三种存储结构，除了第三种存储结构外，其他的两种存储结构比较简单。
（三）、图的遍历
图的遍历和树的遍历类似，希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫图的遍历。 对于图的遍历来说，如何避免因回路陷入死循环，就需要科学地设计遍历方案，通过有两种遍历次序方案：深度优先遍历和广度优先遍历。
深度优先： 1．首先访问出发顶点V 2. 依次从V出发搜索V的每个邻接点W; 3. 若W未访问过，则从该点出发继续深度优先遍历；它类似于树的前序遍历。 广度优先： 1．首先访问出发顶点V 2．然后访问与顶点V邻接的全部未访问顶点w、X、Y… 3．然后再依次访问W、X、Y…邻接的未访问的顶点； 例如 #define MAXVEX 100 //最大顶点数 typedef int Boolean; //Boolean 是布尔类型，其值是TRUE 或FALSE Boolean visited[MAXVEX]; //访问标志数组 #define TRUE 1 #define FALSE 0 //邻接矩阵的深度优先递归算法 void DFS(Graph g, int i) { int j; visited[i] = TRUE; printf("%c ", g.vexs[i]); //打印顶点，也可以其他操作 for(j = 0; j < g.numVertexes; j++) { if(g.arc[i][j] == 1 && !visited[j]) { DFS(g, j); //对为访问的邻接顶点递归调用 } } } //邻接矩阵的深度遍历操作 void DFSTraverse(Graph g) { int i; for(i = 0; i < g.numVertexes; i++) { visited[i] = FALSE; //初始化所有顶点状态都是未访问过状态 } for(i = 0; i < g.numVertexes; i++) { if(!visited[i]) //对未访问的顶点调用DFS，若是连通图，只会执行一次 { DFS(g,i); } } } 如果使用的是邻接表存储结构，其DFSTraverse函数的代码几乎是相同的，只是在递归函数中因为将数组换成了链表而有不同，代码如下。 //邻接表的深度递归算法 void DFS(GraphList g, int i) { EdgeNode *p; visited[i] = TRUE; printf("%c ", g->adjList[i].data); //打印顶点，也可以其他操作 p = g->adjList[i].firstedge; while(p) { if(!visited[p->adjvex]) { DFS(g, p->adjvex); //对访问的邻接顶点递归调用 } p = p->next; } } //邻接表的深度遍历操作 void DFSTraverse(GraphList g) { int i; for(i = 0; i < g.numVertexes; i++) { visited[i] = FALSE; } for(i = 0; i < g.numVertexes; i++) { if(!visited[i]) { DFS(g, i); } } } 例如 
的拓扑排序为：02143567或01243657或02143657或01243567
对比两个不同的存储结构的深度优先遍历算法，对于n个顶点e条边的图来说，邻接矩阵由于是二维数组，要查找某个顶点的邻接点需要访问矩阵中的所有元素，因为需要O(n2)的时间。而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，所以是O(n+e)。显然对于点多边少的稀疏图来说，邻接表结构使得算法在时间效率上大大提高。 3.2 广度优先遍历广度优先遍历，又称为广度优先搜索，简称BFS。图的广度优先遍历就类似于树的层序遍历了。 邻接矩阵做存储结构时，广度优先搜索的代码如下。 //邻接矩阵的广度遍历算法 void BFSTraverse(Graph g) { int i, j; Queue q; for(i = 0; i < g.numVertexes; i++) { visited[i] = FALSE; } InitQueue(&q); for(i = 0; i < g.numVertexes; i++)//对每个顶点做循环 { if(!visited[i]) //若是未访问过 { visited[i] = TRUE; printf("%c ", g.vexs[i]); //打印结点，也可以其他操作 EnQueue(&q, i); //将此结点入队列 while(!QueueEmpty(q)) //将队中元素出队列，赋值给 { int m; DeQueue(&q, &m); for(j = 0; j < g.numVertexes; j++) { //判断其他顶点若与当前顶点存在边且未访问过 if(g.arc[m][j] == 1 && !visited[j]) { visited[j] = TRUE; printf("%c ", g.vexs[j]); EnQueue(&q, j); } } } } } 对于邻接表的广度优先遍历，代码与邻接矩阵差异不大， 代码如下 。 //邻接表的广度遍历算法 void BFSTraverse(GraphList g) { int i; EdgeNode *p; Queue q; for(i = 0; i < g.numVertexes; i++) { visited[i] = FALSE; } InitQueue(&q); for(i = 0; i < g.numVertexes; i++) { if(!visited[i]) { visited[i] = TRUE; printf("%c ", g.adjList[i].data); //打印顶点，也可以其他操作 EnQueue(&q, i); while(!QueueEmpty(q)) { int m; DeQueue(&q, &m); p = g.adjList[m].firstedge; 找到当前顶点边表链表头指针 while(p) { if(!visited[p->adjvex]) { visited[p->adjvex] = TRUE; printf("%c ", g.adjList[p->adjvex].data); EnQueue(&q, p->adjvex); } p = p->next; } } } } 对比图的深度优先遍历与广度优先遍历算法，会发现，它们在时间复杂度上是一样的，不同之处仅仅在于对顶点的访问顺序不同。可见两者在全图遍历上是没有优劣之分的，只是不同的情况选择不同的算法。 最小生成树 包含图所有顶点的树，成为图的生成树，各边权值之和最小的树成为最小生成树。 普里姆算法： 1. 定义出发点为一个集合 2. 其它点为另外一个集合 3. 找到顶点和其它点的距离，不可到达为无穷大 4. 每确定一个点，则把这个点当做出发点集合中的点，从此点开始再次循环规则 克鲁斯卡尔算法： 1. 先确定各个点之间的距离 2. 画出各个点 3. 距离从小到大排序，依次加入画的顶点中（但是避免形成回路，如果形成回路，则忽略此距离），直到各个点之间可以连通 拓扑排序 用有向边表示各顶点活动开始的先后顺序，这些顶点组成的网络成为AOV网络。对一个有向无环图的顶点排成一个线性序列，使得有向边起点排在该有向边终点前的序列称之为拓扑序列。拓扑排序不一定唯一。 1. 找到入度为0的点，作为起点 2. 起点完成后，删除该起点的出度 3. 在剩余的aov网络中重复此过程 关键路径 AOV网络中，如果边上的权表示完成该活动所需的时间，则称这样的AOV为AOE网络。其中关键路径是最长的一条路径。如下：
|
其中firstin表示入边表头指针，指向该顶点的入边表中第一个结点，firstout表示出边表头指针，指向该顶点的出边表中的第一个结点。 重新定义边表结构，如下所示。 
其中，tailvex是指弧起点在顶点表的下表，headvex是指弧终点在顶点表的下标，headlink是指入边表指针域，指向终点相同的下一条边，taillink是指边表指针域，指向起点相同的下一条边。如果是网，还可以增加一个weight域来存储权值。 比如下图，顶点依然是存入一个一维数组，实线箭头指针的图示完全与邻接表相同。就以顶点v0来说，firstout指向的是出边表中的第一个结点v3。所以，v0边表结点hearvex = 3，而tailvex其实就是当前顶点v0的下标0，由于v0只有一个出边顶点，所有headlink和taillink都是空的。 
的深度优先遍历为：V1 V2 V3 V4 V5 V6；广度优先遍历为：V1 V2 V5 V3 V6 V4。
的关键路径为V1--V2--Vk或V1--V4--Vk。 【本文地址】
今日新闻 |
推荐新闻 |