数据结构 图

图定义存储结构邻接矩阵邻接表 图的遍历深度优先搜索广度优先搜索

图定义

图是一个二元组<V,E>。其中V是顶点的有穷非空集合，E是两个顶点之间关系的集合。

如果<v，w>属于E，则<v,w>表示从v到w的一条弧，v为弧尾，w为弧头，此时的图称为有向图；如果<v，w>属于E必有<w，v>属于E，则为无向图。完全图 ① 具有n(n-1)条弧的有向图为有向完全图。 ② 具有n(n-1)/2条边的无向图称为无向完全图。顶点的度/入度/出度 ① 以顶点v为弧头的弧的数目称作顶点v的入度; ② 以顶点v为弧尾的弧的数目称作顶点v的出度; ③ 与顶点v相关的边的条数称作顶点v的度;路径长度 路径上边或弧的数目简单路径 顶点没有重复出现的路径;

存储结构

邻接矩阵

表示方法 假设图中有n个结点，其值分别为d1，d2，d3… 用自然数将他们依次编号为1，2，3…定义一个二位数组矩阵存放图中各结点的邻接信息； 邻接矩阵的每一个元素定义如下： 特点 ① 无向图的邻接矩阵是对称的； ② 可以很方便求得各点的度。 邻接矩阵表示法类型定义： //最大顶点个数 #define max_size 30 typedef struct graph{ ElemType data[max_size][max_size]; int n; }graph;

邻接表

表示方法 用一个顺序存储空间来存储各节点的信息； 对于图中每一个结点dn构造一个单链表。单链表的头指针为顺序空间中对应存储结点的指针域。邻接表类型定义 //最大定点数 #define max_num 30 //边结点 typedef struct edgenode{ int adjvex; struct edgenode *nextarc; }edgenode; //顶点结构 typedef struct vextexnode{ int adjvex; edgenode *firstarc; }vextexnode,AdjList[max_num];

图的遍历

从图的某一顶点出发访遍图中所有顶点，且使每一顶点仅被访问一次，这一过程称为图的遍历。

深度优先搜索

树的先根遍历的扩展

广度优先搜索

树的层次遍历的扩展