[数据结构与算法]【数据结构】05 图

05 图

01 图的基本概念

• 图的定义：由顶点集$V$ 和边集$E$ 组成，记为$G=(V,E)$
• 类型：
  • 有向图
  • 无向图
  • 简单图：不存在重复边，不存在顶到到自身的边
  • 多重图：图$G$ 中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己相关联
  • 完全图：无向图中任意两个顶点都存在边，有向图中任意两个顶点之间都存在方向相反的两条弧

02 图的存储和基本操作

• 邻接矩阵表示法：

  $A[i][j]=\{\begin{array}{ll}1& 若(v_i,v_j)或<v_i,v_j>是E(G)中的边\\ 0& 若(v_i,v_j)或<v_i,v_j>不是E(G)中的边\end{array}$

  // 邻接矩阵存储结构定义如下
  # define MaxVertexNum 100  // 顶点数目的最大值
  typedef char VertexType;  // 顶点的数据类型
  typedef int EdgeType;  // 带权图中边上权值的数据类型
  typedef struct  
  {
   	VertexType[MaxVertexNum]; // 顶点表
      EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵，边表
      int vexnum, arcnum;  // 图的当前顶点数和弧数
  }MGraph;
  

• 邻接表法：

  # define MaxVertexNum 100	 // 顶点数目的最大值
  typedef struct ArcNode{	 // 边表结点
      int adjvex;			// 该弧所指向的顶点的位置
      struct ArcNode *next;	// 指向下一条弧的指针
      // Infotype info	// 网的权值
  }ArcNode;
  typedef struct VNode{	//顶点表结点
      VertexType data;	// 顶点信息
      ArcNode *first;		// 指向第一条依附该顶点的弧的指针
  }VNode, AdjList[MaxVertexNum];
  typedef struct{
      AdjList vertices; // 邻接表
      int vexnum, arcnum;  //图的顶点数和弧数
  }ALGraph;  // ALGraph是以邻接表存储类型的图类型
  
  

• 十字表法：

  #define MaxVertexNum 100  //图中顶点数目的最大值
  typedef struct ArcNode{		// 边表结点
      int tailvex, headvex;	// 该弧的头尾结点
      struct ArcNode *hlink, *tlink;	// 分布指向弧头相同和弧尾相同的结点
      //infotype info;
  }ArcNode;  // 相关信息指针
  typedef struct VNode{		// 顶点表结点
      VertexType data;		// 顶点信息
      ArcNode *firstin, *firstout; // 指向第一条入弧和第一条出弧
  }VNode;
  typedef struct{		
      VNode xlist[MaxVertexNum];  //邻接表
      int vexnum, arcnum;  // 图的顶点数和弧数
  }GLGraph;		// GLgraph是以十字邻接表存储的图结构
  

• 邻接多重表法：

  #define MaxVertexNum 100	//图中顶点数目的最大值
  typedef struct ArcNode{		//边表结点
      bool mask;				// 访问标记
      int ivex, jvex;			// 分别指向该弧的两个结点
      struct ArcNode *ilink, *jlink;	// 分别指向两个顶点的下一条边
      // Infotype info
  }ArcNode;
  typedef struct VNode{		//顶点表结点
      VertexType data;		//顶点信息
      ArcNode *firstedge;		//指向第一条依附该顶点的边
  }VNode;
  typedef struct{			// 邻接表
      VNode adjmulist[MaxVertexNum];	//图的顶点数和弧数
      int vexnum, arcnum;			//AMLGraph是以邻接多重表存储的图类型
  }AMLGraph;
  

03 图的遍历：

• 深度优先遍历（需要背下基本写法）
  • 一直向下探，当不能向下访问后，依次被访问的任一结点，若其还有邻接顶点未被访问，则从该点开始搜索，直到图中所以顶点均被访问为止
• 广度优先遍历（需要背下基本写法）
  • 类似树的层次遍历

04 图的应用：

• 最小生成树：是图的极小连通子图，包含图中的所以顶点，并且只含尽可能少的边

  • Prim算法：求解稠密图的最小生成树
  • Kruskal算法：选择边，边不够成回路就将其加入$E_T$

• 最短路径：顾名思义，在图中选择最小权重的路径

  • Dijkstra算法：思路类似贪心算法，求单源最短路径问题
  • Floyd算法：求个顶点之间的最短路径问题，初始是邻接矩阵的原始数据，之后每一步多考虑一个顶点，直到所有顶点都考虑到。

• 拓扑排序：

  • DAG图：若一个有向图中不存在环，则称为有向无环图
  • AOV网：用DAG网表示一个工程，顶点表示活动。活动的执行有顺序要求

• 关键路径：找到最长的路径

  • 最早发生时间max
  • 最晚发生时间min