【大话数据结构C语言】38 图的存储结构（邻接矩阵）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【大话数据结构C语言】38 图的存储结构（邻接矩阵），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2109字，纯文字阅读大概需要4分钟。

内容图文

我的公众号是【CodeAllen】，程序员技术交流①群：736386324,转载请注明出处

上一篇说的临接矩阵是不错的图存储结构，但是对于边数相对顶点较少的图，这种结构是存在对存储空间极大浪费的

因此可以考虑另外一种存储结构：比如把数组和链表结合一起来存储

 

临接表无向图的处理方法：

1.图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便

2.图中每个顶点Vi的所有邻接点构成一个线性表，由于邻接点的个数不确定，所以我们选择用单链表来存储

 

临接表有向图的处理方法：

以把顶点当弧尾建立的临接表，这样很容易可以得到每个顶点的出度

 

临接表网的处理方法：

对于带权值的网图，可以在边表结点定义中在增加一个数据域来存储权值即可

 

代码实现：

#define?MAXVEX?100

typedef?struct?EdgeNode?????????//?边表结点
{
????int?adjvex;?????????????????//?邻接点域，存储该顶点对应的下标
????int?weight;?????????????????//?用于存储权值，对于非网图可以不需要
????struct?EdgeNode?*next;??????//?链域，指向下一个邻接点
}?EdgeNode;

typedef?struct?VertexNode???????//?顶点表结点
{
????char?data;??????????????????//?顶点域，存储顶点信息
????EdgeNode?*firstEdge;????????//?边表头指针
}?VertexNode,?AdjList[MAXVEX];

typedef?struct
{
????AdjList?adjList;
????int?numVertexes,?numEdges;??//?图中当前顶点数和边数
}?GraphAdjList;

//?建立图的邻接表结构
void?CreateALGraph(GraphAdjList?*G)
{
????int?i,?j,?k;
????EdgeNode?*e;

????printf("请输入顶点数和边数：\n");
????scanf("%d?%d",?&G->numVertexes,?&G->numEdges);

????//?读取顶点信息，建立顶点表
????for(?i=0;?i?<?G->numVertexes;?i++?)
????{
????????scanf("%c",?&G->adjList[i].data);
????????G->adjList[i].firstEdge?=?NULL;?????//?初始化置为空表
????}

????for(?k=0;?k?<?G->numEdges;?k++?)
????{
????????printf("请输入边(Vi,Vj)上的顶点序号：\n");
????????scanf("%d?%d",?&i,?&j);

????????e?=?(EdgeNode?*)malloc(sizeof(EdgeNode));
????????e->adjvex?=?j;??????????????????????//?邻接序号为j
????????e->next?=?G->adjList[i].firstEdge;
????????G->adjList[i].firstEdge?=?e;

????????e?=?(EdgeNode?*)malloc(sizeof(EdgeNode));
????????e->adjvex?=?i;??????????????????????//?邻接序号为i
????????e->next?=?G->adjList[j].firstEdge;
????????G->adjList[j].firstEdge?=?e;
????}
}

 

 

 

 

 

 

 

 

 

 

 

内容总结

以上是互联网集市为您收集整理的【大话数据结构C语言】38 图的存储结构（邻接矩阵）全部内容，希望文章能够帮你解决【大话数据结构C语言】38 图的存储结构（邻接矩阵）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---