1. 有向图和无向图的邻接矩阵
设 G(V, E)是一个具有 n 个顶点的图,则图的邻接矩阵是一个 n×n 的二维数组,用 Edge[n][n]表示,它的定义为:
下面的图给出了无向图 G1(V, E)及其邻接矩阵表示。在图中,为了表示顶点信息,特意将顶点的标号用字母 A、 B、 C、 D、 E 和 F 表示,各顶点的信息存储在顶点数组中,如图(b)所示,注意在 C/C++语言中,数组元素下标是从 0 开始计起的。 G1 的邻接矩阵如图(c)所示,从该图可以看出,无向图的邻接矩阵是沿主对角线对称的。
对无向图的邻接矩阵来说, 如果 Edge[i][j] = 1, 则表示顶点 i 和顶点 j 之间有一条边。因此,邻接矩阵 Edge 第 i 行所有元素中元素值为 1 的个数表示顶点 i的度数,第 i 列所有元素中元素值为 1 的个数也表示顶点 i 的度数,即:
而对有向图的邻接矩阵来说, 如果 Edge[i][j] = 1, 则表示存在从顶点 i 到顶点 j 有一条有向边, i 是起点, j 是终点。因此,邻接矩阵 Edge 第 i 行所有元素中元素值为 1 的个数表示顶点 i 的出度,第 i 列所有元素中元素值为 1 的个数表示顶点 i 的入度,即:
2. 用邻接矩阵存储有向图,并输出各顶点的出入和入度
输入描述:
输入文件中包含多个测试数据,每个测试数据描述了一个无权有向图。每个测试数据的第一行为两个正整数 n 和 m, 1 ≤ n ≤ 100, 1 ≤ m ≤ 500,分别表示该有向图的顶点数目和边数,顶点的序号从 1 开始计起。接下来有 m 行,每行为两个正整数,用空格隔开,分别表示一条边的起点和终点。每条边出现一次且仅一次,图中不存在自身环和重边。输入文件最后一行为 0 0,表示输入数据结束。
输出描述:
对输入文件中的每个有向图,输出两行:第 1 行为 n 个正整数,表示每个顶点的出度;第 2行也为 n 个正整数,表示每个顶点的入度。每两个正整数之间用一个空格隔开,每行的最后一个正整数之后没有空格。
#include <iostream>
#include <cstring>
#define MAXL 100
using namespace std;
int Edge[MAXL][MAXL]; // 定义存储矩阵
int main() {
int n, m; // n为顶点个数,m为边个数
int od, id; // od为出度,id为入度
int u, v; // u为起点,v为终点
while (1) {
cin >> n >> m;
if (m == 0 && n == 0) {
break;
}
memset(Edge, 0, sizeof(Edge));
for (int i = 1; i <= m; i++) {
cin >> u >> v; // 读入起点终点
Edge[u - 1][v - 1] = 1; // 构建邻接矩阵
}
for (int i = 0; i < n; i++) {
od = 0;
for (int j = 0; j < n; j++) {
od += Edge[i][j]; // 求入度
}
cout << od << " ";
}
cout << endl;
for (int i = 0; i < n; i++) {
id = 0;
for (int j = 0; j < n; j++) {
id += Edge[j][i]; // 求出度
}
cout << id << " ";
}
cout << endl;
}
}
程序输出结果如下:
3. 有向网和无向网的邻接矩阵
对于网络(即带权值的图),邻接矩阵的定义为:
在编程实现时,可以用一个比较大的常量表示无穷大∞。
下面给出了无向网 G1(V, E)及其邻接矩阵表示。在无向网的邻接矩阵中,如果 0<Edge[i][j]<∞,则顶点 i 和顶点 j 之间有一条无向边,其权值为 Edge[i][j]。从图中可以看出,无向网的邻接矩阵也是沿主对角线对称的。
下面给出了有向网 G2(V, E)及其邻接矩阵表示。在有向网的邻接矩阵中,如果 0<Edge[i][j]<∞,则从顶点 i 到顶点 j 有一条有向边,其权值为 Edge[i][j]。从该图可以看出,有向网的邻接矩阵不一定是沿对主角线对称的。
标签:表示,存储,有向图,int,邻接矩阵,Edge,顶点 From: https://www.cnblogs.com/love-9/p/18114474