计算机考研专业课复习科目包括数据结构、操作系统、计算机组成原理、计算机网络四门课程。其中数据结构这一科目兼具理论与实践，要求同学们在复习过程中不仅要对教材的基本概念进行记忆，同时还要结合知识点掌握相应的实际操作知识。为帮助同学们在计算机专业课复习上卓有成效，中公考研将为同学们整理全面的考点梳理，今天为大家带来的是数据结构的相关内容，请同学们适当参考，结合自身实际在全面复习的基础上进行重点理解记忆。

　　4.邻接多重表(无向图)

　　markivexjvexilinkjlinkinfo

　　边结点

　　datafirstedge

　　顶点结点

　　有向无环图(DAG)：是描述含有公共子式的表达式的有效工具。二叉树也能表示表达式，但是利用有向无环图可以实现对相同子式的共享，从而节省存储空间。

　　顶点的度：

　　无向图：某顶点V的度记为D(V)，代表与V相关联的边的条数

　　有向图：顶点V的度D(V)=ID(V)+OD(V)

　　强连通分量:在有向图中，若图中任意两顶点间都存在路径，则称其是强连通图。图中极大 强连通子图称之为强连通分量

　　“极大”在这里指的是：往一个连通分量中再加入顶点和边，就构不成原图中的一个 连通子图，即连通分量是一个最大集的连通子图。有向图的连通就是指该有向图是强连通的。

　　遍历图的过程实质上是_对每个顶点查找其邻接点的过程___ 其耗费的时间主要取决于采用的存储结构。当用邻接矩阵存储图时，查找每个顶点的邻接点所需的时间O( )，其中n是图中顶点数。而当用邻接表存储图时，找邻接点的所需时间为O(e)，其中e为图中边的个数或有向弧的个数，由此，当以邻接表作为存储结构时，深度优先搜索遍历图的时间复杂度O(n+e).

　　广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者的不同之处仅在于对结点访问的顺序不同。也就是说他们的时间复杂度都取决于说采用的存储结构，当用邻接矩阵存储时，复杂度为O( )，当用邻接表存储时，时间复杂度为O(n+e).

　　建图的算法：(邻接表是常考的，邻接矩阵简单，十字链表和 多重表和建邻接表十分的相似)

　　void CreatGraph (AdjList &g) //建立有n个顶点和m 条边的无向图的邻接表存储结构

　　{ int n,m;

　　scanf("%d%d",&n,&m);//输入顶点数和边数

　　for (i =1,i<=n;i++)//输入顶点信息,建立顶点向量

　　{ scanf(&g[i].vertex);

　　g[i].firstarc=null;

　　}

　　for (k=1;k<=m;k++)//输入边信息

　　{ scanf(&v1,&v2);//输入两个顶点

　　i= LocateVertex (g,v1); j=GraphLocateVertex (g,v2); //顶点定位

　　p=(ArcNode *)malloc(sizeof(ArcNode));//申请边结点

　　p->adjvex=j;

　　p->next=g[i].firstarc; g[i].firstarc=p;//将边结点链入出边链表的头部

　　p=(ArcNode *)malloc(sizeof(ArcNode)); //因为是无向图所以要在另外一个

　　p->adjvex=i;

　　p->next=g[j].firstarc; g[j].frstarc=p;// 顶点的出边表中插入该结点

　　}

　　}//算法CreatGraph结束