数据结构-图

图的增删改查

增

• 邻接表
• 邻接矩阵

删

改

查

图的遍历

深度优先遍历(DFS)

深度优先搜索法是树的先根遍历的推广，它的基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。

递归实现
（1）访问顶点v；visited[v]=1；//算法执行前visited[n]=0
（2）w=顶点v的第一个邻接点；
（3）while（w存在）  
        if（w未被访问）
            从顶点w出发递归执行该算法； 
        w=顶点v的下一个邻接点；

非递归实现（栈实现）
（1）栈S初始化；visited[n]=0；
（2）访问顶点v；visited[v]=1；顶点v入栈S
（3）while(栈S非空)
        x=栈S的顶元素(不出栈)；
        if(存在并找到未被访问的x的邻接点w)
            访问w；visited[w]=1；
            w进栈;
        else
            x出栈；

广度优先遍历(BFS)

图的广度优先搜索是树的按层次遍历的推广，它的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2,…, vi t，并均标记已访问过，然后再按照vi1,vi2,…, vi t的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。

非递归实现（队列实现）
（1）初始化队列Q；visited[n]=0；
（2）访问顶点v；visited[v]=1；顶点v入队列Q；
（3）while（队列Q非空）   
        v=队列Q的对头元素出队；
        w=顶点v的第一个邻接点；
        while（w存在） 
            如果w未访问，则访问顶点w；
            visited[w]=1；
            顶点w入队列Q；
            w=顶点v的下一个邻接点。

图的种类

• 补图
  与G拥有相同的点的完全图删除原图G的边所得到的图成为G的补图

• 树状图

• 平面图
  平面图是可以画在平面上并且使得不同的边可以互不交叠的图。

• 连通图

  • 强连通图
    有向图G= (V,E)中，若对于V中任意两个不同的顶点x和y，都存在从x到y以及从y到x的路径，则称G是强连通图（Strongly Connected Graph）。相应地有强连通分量（Strongly Connected Component）的概念。强连通图只有一个强连通分量，即是其自身；非强连通的有向图有多个强连通分量。
  • 连通分量
    无向图G的一个极大连通子图称为G的一个连通分量（或连通分支）。连通图只有一个连通分量，即其自身；非连通的无向图有多个连通分量。

• 有向无环图
  如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个有向无环图（DAG图）。

  • AOE网
    AOE网(Activity On Edge)即边表示活动的网，是一个带权的有向无环图，其中顶点表示事件（Event），每个事件表示在它之前的活动已经完成，在它之后的活动可以开始，弧表示活动，权表示活动持续的时间。AOE网可用来估算工程的完成时间。由于整个工程只有一个开始点和一个完成点，故在正常的情况（无环）下，网中只有一个入度为零的点（源点）和一个出度为零的点（汇点）。

• 完全图
  完全图是每对顶点之间都恰连有一条边的简单图。

• 二分图
  二分图又称双分图、二部图、偶图，指顶点可以分成两个不相交的集U和V( U and V 皆为独立集（independent sets），使得在同一个集内的顶点不相邻（没有共同边）的图。

• 正则图
  正则图是每个顶点都有相同数目的邻居的图，即每个顶点的度相同。若每个顶点的度均为 k，称为 k-正则图。0-正则图是没有边的图。1-正则图由不相连的边组成。2-正则图由不相连的圈组成。3-正则图称为三次图。阶为k的 k-1-正则图是 k完全图。
  

  正则图

• 欧拉图
  存在经过所有边一次（可以多次经过点）的路径的图。

• 哈密顿图
  存在经过所有点一次的路径的图。