采用邻接表存储结构如何求顶点的入度和出度c++
时间: 2023-09-24 14:01:00 浏览: 94
邻接表是一种图的存储结构,可以有效地表示图的结构和关系。在邻接表中,每个顶点v都对应一个链表,链表中存储了与顶点v相邻的顶点。
要求一个顶点v的入度,可以遍历邻接表,查找所有指向顶点v的边的个数。具体步骤如下:
1. 初始化一个变量count为0,用于计算入度。
2. 遍历图的所有顶点,对于每个顶点u,遍历其邻接表中的每个顶点w。
3. 如果顶点w与顶点v相等,即找到指向顶点v的边,将count加1。
4. 返回count作为顶点v的入度。
要求一个顶点v的出度,可以直接获取顶点v的邻接表的长度,即链表中顶点的个数。具体步骤如下:
1. 获取顶点v的邻接表链表长度,记为count。
2. 返回count作为顶点v的出度。
通过邻接表存储结构可以有效地求顶点的入度和出度,时间复杂度为O(|V|+|E|),其中|V|为顶点的个数,|E|为边的个数。
相关问题
邻接表求图的入度出度
邻接表是一种图的存储结构,可以用来表示有向图和无向图。在邻接表中,每个顶点都对应一个链表,链表中存储了该顶点所指向的其他顶点。邻接表可以用来求图的入度和出度。
求图的入度:对于有向图中的每个顶点,遍历整个邻接表,统计指向该顶点的边的数量即为该顶点的入度。
求图的出度:对于有向图中的每个顶点,遍历该顶点对应的链表,统计链表中边的数量即为该顶点的出度。
下面是C++代码实现:
```c++
#include <iostream>
using namespace std;
#define MaxSize 20
struct Node {
int weight;
int index;
struct Node *next;
};
struct HNode {
char nodeData;
struct Node *next;
};
struct Graph {
int vertexNum;
int arcNum;
bool isDireted;
HNode verList[MaxSize];
};
// 计算顶点v的入度
int getInDegree(Graph G, int v) {
int inDegree = 0;
for (int i = 0; i < G.vertexNum; i++) {
Node *p = G.verList[i].next;
while (p != NULL) {
if (p->index == v) {
inDegree++;
}
p = p->next;
}
}
return inDegree;
}
// 计算顶点v的出度
int getOutDegree(Graph G, int v) {
int outDegree = 0;
Node *p = G.verList[v].next;
while (p != NULL) {
outDegree++;
p = p->next;
}
return outDegree;
}
// 计算出度最大的顶点编号
int getMaxOutDegreeVertex(Graph G) {
int maxOutDegree = 0;
int maxOutDegreeVertex = -1;
for (int i = 0; i < G.vertexNum; i++) {
int outDegree = getOutDegree(G, i);
if (outDegree > maxOutDegree) {
maxOutDegree = outDegree;
maxOutDegreeVertex = i;
}
}
return maxOutDegreeVertex;
}
// 计算出度为0的顶点数
int getZeroOutDegreeVertexNum(Graph G) {
int zeroOutDegreeVertexNum = 0;
for (int i = 0; i < G.vertexNum; i++) {
int outDegree = getOutDegree(G, i);
if (outDegree == 0) {
zeroOutDegreeVertexNum++;
}
}
return zeroOutDegreeVertexNum;
}
int main() {
// 创建一个有向图
Graph G;
G.vertexNum = 5;
G.arcNum = 7;
G.isDireted = true;
for (int i = 0; i < G.vertexNum; i++) {
G.verList[i].nodeData = 'A' + i;
G.verList[i].next = NULL;
}
int arcs[7][2] = {{0, 1}, {0, 3}, {1, 2}, {1, 3}, {2, 4}, {3, 2}, {4, 3}};
for (int i = 0; i < G.arcNum; i++) {
int from = arcs[i][0];
int to = arcs[i][1];
Node *p = new Node;
p->index = to;
p->next = G.verList[from].next;
G.verList[from].next = p;
}
// 计算每个顶点的入度和出度
for (int i = 0; i < G.vertexNum; i++) {
cout << "顶点" << G.verList[i].nodeData << "的入度为:" << getInDegree(G, i) << endl;
cout << "顶点" << G.verList[i].nodeData << "的出度为:" << getOutDegree(G, i) << endl;
}
// 计算出度最大的顶点编号
int maxOutDegreeVertex = getMaxOutDegreeVertex(G);
cout << "出度最大的顶点编号为:" << maxOutDegreeVertex << endl;
// 计算出度为0的顶点数
int zeroOutDegreeVertexNum = getZeroOutDegreeVertexNum(G);
cout << "出度为0的顶点数为:" << zeroOutDegreeVertexNum << endl;
return 0;
}
```
数据结构 C++实现 有向图的邻接表存储,并输出 顶点的出度和入度
下面是一个简单的 C++ 实现,使用邻接表存储有向图,并输出每个顶点的出度和入度:
```cpp
#include <iostream>
#include <vector>
using namespace std;
class Graph {
private:
int V; // 图中顶点的数量
vector<vector<int>> adj; // 邻接表
public:
// 构造函数
Graph(int V) {
this->V = V;
adj.resize(V);
}
// 添加一条从 u 到 v 的边
void addEdge(int u, int v) {
adj[u].push_back(v);
}
// 输出每个顶点的出度和入度
void printDegree() {
for (int i = 0; i < V; i++) {
int out_degree = adj[i].size(); // 出度
int in_degree = 0; // 入度
// 计算入度
for (int j = 0; j < V; j++) {
for (auto k : adj[j]) {
if (k == i) {
in_degree++;
break;
}
}
}
cout << "顶点 " << i << " 的出度为 " << out_degree << ",入度为 " << in_degree << endl;
}
}
};
int main() {
// 创建图
Graph g(5);
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(3, 4);
// 输出每个顶点的出度和入度
g.printDegree();
return 0;
}
```
输出结果如下:
```
顶点 0 的出度为 1,入度为 1
顶点 1 的出度为 1,入度为 1
顶点 2 的出度为 1,入度为 1
顶点 3 的出度为 1,入度为 0
顶点 4 的出度为 0,入度为 1
```