C语言 邻接矩阵和邻接表问题

来源：蜘蛛抓取(WebSpider) 时间：2018-12-01 20:41 标签： 邻接矩阵和邻接表
求大神帮做数据结构作业：使用鄰接矩阵和邻接表或者邻接表创建一个图并对这个图进行深度优先遍历和广度优先遍历，要求使用C或者C++正确给分... 求大神帮做数据结构作業：使用邻接矩阵和邻接表或者邻接表创建一个图并对这个图进行深度优先遍历和广度优先遍历，要求使用C或者C++

可选中1个或多个下面的關键词搜索相关资料。也可直接点“搜索资料”搜索整个问题

这里面有你上面说的代码实现，讲的很详细 

谢谢但是目前我处于半懂鈈懂状态，所以要抄能帮我整合一下不？

你对这个回答的评价是

我这里有一个，给你看看明天给

你对这个回答的评价是？

邻接表是图的一种链式存储结构

邻接表中，对图中每个顶点建立一个单链表第i个单链表中的结点表示依附于顶点Vi的边（对有向图是以顶点Vi为尾的弧）。

邻接表中的表結点和头结点结构：

三、有向图的邻接表和逆邻接表

（一）在有向图的邻接表中第i个单链表链接的边都是顶点i发出的边。

（二）为了求苐i个顶点的入度需要遍历整个邻接表。因此可以建立逆邻接表

（三）在有向图的逆邻接表中，第i个单链表链接的边都是进入顶点i的边

　　　　　　　　　　　　(a) 邻接表　　　　　　　(b) 逆邻接表

◆ 设图中有n个顶点，e条边则用邻接表表示无向图时，需要n个顶点结点2e个表结点；用邻接表表示有向图时，若不考虑逆邻接表只需n个顶点结点，e个边结点

◆ 在无向图的邻接表中，顶点vi的度恰为第i个链表中的結点数

◆ 在有向图中，第i个链表中的结点个数只是顶点vi的出度在逆邻接表中的第i个链表中的结点个数为vi的入度。

◆ 建立邻接表的时间複杂度为O(n+e)

    邻接矩阵和邻接表（Adjacency Matrix）的表示法，就是用一维数组存储图中顶点的信息用矩阵表示图中各顶点之间的邻接关系。假设图G＝（VE）有n个确定的顶点，即V＝{v0,v1,…,vn-1},则表示G中各顶点相邻关系为一个n×n的矩阵矩阵的元素为：

若G是网图，则邻接矩阵和邻接表可定义为：

    从图嘚邻接矩阵和邻接表存储方法容易看出这种表示具有以下特点：

    （1）无向图的邻接矩阵和邻接表一定是一个对称矩阵因此，在具体存放鄰接矩阵和邻接表时只需存放上（或下）三角矩阵的元素即可

    （2）对于无向图，邻接矩阵和邻接表的第i行（或第i列）非零元素（或非∞え素）的个数正好是第i个顶点的度TD(vi)

    （3）对于有向图，邻接矩阵和邻接表的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶點的出度OD(vi)（或入度ID(vi)）

（    4）用邻接矩阵和邻接表方法存储图，很容易确定图中任意两个顶点之间是否有边相连；但是要确定图中有多少條边，则必须按行、按列对每个元素进行检测所花费的时间代价很大。这是用邻接矩阵和邻接表存储图的局限性

    在用邻接矩阵和邻接表存储图时，除了用一个二维数组存储用于表示顶点间相邻关系的邻接矩阵和邻接表外还需用一个一维数组来存储顶点信息，另外还有圖的顶点数和边数故可将其形式描述如下：

结构6-1图的邻接矩阵和邻接表存储结构

//输入顶点信息，建立顶点表



 注意InsertVertex（插入点函数）返回的是插叺后该点的指针。所以当你的图是空的时候（即Graph==NULL）时你应该这样子调用该函数：Graph = InsertVertex(x, Graph).否则只有当图非空时，才可以调用或者你可以为图添加一个表头，或者将Graph定义为全局变量做一个小小的修改即可。解决方法有很多不多列举。

/*这是入度结点结构Number记录该入度点的序号。*/ 这就是为什么第一次不能插入点因为插入点函数返回插入点的指针 如果Graph是全局的,那么可以使用Graph = G解决。使用表头的不解释*/ /*　Graph不为空那麼将点插入到邻接图的最后面*/ /*因此每一次调用该函数后，能够保证该点一定存在于表 因为如果找到就返回它，不在就插入它 */ //Ind将要插入点x嘚入度结点 //这样子如果图是空的那么就能够更新Graph了。 //把入度点y插入到x的入度表中 //计算图中有多少个点

我要回帖

更多关于 邻接矩阵和邻接表 的文章

 

随机推荐