建立一有向图的邻接矩阵

邻接矩阵是一种表示图的方式，其中行和列分别对应于图中的节点，矩阵中的每个元素表示这两个节点之间是否存在一条边。对于有向图来说，邻接矩阵是一个方阵，其中第 i 行第 j 列的元素表示从节点 i 到节点 j 是否存在一条有向边。

如果有向图中有 n 个节点，则其邻接矩阵是一个 n × n 的矩阵。如果从节点 i 到节点 j 存在一条有向边，则邻接矩阵中的第 i 行第 j 列的元素为 1，否则为 0。

下面是一个有向图的邻接矩阵的示例：

  1 2 3 4
1 0 1 0 1
2 0 0 1 0
3 0 0 0 1
4 0 0 0 0

在这个有向图中，共有四个节点，分别用数字 1、2、3 和 4 表示。从第 1 个节点到第 2 个节点存在一条有向边，从第 1 个节点到第 4 个节点也存在一条有向边，从第 2 个节点到第 3 个节点存在一条有向边，从第 3 个节点到第 4 个节点也存在一条有向边。因此，邻接矩阵中的第 1 行第 2 列、第 1 行第 4 列、第 2 行第 3 列和第 3 行第 4 列的元素为 1，其余元素都为 0。

相关问题

c语言定义有向图邻接矩阵

C语言定义有向图邻接矩阵可以通过二维数组来实现。邻接矩阵是一个n*n的矩阵，其中n是有向图中顶点的数量。如果有向图中存在一条从顶点i到顶点j的边，则邻接矩阵中第i行第j列的元素为1，否则为0。在C语言中，可以使用二维数组来表示邻接矩阵，例如：

int graph[MAX][MAX]; // MAX为顶点的最大数量

// 初始化邻接矩阵
for (int i = 0; i < MAX; i++) {
    for (int j = 0; j < MAX; j++) {
        graph[i][j] = 0;
    }
}

// 添加边
graph[0][1] = 1; // 添加从顶点0到顶点1的边
graph[1][2] = 1; // 添加从顶点1到顶点2的边
// ...

这样，我们就可以使用邻接矩阵来表示有向图，并且可以方便地添加和删除边。

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数组表示邻接矩阵。输入节点数和边数后，读入每条边，并建立邻接矩阵。最后枚举所有节点，从未被访问过的节点开始深度遍历。