数据结构：六图.ppt

6.1 图的定义与基本术语 6.2 图的存储结构 6.1 图的定义与基本术语 有向图 无向图 二、基本术语 顶点在图中的位置 基本操作 6.2 图的存储结构 一、图的邻接矩阵存储表示 网的邻接矩阵 邻接矩阵的C语言类型描述 创建邻接矩阵存储的有向网 二.图的邻接表存储表示 有向图的邻接表 有向图的逆邻接表 网的邻接表存储表示 邻接表存储结构C语言类型描述 邻接表存储的特点 三、有向图的十字链表存储表示 十字链表存储结构C语言类型描述 有向图的十字链表实例: 建立有向图十字链表算法 十字链表的特点 四、无向图的邻接多重表存储表示 邻接多重表存储结构C语言类型描述 无向图的邻接多重表实例 边(弧) 顶点 data farc adjv info nextarc 15 9 7 21 11 3 2 A B E C D 2 15 5 9 3 3 4 1 11 2 7 3 21 1 2 3 4 5 A B C D E ? ? 2 ? ? ? #define MAX_V 20 typedef enum{DG, DN, UDG, UDN} GraphKind; typedef struct ArcNode{ int adjvex; OtherInfo info; struct ArcNode *nextarc; } ArcNode; ? typedef struct VertexNode{ VertexData data; ArcNode *firstarc; } VertexNode; ? typedef struct{ VertexNode vertex[MAX_V]; int vexnum,arcnum; GraphKind kind; }AdjList; ●存储空间：对于有n个顶点，e条边的无向图而言，若采取邻接表作为存储结构，则需要n个表头结点和2e个表结点。 ●无向图的度：在无向图的邻接表中，顶点vi的度恰好就是第i个边链表上结点的个数。 ●有向图的度：在有向图中，第i个边链表上顶点的个数是顶点vi的出度。要想求得该顶点的入度，则必须遍历整个邻接表(在所有单链表中查找邻接点域的值为i的结点并计数求和),或用逆邻接表。 将有向图的邻接表和逆邻接表结合起来就可以得到十字链表，它是有向图的另一种链式存储结构。顶点和弧分别各用一种存储结构的结点表示。弧头相同的弧被链在同一链表上，弧尾相同的弧也被链在同一链表上，链表的头结点就是顶点结点。 类似于十字链表表示的稀疏邻接矩阵。 顶点信息数据 指向第一条入弧 指向第一条出弧 弧的结点结构 弧尾顶点序号 弧头顶点序号 弧信息 顶点的结点结构 指向弧头相同的下一条弧 指向弧尾相同的下一条弧 data firin firout tv hv hlink tlink info 弧的结点结构 顶点的结点结构 data firin firout tv hv hlink tlink info #define MAX_V 20 typedef enum{DG, DN, UDG, UDN} GraphKind; typedef struct ArcNode{ int tv, hv; struct ArcNode *hlink, *tlink; Infotype info; } ArcNode;? typedef struct VertexNode{ VertexData data; ArcNode *firin, *firout; } VertexNode; ? typedef struct{ VertexNode vertex[MAX_V]; int vexnum, arcnum; GraphKind kind; }AdjList; A B C D A B ∧ C D