图的分类

有向图和无向图

连通图和非连通图

有权图和无权图

图的常见术语

邻接(adjacency)：两个顶点有边相连，则称两个顶点邻接。
路径(path)：两个顶点相连经过的边。
度(degree)：一个顶点拥有多少边。对于有向图，细分为入度和出度。

图的表示

邻接矩阵

邻接矩阵表示法有以下特点：

简单图中，顶点不能与自身相连，主对角线元素无意义。
无向图中，两个方向的边等价，此时临接矩阵关于主对角线对称。
将邻接矩阵的元素从0和1替换为权重，可以表示有权图。
邻接矩阵的增删查改时间复杂度都是 $O(1)$，但空间复杂度为 $O(n^2)$。

邻接表

邻接表使用 $n$ 个链表表示图，每个链表存储了顶点的所有邻接顶点。邻接表可以采用类似哈希表“链式地址”的方法来优化存储效率。

图的基础操作

邻接矩阵实现

给定一个顶点数量为n的无向图，则各种操作的实现方式如图9-7所示。

• 添加或删除边：直接在邻接矩阵中修改指定的边即可，使用$O(1)$时间。而由于是无向图，因此需要同

时更新两个方向的边。
添加顶点：在邻接矩阵的尾部添加一行一列，并全部填O即可，使用$O(n)$时间。
删除顶点：在邻接矩阵中删除一行一列。当删除首行首列时达到最差情况，需要将$(n-1)^2$ 个元素“向左上移动”，从而使用$O(n_2)$时间。
初始化：传入n个顶点，初始化长度为n的顶点列表，使用$O(n)$时间；初始化邻接矩阵 adjMat，使用$O(n_2)$时间。

class GraphAdjMat {
  vector<int> vertices;
  vector<vector<int>> adjMat;
public:
  GraphAdjMat(const vector<int>& vectices, const vector<vector<int>>& edges) {
    for (int val : vertices) {
      addVertex(val);
    }
    
    for (const vector<int>& edge : edges) {
      addEdge(edge[0], edge[1]);
    }
  }
  
  int size() const {
    return vertices.size();
  }
  
  void addVertex(int val) {
    vertices.push_back(val);
    adjMat.emplace_back(vector<int>(n, 0));
    for (vector<int>& row : adjMat) {
      row.push_back(0);
    }
  }
  
  void removeVertex(int index) {
    if (index >= size()) {
      throw out_of_range("");
    }
    
    vertices.erase(vertices.begin() + index);
    adjMat.erase(adjMat.begin() + index);
    for (vector<int>& row : adjMat) {
      row.erase(row.begin() + index);
    }
  }
  
  void addEdge(int i, int j) {
    if (i < 0 || j < 0 || i >= size() || j >= size() || i == j) {
      throw out_of_range("");
    }
    
    adjMat[i][j] = 1;
    adjMat[j][i] = 1;
  }
  
  void removeEdge(int i, int j) {
    if (i < 0 || j < 0 || i >= size() || j >= size() || i == j) {
      throw out_of_range("");
    }
    adjMat[i][j] = 0;
    adjMat[j][i] = 0;
    
  }
}

邻接表实现

添加边：在顶点对应链表的末尾添加边即可，使用$O(1)$时间。因为是无向图，所以需要同时添加两个方向的边。
删除边：在顶点对应链表中查找并删除指定边，使用$O(m)$时间。在无向图中，需要同时删除两个方向的边。
添加顶点：在邻接表中添加一个链表，并将新增顶点作为链表头节点，使用$O(1)$时间。
删除顶点：需遍历整个邻接表，删除包含指定顶点的所有边，使用$O(n+m)$时间。
初始化：在邻接表中创建n个顶点和2m.条边，使用$O（n+m）$时间。

class GraphAdjList {
public:
  unordered_map<Vertex*, vector<Vertex*>> adjList;

  // 删除顶点
  void remove(vector<Vertex*>& vec, Vertex* vet) {
    for (int i = 0; i < vec.size(); ++i) {
      if (vec[i] == vet) {
        vec.erase(vec.begin() + 1);
        break;
      }
    }
  }

  GraphAdjList(const vector<vector<Vertex*>>& edges) {
    for (const vector<Vertex*>& edge : edges) {
      addVertex(edge[0]);
      addVertex(edge[1]);
      addEdge(edge[0], edge[1]);
    }
  }

  void addEdge(Vertex* vet1, Vertex* vet2) {
    if (!adjList.count(vet1) || !adjList.count(vet2) || vet1 == vet2) throw invalid_argument("");
   adjList[vet1].push_back(vet2);
    adjList[vet2].push_back(vet1);
  }
  
  void removeEdge(Vertex* vet1, Vertex* vet2) {
    if (!adjList.count(vet1) || !adjList.count(vet2) || vet1 == vet2) throw invalid_argument("");
    remove(adjList[vet1], vet2);
    remove(adjList[vet2], vet1);
  }


  void addVertex(Vertex* vet) {
    if (adjList.count(vet)) {
      return;
    }

    adjList[vet] = vector<Vertex*>();
  }

  void removeVertex(vertex* vet) {
    if (!adjList.count(vet))
      throw invalid_argument("");

    adjList.erase(vet);

    for (auto& adj : adjList) {
      remove(adj.second, vet);
    }
  }
};

图的遍历

广度优先遍历