图(Graph)

• 顶点(Vertex)：图中的数据元素
• 弧(Arc)：<v, w>表示从v到w的一条弧，v称为弧尾(Tail)或初始点，w称为弧头(Head)或终端点，此时的图称为有向图
• 无序对 (v, w)，表示v和w之间的一条边(Edge)，此时的图称为无向图

• 有n(n-1)/2条边的无向图称为无向完全图
• 有n(n-1)条弧的有向图称为有向完全图
• 稀疏图：有很少的边或弧，反之为稠密图
• 权(weight)：与图的边或弧相关的数
• 带权的图通常称为网(network)
• 子图
• 邻接点
• 顶点v的度：是和v相关联的边的数目
• v的入度：以v为头的弧的数目
• v的出度：以v为尾的弧的数目
• 路径：相邻顶点序偶所构成的序列
• 简单路径：顶点不重复出现的路径
• 回路或环(cycle)：第一个顶点和最后一个顶点相同
• 连通图：无向图中任意两个顶点都是连通的
• 连通分量：无向图中的极大连通子图
• 强连通图：有向图中，对于每一对顶点i和j，从i到j和从j到i都有路径
• 强连通分量：极大强连通子图

图的存储结构

• 邻接矩阵

  图的顺序存储结构

  typedef struct
  {
      int no;		//顶点标号
      char info;		//顶点其他信息，可以省略
  }VertexType;	//顶点类型
  
  typedef struct		//图的定义
  {
  	int edges[maxSize][maxSize];
      //邻接矩阵定义，如果是有权图，int可改为float
      int n,e;	//分别为顶点数和边数
      VertexType vex[maxSize];	//存放结点信息
  }MGraph;	//图的邻接矩阵类型

• 邻接表

  图的一种链式存储结构

  对图中每个顶点建立一个单链表

  第i个单链表中的结点表示依附于顶点v_i的边(有向图是以顶点v_i为尾的弧)

  每个结点由3个域组成，其中邻接点域指示与顶点v_i邻接的点在图中的位置，链域指示下一条边或弧的结点，数据域存储和边或弧相关的信息，如权值等

  typedef struct ArcNode
  {
      int adjvex;	//该边所指向的结点的位置
      struct ArcNode *nextarc;	//指向下一条边的指针
      int info;	//该边的相关信息，可省略
  }ArcNode;
  
  typedef struct
  {
      char data;	//顶点信息
      ArcNode *firstarc;	//指向第一条边的指针
  }VNode;
  
  typedef struct
  {
  	VNode adjlist[maxSize];		//邻接表
      int n,e;	//顶点数和边数
  }AGraph;	//图的邻接表类型

• 十字链表

• 邻接多重表

图的遍历

• 深度优先搜索（DFS）

  深度优先搜索生成树

• 广度优先搜索（BFS）

最小生成树

构造连通网的最小代价生成树

• 普利姆(Prim)算法
• 克鲁斯卡尔(Kruskal)算法

有向无环图(directed acycline graph)

• 简称DAG图
• 拓扑排序
• AOV-网：用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网(Activity On Vertex Network)
• AOE-网：用边表示活动的网
• 关键路径

最短路径

• 迪杰斯特拉(Dijkstra)算法

  求图中某一顶点到其余各顶点的最短路径

• 弗洛伊德算法

  求图中任意一对顶点间的最短路径