两种存储结构比较线性表.ppt

文档介绍：该【两种存储结构比较线性表 】是由【hezhihe】上传分享，文档一共【29】页，该文档可以免费在线阅读，需要了解更多关于【两种存储结构比较线性表 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。§ 图的定义和术语
一、图
多对多的关系，非线性结构
G=(V,E)
V(G)：顶点的非空有限集合
E(G)：图中边的有限集合
二、几个术语
有向图：弧（有向边），
<x,y>:xy,x邻接到y，y邻接自x
<x,y> 与x、y相关联
<x,y> ≠ <y,x>
无向图：边（无向边），
(x,y):xy,x与y相邻接
(x,y) 与x、y相关联
(x,y) = (y,x)
有向完全图：每个顶点都与其它任意顶点有弧。
共 条边。
二、几个术语2
n*(n-1)
无向完全图：每个顶点都与其它任意顶点有边。
共 条边。
n*(n-1)/2
子图：V(B)属于V(A)，且E(B)属于E(A)，则B是A的子图。
（B是A中的一部分）
顶点的度：与顶点相关联的边的数目（出度、入度）。
有向图中度＝出度＋入度
设vi的度为di，边数e＝1/2∑di（1<i<n）
路径：vp到vq经过的顶点序列，
经过的边的数目称为路径长度。
回路：起始点和终止点是同一顶点的路径。
简单路径（简单回路）：顶点不重复。
二、几个术语3
连通图：无向图中任意两个顶点都是连通的。
强连通图：有向图中任意两个顶点都是连通的。
连通分量＝极大连通子图
网络（带权图）：边上附加数作为权（代价）。
（连通图的）生成树：极小连通子图。
问题：1、n个顶点的连通图至少 条边。
2、n个顶点的强连通图至少 条边。
二、几个术语4
n-1
n
§ 图的存储
一、邻接矩阵：用二维数组表示顶点的邻接关系
1、n顶点用n阶方阵
A[ i ][ j ] =
1（i与j相邻接）
0（i与j 无边）
2、邻接矩阵特点
① 无向图邻接矩阵对称，有向图不对称
② 无向图第i行(列)非零元素个数即为结点i的度
有向图第i行(列)非零元素个数即为结点i的出(入)度
③ 容易确认任两点之间是否有边，但扫描边数代价大
（对每个结点进行检测）
3、邻接矩阵建立图
main()
{ int i,j,n=5,adj[5][5],v1,v2;
for (i=0;i<n;i++)
for (j=0;j<n;j++) adj[i][j]=0;
scanf(“%d,%d”,&v1,&v2);
while (v1!=0 || v2!=0)
{ adj[v1][v2]=1; adj[v2][v1]=1;
scanf(“%d,%d”,&v1,&v2);
}
} 时间复杂度：O（n2+e）
二、邻接表
例子：
data
指向下一个邻接点
特点：① 每个顶点对应一个单链表（存储邻接点）
② 无向图n个顶点，e条边需n个表头结点和2e个边结点
③ 顶点对应的单链表长度为该顶点的度
（有向图则为出度）
问题：如何求有向图顶点的入度？
解：可建立有向图的逆邻接表
例子：
① 正邻接表：方便求顶点的出度
② 逆邻接表：方便求顶点的入度