图也是数据结构中很重要的一个内容，所以我同意是开一篇文章来作为图的目录
图的概念及专业术语
图分为两种：有向图和无向图
下面是有关图的基本术语：
图的存储结构
图的两种常用存储结构：零阶矩阵和邻接表
零阶矩阵适合稠密图，邻接表则适合稀疏图
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
//图的两种存储结构 #define INF 32767 //定义∞ #define MAXV 100 //最大顶点个数 typedef char InfoType; //以下定义邻接矩阵类型 typedef struct { int no; //顶点编号 InfoType info; //顶点其他信息 } VertexType; //顶点类型 typedef struct { int edges[MAXV][MAXV]; //邻接矩阵数组 int n,e; //顶点数，边数 VertexType vexs[MAXV]; //存放顶点信息 } MatGraph; //完整的图邻接矩阵类型 //以下定义邻接表类型 typedef struct ANode { int adjvex; //该边的邻接点编号 struct ANode *nextarc; //指向下一条边的指针 int weight; //该边的相关信息，如权值（用整型表示） } ArcNode; //边结点类型 typedef struct Vnode { InfoType info; //顶点其他信息 int count; //存放顶点入度,仅仅用于拓扑排序 ArcNode *firstarc; //指向第一条边 } VNode; //邻接表头结点类型 typedef struct { VNode adjlist[MAXV]; //邻接表头结点数组 int n,e; //图中顶点数n和边数e } AdjGraph; //完整的图邻接表类型 |
图的基本运算算法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
//图的基本运算算法 #include <stdio.h> #include <malloc.h> #include "graph.h" //------------------------------------------------------------ //----邻接矩阵的基本运算算法---------------------------------- //------------------------------------------------------------ void CreateMat(MatGraph &g,int A[MAXV][MAXV],int n,int e) //创建图的邻接矩阵 { int i,j; g.n=n; g.e=e; for (i=0;i<g.n;i++) for (j=0;j<g.n;j++) g.edges[i][j]=A[i][j]; } void DispMat(MatGraph g) //输出邻接矩阵g { int i,j; for (i=0;i<g.n;i++) { for (j=0;j<g.n;j++) if (g.edges[i][j]!=INF) printf("%4d",g.edges[i][j]); else printf("%4s","∞"); printf("\n"); } } //------------------------------------------------------------ //------------------------------------------------------------ //----邻接表的基本运算算法------------------------------------ //------------------------------------------------------------ void CreateAdj(AdjGraph *&G,int A[MAXV][MAXV],int n,int e) //创建图的邻接表 { int i,j; ArcNode *p; G=(AdjGraph *)malloc(sizeof(AdjGraph)); for (i=0;i<n;i++) //给邻接表中所有头结点的指针域置初值 G->adjlist[i].firstarc=NULL; for (i=0;i<n;i++) //检查邻接矩阵中每个元素 for (j=n-1;j>=0;j--) if (A[i][j]!=0 && A[i][j]!=INF) //存在一条边 { p=(ArcNode *)malloc(sizeof(ArcNode)); //创建一个结点p p->adjvex=j; p->weight=A[i][j]; p->nextarc=G->adjlist[i].firstarc; //采用头插法插入结点p G->adjlist[i].firstarc=p; } G->n=n; G->e=n; } void DispAdj(AdjGraph *G) //输出邻接表G { int i; ArcNode *p; for (i=0;i<G->n;i++) { p=G->adjlist[i].firstarc; printf("%3d: ",i); while (p!=NULL) { printf("%3d[%d]→",p->adjvex,p->weight); p=p->nextarc; } printf("∧\n"); } } void DestroyAdj(AdjGraph *&G) //销毁图的邻接表 { int i; ArcNode *pre,*p; for (i=0;i<G->n;i++) //扫描所有的单链表 { pre=G->adjlist[i].firstarc; //p指向第i个单链表的首结点 if (pre!=NULL) { p=pre->nextarc; while (p!=NULL) //释放第i个单链表的所有边结点 { free(pre); pre=p; p=p->nextarc; } free(pre); } } free(G); //释放头结点数组 } //------------------------------------------------------------ |
另外，还有十字链表和邻接多重表等多种存储结构，精力有限，暂不学习
