有向图的邻接矩阵c++

有向图的邻接矩阵C是一个n×n的矩阵，其中n是图中顶点的数量。矩阵的第i行第j列的元素c[i][j]表示从顶点i到顶点j是否有一条有向边。如果有边，则c[i][j]为1；如果没有边，则c[i][j]为0。

在有向图的邻接矩阵中，对角线元素c[i][i]通常代表顶点i到自己的边，因为无法自己连向自己，所以c[i][i]通常为0。对于有多重边的图，矩阵中的元素c[i][j]可以表示该边的权重或者出现的次数。

邻接矩阵C可以用于表示有向图的拓扑结构，通过检查矩阵中的元素即可判断两个顶点之间是否存在边的关系。C的大小为n×n，因此空间复杂度为O(n^2)。在判断两个顶点之间是否有边时，时间复杂度为O(1)，因为只需要检查矩阵中的元素。

邻接矩阵C还可以用于解决一些与图结构相关的问题，如查找顶点的入度和出度、判断图的连通性以及查找图中的环等。然而，邻接矩阵的缺点是当图中的边数量相对较少时，矩阵中会存在大量的0元素，导致存储空间的浪费。此外，邻接矩阵无法表示带权有向图中负权边的情况。

总之，有向图的邻接矩阵C是一种有效的图表示方法，能够方便地表示图的结构和边的关系，但在面对稀疏图或带负权边的情况时存在一些局限性。

相关问题

邻接矩阵c++存储有向图无向图加权图

邻接矩阵是一种常用的图的表示方法，可以用于存储有向图、无向图和加权图。在邻接矩阵中，矩阵的行和列分别表示图中的顶点，矩阵中的元素表示两个顶点之间是否存在边或者边的权重。

对于有向图，邻接矩阵的元素A[i][j]表示从顶点i到顶点j是否存在一条有向边。如果A[i][j]的值为1，则表示存在有向边；如果A[i][j]的值为0，则表示不存在有向边。

对于无向图，邻接矩阵是对称的，即A[i][j]的值与A[j][i]的值相等。如果A[i][j]的值为1，则表示顶点i与顶点j之间存在一条无向边；如果A[i][j]的值为0，则表示顶点i与顶点j之间不存在边。

对于加权图，邻接矩阵的元素A[i][j]可以表示边的权重。如果A[i][j]的值为0，则表示顶点i与顶点j之间不存在边；如果A[i][j]的值为非零正数，则表示顶点i与顶点j之间存在一条边，并且边的权重为A[i][j]的值。

c++有向图邻接矩阵建立深度遍历

下面是C++语言实现邻接矩阵建立有向图并进行深度遍历的示例代码：

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 100; //最大节点数
int G[maxn][maxn]; //邻接矩阵
bool vis[maxn]; //标记节点是否已被访问
int n, m; //节点数和边数

void DFS(int u) { //深度遍历
    vis[u] = true; //标记节点已被访问
    cout << u << " "; //输出节点编号
    for (int v = 1; v <= n; v++) { //枚举所有节点
        if (G[u][v] && !vis[v]) { //如果u和v之间有边，并且v未被访问过
            DFS(v); //从v开始继续深度遍历
        }
    }
}

int main() {
    cin >> n >> m; //读入节点数和边数
    memset(G, 0, sizeof(G)); //初始化邻接矩阵
    memset(vis, false, sizeof(vis)); //初始化节点访问标记
    for (int i = 1; i <= m; i++) { //读入m条边
        int u, v;
        cin >> u >> v;
        G[u][v] = 1; //建立有向边
    }
    for (int i = 1; i <= n; i++) { //枚举所有节点
        if (!vis[i]) { //如果节点未被访问过
            DFS(i); //从该节点开始深度遍历
        }
    }
    return 0;
}

以上代码中，DFS函数表示深度遍历函数，vis数组用于标记节点是否已被访问，G数组表示邻接矩阵。输入节点数和边数后，读入每条边，并建立邻接矩阵。最后枚举所有节点，从未被访问过的节点开始深度遍历。