求有向图G中各顶点的入度与出度。建议分别采用邻接矩阵和邻接表这两种不同的存储结构完成。 输入格式: 首先输入一个正整数T,表示测试数据的组数,然后是T组测试数据。每组测试第一行输入2个整数n、m(2≤n≤26,1≤m≤n(n-1)/2),分别表示顶点数、边数;然后输入m行,每行包含两个顶点Ai、Bi(大写字母表示),表示Ai到Bi有一条有向边。 输出格式: 对于每组测试,输出n行,依顶点的字典序在每行上输出各顶点的入度和出度(数据之间留一个空格)。 输入样例: 1 5 4 A C A B B D E C 输出样例: 0 2 1 1 2 0 1 0 0 1
时间: 2024-04-01 10:37:50 浏览: 20
邻接矩阵与邻接表分别求解有向图中各个顶点的入度和出度的方法如下:
邻接矩阵:
1. 构建一个大小为 n*n 的邻接矩阵,其中 n 表示顶点数。
2. 对于每条有向边 (i,j),将邻接矩阵中第 i 行第 j 列的元素设为 1。
3. 统计每个顶点的入度和出度。对于第 i 个顶点,其入度为第 i 列中非零元素的个数,出度为第 i 行中非零元素的个数。
邻接表:
1. 构建一个大小为 n 的邻接表数组,其中 n 表示顶点数。
2. 对于每条有向边 (i,j),将顶点 i 的邻接表中加入一个指向 j 的边。
3. 统计每个顶点的入度和出度。对于第 i 个顶点,其入度为所有指向 i 的边的个数,出度为其邻接表的长度。
以下是代码实现:
相关问题
分别基于图的邻接矩阵存储结构和邻接表存储结构,编程求一个有向图G的指定顶点的入度和出度。即,输入一个有向图G,和它的一个顶点,输出这个顶点的入度和出度。
好的,这是一个比较基础的图论问题,我可以帮您解答。
首先,我们需要了解一下图的邻接矩阵和邻接表存储结构。
邻接矩阵存储结构是用一个二维数组来表示图中的所有顶点之间的关系。其中,数组中的每个元素都表示对应顶点之间的连通关系,如果存在连通关系,则为1,否则为0。
邻接表存储结构则是基于链表的数据结构,用来表示图中每个顶点和它的邻居顶点之间的关系。每个顶点对应一个链表,链表中存储了所有与该顶点相邻的顶点。
接下来,分别基于这两种存储结构,编写求指定顶点入度和出度的程序。
1. 邻接矩阵存储结构
我们可以先建立一个邻接矩阵,然后遍历该顶点所在的行和列,统计出度和入度。
具体代码如下:
```python
# 假设邻接矩阵为adj_matrix,顶点为v
def get_degree_adj_matrix(adj_matrix, v):
n = len(adj_matrix)
in_degree = 0
out_degree = 0
for i in range(n):
if adj_matrix[v][i] == 1: # 统计出度
out_degree += 1
if adj_matrix[i][v] == 1: # 统计入度
in_degree += 1
return in_degree, out_degree
```
2. 邻接表存储结构
对于邻接表存储结构,我们可以直接遍历该顶点对应的链表,统计出度和入度。
具体代码如下:
```python
# 假设邻接表为adj_list,顶点为v
def get_degree_adj_list(adj_list, v):
in_degree = 0
out_degree = 0
for node in adj_list[v]: # 统计出度
out_degree += 1
for i in range(len(adj_list)): # 统计入度
for node in adj_list[i]:
if node == v:
in_degree += 1
return in_degree, out_degree
```
希望能够帮助到您。
用java语言分别基于图的邻接矩阵存储结构和邻接表存储结构,编程求一个有向图G的指定顶点的入度和出度。即,输入一个有向图G,和它的一个顶点,输出这个顶点的入度和出度。
好的,这里提供基于Java语言的代码,分别使用邻接矩阵和邻接表存储结构实现求有向图G的指定顶点的入度和出度。
1. 邻接矩阵存储结构
```java
public class Graph {
private int[][] adjMatrix; // 邻接矩阵
private int vertexNum; // 顶点数
public Graph(int vertexNum) {
this.vertexNum = vertexNum;
adjMatrix = new int[vertexNum][vertexNum];
}
// 添加边
public void addEdge(int v1, int v2) {
adjMatrix[v1][v2] = 1;
}
// 获取指定顶点的出度和入度
public void getDegree(int v) {
int inDegree = 0;
int outDegree = 0;
for (int i = 0; i < vertexNum; i++) {
if (adjMatrix[v][i] == 1) { // 统计出度
outDegree++;
}
if (adjMatrix[i][v] == 1) { // 统计入度
inDegree++;
}
}
System.out.println("Vertex " + v + " has an in-degree of " + inDegree + " and an out-degree of " + outDegree);
}
}
```
2. 邻接表存储结构
```java
import java.util.ArrayList;
import java.util.List;
public class Graph {
private List<List<Integer>> adjList; // 邻接表
private int vertexNum; // 顶点数
public Graph(int vertexNum) {
this.vertexNum = vertexNum;
adjList = new ArrayList<>();
for (int i = 0; i < vertexNum; i++) {
adjList.add(new ArrayList<>());
}
}
// 添加边
public void addEdge(int v1, int v2) {
adjList.get(v1).add(v2);
}
// 获取指定顶点的出度和入度
public void getDegree(int v) {
int inDegree = 0;
int outDegree = 0;
for (int i = 0; i < vertexNum; i++) {
List<Integer> neighbors = adjList.get(i);
for (int neighbor : neighbors) {
if (neighbor == v) { // 统计入度
inDegree++;
}
}
if (i == v) { // 统计出度
outDegree = neighbors.size();
}
}
System.out.println("Vertex " + v + " has an in-degree of " + inDegree + " and an out-degree of " + outDegree);
}
}
```
希望能够帮助到您。