有向图的关联矩阵与邻接矩阵有何联系

有向图的邻接矩阵和关联矩阵都是表示有向图的常用矩阵表示方法。

邻接矩阵是一个 $n\times n$ 的矩阵，其中 $n$ 表示有向图中顶点的个数。如果 $i$ 到 $j$ 有一条有向边，则邻接矩阵中的第 $i$ 行第 $j$ 列为 $1$，否则为 $0$。

而关联矩阵是一个 $n\times m$ 的矩阵，其中 $n$ 表示有向图中的顶点数，$m$ 表示有向边的数量。如果第 $i$ 个顶点和第 $j$ 条边之间有关联，则关联矩阵中的第 $i$ 行第 $j$ 列为 $1$ 或 $-1$，表示该边是从 $i$ 开始或者结束。

它们的联系在于，我们可以从邻接矩阵中得到关联矩阵。具体地，设邻接矩阵为 $A$，则关联矩阵 $B$ 可以通过以下方法得到：

1. 对于邻接矩阵中第 $i$ 行第 $j$ 列为 $1$ 的元素，假设这是一条从 $i$ 到 $j$ 的边，则在关联矩阵中的第 $i$ 行第 $k$ 列和第 $j$ 行第 $k$ 列分别为 $1$ 和 $-1$，其中 $k$ 是表示第 $i$ 到 $j$ 的第 $k$ 条边。
2. 对于邻接矩阵中第 $i$ 行第 $j$ 列为 $0$ 的元素，则在关联矩阵中的第 $i$ 行和第 $j$ 行的所有列都为 $0$。

因此，关联矩阵可以从邻接矩阵中计算得到。

相关问题

用c++实验无向图有向图关联矩阵，邻接矩阵的存储结构，以及深度遍历算法

在C++中，无向图和有向图通常使用邻接矩阵（Adjacency Matrix）作为其存储结构。邻接矩阵是一个二维数组，其中行代表图中的顶点，列表示每个顶点连接的顶点集合。对于无向图，邻接矩阵是对称的，即如果(i, j)位置的值存在，则(j, i)位置也有相同的值；而对于有向图，邻接矩阵是对角线不对称的，表示从一个顶点到另一个顶点是否有边。

存储结构通常是这样的：
1. 对于无向图：`adjMatrix[vertex][vertex]`
2. 对于有向图：`adjMatrix[vertex][neighbor]`

深度优先搜索（Depth-First Search, DFS）是一种用于遍历图的算法，特别是用于寻找连通分量、拓扑排序等应用。在邻接矩阵上实现DFS的基本步骤如下：

void dfs(int start, bool graph[vertices][vertices], vector<bool>& visited) {
    // 标记当前节点已访问
    visited[start] = true;
    cout << start << " ";

    // 遍历邻居节点
    for (int i = 0; i < vertices; i++) {
        if (graph[start][i] && !visited[i]) {
            dfs(i, graph, visited);
        }
    }
}

在这个函数里，`start`是起点，`graph`是邻接矩阵，`visited`是一个布尔数组记录了每个节点是否被访问过。通过递归地访问未访问过的邻居节点，直到遍历完所有可达路径。