数据结构之图
2016-03-08 11:16:29 12 举报AI智能生成
图是一种特殊的数据结构，由顶点（或称节点）和边组成。图中的每个顶点可以与其他一个或多个顶点相连，相连的部分称为边。边的连接关系可以是无向的，也可以是有向的。图的应用非常广泛，例如社交网络中的人与人的关系、互联网中的网页链接关系等都可以用图来表示。常用的图的存储结构有邻接矩阵和邻接表等。在图的算法中，最短路径问题是最常见的问题之一，常用的算法有Dijkstra算法和Floyd-Warshall算法等。除此之外，还有最小生成树、拓扑排序、网络流等问题也是图论的重要研究内容。
作者其他创作
大纲/内容
图的定义
顶点（Vertex）
1、图中的数据元素
2、在图结构中，不允许没有顶点，即顶点集合V为有穷非空
各种图定义
无向图（Undirected graphs）
定义：任意两个顶点之间的边都是无向边
无向边:表示为(A,B)
无向完全图：任意两个顶点之间都存在边
有向图（Directed graphs）
定义：任意两个顶点之间的边都是有向边
有向边（弧）:，有弧头弧尾之分
有向完全图：任意两个顶点之间都存在方向互为相反的两条弧
网（Network）
定义：带权的图
权（Weight）：与图的边或弧相关的数
顶点与边的关系
入度（InDegree）：以顶点v为头的弧的数目，记为ID(v)
度（Degree）：和顶点v相关联的边的数目，记为TD(v)
出度（OutDegree）：以顶点v为尾的弧的数目，记为OD(v)
路径的长度：路径上的边或弧的数目
回路/环（Cycle）：第一个顶点到最后一个顶点相同的路径
简单路径：序列中顶点不重复出现的路径
简单回路或简单环：除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路
连通图（Connected Graph）
定义：针对无向图，任意两个顶点都是连同的
连通分量：无向图中的极大连通子图
1、要是子图
2、子图要是连通的
3、连通子图含有极大顶点数
4、具有极大顶点数的连通子图包含依附于这些顶点的所有边
强连通图（Strongly Connected Graph）
定义：针对有向图，V1到V2和V2到V1都存在路径
强连通分量：有向图中的极大强连通子图
生成树：无向图中连通且n个顶点n-1条边
有向树：有向图中一顶点入度为0，其余项点入度为1
生成森林：一个有向图由若干棵有向树构成生成森林
图的存储结构
邻接矩阵
邻接表（Adjacency List）
定义：图的一种顺序存储与链式存储相结合的存储方法
顶点表：由顶点域（vertex）和指向第一条领接边的指针域（firstedge）构成
边表：由邻接点域（adjvex）和指向下一条邻接边的指针域（next）构成
出边表：有向图中，顶点Vi作为弧尾的边表
扩展：对于带权值的网图，可以在边表结点定义中在增加一个weight的数据域，存储权值信息
十字链表（Orthogonal List）
邻接多重表
边集数组
适用于对边进行处理的操作
应用：克鲁斯卡尔算法
图的遍历
深度优先遍历（Depth First Search）
广度优先遍历（Breadth First Search）
0 条评论
下一页
