显示图的邻接矩阵的流程图
时间: 2023-10-20 15:35:13 浏览: 66
以下是显示图的邻接矩阵的流程图:
```
开始
输入图的顶点数和边数
创建一个顶点数*顶点数的矩阵
标记矩阵的行和列为对应的顶点
对于每条边:
输入边的起点和终点
如果是无向图:
在矩阵中将起点和终点对应的元素设为1
将终点和起点对应的元素设为1
如果是有向图:
在矩阵中将起点和终点对应的元素设为1
如果有权重:
输入权重值
在相应的矩阵元素中填入权重值
输出邻接矩阵
结束
```
该流程图描述了一般情况下的邻接矩阵生成过程,具体实现可能会因为实际情况而有所不同。
相关问题
图的邻接矩阵和邻接表的相互转化的流程图
以下是图的邻接矩阵和邻接表的相互转化的流程图:
将图的邻接矩阵转化为邻接表:
```
开始
创建空的邻接表
遍历邻接矩阵
如果邻接矩阵中当前位置的值不为0
添加一条边到邻接表的相应节点的相邻列表中
结束遍历
返回邻接表
```
将图的邻接表转化为邻接矩阵:
```
开始
计算图中的节点数n
创建一个n x n的邻接矩阵,初始化所有元素为0
遍历邻接表
对于每个节点,遍历其相邻节点列表
将相邻节点与该节点之间的边转化为邻接矩阵中的一个非零值
结束遍历
返回邻接矩阵
```
用算法流程和算法流程图阐述通过点集和边集构建关联矩阵和邻接矩阵的过程
通过点集和边集构建关联矩阵和邻接矩阵的过程可以分为以下几个步骤:
1. 读入点集和边集。
2. 定义关联矩阵和邻接矩阵,并初始化为 0。
3. 遍历边集,对于每一条边,找到它的两个端点,然后在关联矩阵中相应位置填写 1 和 -1,表示这条边从一个端点出发,到达另一个端点。同时在邻接矩阵中相应位置填写 1,表示这两个顶点之间有一条边。
4. 遍历每一个顶点,计算它的度数。如果是无向图,度数等于它的相邻顶点个数;如果是有向图,分别计算它的入度和出度。
5. 输出关联矩阵、邻接矩阵和每个顶点的度数。
以下是算法流程图:
<img src="https://img-blog.csdnimg.cn/20211012004223817.png" width="500px">
以下是 C++ 代码实现:
```cpp
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1005;
int n, m; // n 是顶点数,m 是边数
vector<int> edge[MAXN]; // 邻接表存图
int mat[MAXN][MAXN]; // 关联矩阵
int adj[MAXN][MAXN]; // 邻接矩阵
int indeg[MAXN], outdeg[MAXN]; // 入度和出度
int main()
{
cin >> n >> m;
// 读入边集
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
edge[u].push_back(v);
mat[u][i] = 1;
mat[v][i] = -1;
adj[u][v] = 1;
adj[v][u] = 1;
outdeg[u]++;
indeg[v]++;
}
// 输出关联矩阵
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout << mat[i][j] << " ";
}
cout << endl;
}
// 输出邻接矩阵
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << adj[i][j] << " ";
}
cout << endl;
}
// 输出顶点度数
for (int i = 1; i <= n; i++) {
cout << "Vertex " << i << ": ";
if (indeg[i] > 0) {
cout << "indeg = " << indeg[i] << ", ";
}
if (outdeg[i] > 0) {
cout << "outdeg = " << outdeg[i] << ", ";
}
cout << "deg = " << indeg[i] + outdeg[i] << endl;
}
return 0;
}
```
测试数据:
输入:
```
4 5
1 2
1 3
2 3
2 4
3 4
```
输出:
```
0 0 -1 1 0
1 -1 1 0 0
-1 1 0 1 -1
0 0 0 -1 1
Vertex 1: indeg = 0, outdeg = 2, deg = 2
Vertex 2: indeg = 1, outdeg = 2, deg = 3
Vertex 3: indeg = 2, outdeg = 1, deg = 3
Vertex 4: indeg = 2, outdeg = 0, deg = 2
```
输入:
```
5 7
1 2
1 3
2 3
2 4
3 2
4 5
5 4
```
输出:
```
0 0 -1 1 0 -1 1
1 -1 1 0 0 0 0
-1 1 0 1 -1 0 0
0 0 0 -1 1 1 0
0 0 0 0 0 -1 1
Vertex 1: indeg = 0, outdeg = 2, deg = 2
Vertex 2: indeg = 1, outdeg = 2, deg = 3
Vertex 3: indeg = 2, outdeg = 1, deg = 3
Vertex 4: indeg = 1, outdeg = 1, deg = 2
Vertex 5: indeg = 1, outdeg = 1, deg = 2
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)