跳转至

Graph

图的相关概念

在图论中，有一些基本的概念和术语需要了解。以下是一些与图相关的重要概念：

  1. 节点（顶点）（Node / Vertex）：图中的一个元素，可以表示为一个实体、一个对象或一个抽象概念。节点被用来表示图中的个体。
  2. 边（Edge）：连接两个节点的线段，用于表示节点之间的关系。边可以是有向的（从一个节点指向另一个节点），也可以是无向的（没有方向性）。
  3. 有向图（Directed Graph）：图中的边具有方向的图称为有向图。在有向图中，边从一个节点指向另一个节点，并且不一定是对称的。
  4. 无向图（Undirected Graph）：图中的边没有方向的图称为无向图。在无向图中，边是对称的，可以双向通行。
  5. 加权图（Weighted Graph）：图中的边可以带有权重或距离的图称为加权图。这种权重可以表示节点之间的关联强度、距离等信息。
  6. 路径（Path）：在图中由边连接的节点序列称为路径。路径可以由一个节点到另一个节点，可以是直接连接的，也可以经过其他节点。
  7. 环（Cycle）：在有向图中，如果存在从一个节点出发并经过若干边又回到该节点的路径，则称之为环。
  8. 连通图（Connected Graph）：无向图中，如果任意两个节点之间都存在一条路径，则称之为连通图。有向图中，如果对于任意两个节点 u 和 v，都存在从 u 到 v 和从 v 到 u 的路径，则称之为强连通图。
  9. 强连通分量（Strongly Connected Component）：在有向图中，一个最大的子图，其中每两个节点之间都是互相可达的，称为强连通分量。
  10. 入度（In-degree）和出度（Out-degree）：在有向图中，节点的入度表示指向该节点的边的数量，出度表示从该节点发出的边的数量。

图的表示方法

在图论中，有多种表示图的方法。常用的包括邻接矩阵、邻接表和关联矩阵。以下将详细介绍这些表示方法：

  1. 邻接矩阵（Adjacency Matrix）：

  2. 邻接矩阵是一个二维数组，用于表示图中节点之间的连接关系。

  3. 对于有n个节点的图，邻接矩阵是一个n×n的矩阵，矩阵的元素表示节点之间的边的存在与否，通常使用0和1表示。
  4. 如果图是无向图，则邻接矩阵是对称的；如果图是有向图，则不一定是对称的。
  5. 邻接矩阵的优点是可以快速判断任意两个节点之间是否存在连接关系，但缺点是对于稀疏图（边很少）而言，会浪费大量空间。
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//邻接矩阵表示法
#include <iostream>
#include <vector>

using namespace std;

class Graph {
private:
    int numNodes;
    vector<vector<int>> adjacencyMatrix;

public:
    Graph(int n) : numNodes(n), adjacencyMatrix(n, vector<int>(n, 0)) {}

    void addEdge(int from, int to) {
        adjacencyMatrix[from][to] = 1;
        // 如果是无向图，还需添加以下代码
        // adjacencyMatrix[to][from] = 1;
    }

    void printGraph() {
        for (int i = 0; i < numNodes; i++) {
            for (int j = 0; j < numNodes; j++) {
                cout << adjacencyMatrix[i][j] << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    Graph graph(5);
    graph.addEdge(0, 1);
    graph.addEdge(1, 2);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);
    graph.addEdge(4, 0);

    graph.printGraph();

    return 0;
}

  1. 邻接表（Adjacency List）：

  2. 邻接表使用链表或数组的集合来表示图的每个节点以及其相邻的节点。

  3. 对于有n个节点的图，邻接表是一个大小为n的数组，每个数组元素都是一个链表，存储了与该节点相邻的节点。
  4. 对于有向图，邻接表中的链表只包含出度的节点；对于无向图，邻接表中的链表要同时包含入度和出度的节点。
  5. 邻接表的优点是可以有效地表示稀疏图，并且占用的空间相对较少。但在判断两个节点之间是否有连接时需要遍历链表。
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//邻接表表示法
#include <iostream>
#include <list>

using namespace std;

class Graph {
private:
    int numNodes;
    list<int> *adjacencyList;

public:
    Graph(int n) : numNodes(n) {
        adjacencyList = new list<int>[numNodes];
    }

    void addEdge(int from, int to) {
        adjacencyList[from].push_back(to);
        // 如果是无向图，还需添加以下代码
        // adjacencyList[to].push_back(from);
    }

    void printGraph() {
        for (int i = 0; i < numNodes; i++) {
            cout << "节点 " << i << " 的相邻节点: ";
            for (auto it = adjacencyList[i].begin(); it != adjacencyList[i].end(); ++it) {
                cout << *it << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    Graph graph(5);
    graph.addEdge(0, 1);
    graph.addEdge(1, 2);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);
    graph.addEdge(4, 0);

    graph.printGraph();

    return 0;
}

  1. 关联矩阵（Incidence Matrix）：

  2. 关联矩阵也是一个二维数组，用于表示图中节点和边之间的关系。

  3. 对于有n个节点和m条边的图，关联矩阵是一个n×m的矩阵，矩阵的元素表示节点与边的关系，通常使用0和1表示。
  4. 关联矩阵的行表示节点，列表示边，当某个节点与某条边相连时，对应的位置为1；否则为0。
  5. 关联矩阵适用于表示多重图（存在平行边）或者需要考虑边的权重等其他信息的情况。
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//关联矩阵表示法
#include <iostream>
#include <vector>

using namespace std;

class Graph {
private:
    int numNodes;
    int numEdges;
    vector<vector<int>> incidenceMatrix;

public:
    Graph(int n, int m) : numNodes(n), numEdges(m), incidenceMatrix(n, vector<int>(m, 0)) {}

    void addEdge(int from, int to, int edgeIndex) {
        incidenceMatrix[from][edgeIndex] = 1;
        incidenceMatrix[to][edgeIndex] = 1;
    }

    void printGraph() {
        for (int i = 0; i < numNodes; i++) {
            for (int j = 0; j < numEdges; j++) {
                cout << incidenceMatrix[i][j] << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    Graph graph(5, 5);
    graph.addEdge(0, 1, 0);
    graph.addEdge(1, 2, 1);
    graph.addEdge(2, 3, 2);
    graph.addEdge(3, 4, 3);
    graph.addEdge(4, 0, 4);

    graph.printGraph();

    return 0;
}

图论的常见算法

图论是一个相当庞大的领域，因此有很多种类的图算法。以下是一些常见的图算法：

  1. 遍历算法：这些算法用于遍历图的所有顶点或边。
  2. 深度优先搜索 (DFS)
  3. 广度优先搜索 (BFS)
  4. 最短路径算法：这些算法用于找到两点之间的最短路径。
  5. Dijkstra的算法
  6. Bellman-Ford算法
  7. Floyd-Warshall算法
  8. A*搜索算法
  9. 最小生成树算法：这些算法用于找到连通所有顶点并具有最小总权重的树。
  10. Kruskal的算法
  11. Prim的算法
  12. Boruvka的算法
  13. 拓扑排序算法：这些算法用于有向无环图，结果是一个线性排序，该排序中的每个节点都出现在其依赖项之后。
  14. Kahn's算法
  15. Depth-First Search (DFS)
  16. 匹配和网络流算法：这些算法用于找到网络流中的最大流或最小割。
  17. Ford-Fulkerson算法
  18. Edmonds-Karp算法
  19. Dinic's算法
  20. Kuhn-Munkres (或Hungarian)算法
  21. 连通性算法：这些算法用于确定图的连通性。
  22. Tarjan的强连通分量算法
  23. Kosaraju's算法
  24. Union-Find算法
  25. 图着色算法：这些算法用于为图的顶点分配颜色，以使相邻的顶点具有不同的颜色。
  26. Greedy图着色算法
  27. Backtracking
  28. 哈密顿和欧拉图算法：这些算法用于找到经过所有顶点一次且仅一次的路径或循环。
  29. Fleury's Algorithm（欧拉路径）
  30. Backtracking（哈密顿路径）
  31. 图的割点与桥的查找
  32. Tarjan's algorithm for Articulation Points
  33. Tarjan's algorithm for Bridges
  34. 最大独立集问题：在图论中，独立集是图的一组顶点，这组顶点之间没有任何边。最大独立集问题就是找到一个图的最大独立集。
  35. 最小覆盖集问题：在图论中，覆盖集是图的一组顶点，这组顶点可以覆盖图的所有边。最小覆盖集问题就是找到一个图的最小覆盖集。
  36. 最大团问题：在图论中，团是图的一组顶点，这组顶点之间两两相邻。最大团问题就是找到一个图的最大团。
  37. 图的同构性：给定两个图，判断它们是否同构。
  38. 点覆盖问题：在图论中，点覆盖是图的一组顶点，这组顶点至少与图的每一条边相邻。最小点覆盖问题就是找到一个图的最小点覆盖。
  39. 最大流最小割定理：这是一个网络流问题，用于找出一个网络的最大流和最小割。
  40. Hopcroft–Karp algorithm：这是一种用于解决二分图的最大匹配问题的算法。
  41. Johnson's algorithm：这是一种用于在所有顶点对之间找到最短路径的算法，适用于处理包含负权重边的图。
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用