已知图的邻接表存储结构定义及建立图的邻接表、输出邻接表等函数均已定义(详见ljb.h文件);图的邻接矩阵存储结构定义及建立图的邻接矩阵、输出邻接矩阵等函数均已定义(详见ljjz.h文件),完成下面的实验题。 1. 编写程序输出以邻接表为存储结构的无向图的各顶点的度。
时间: 2024-04-30 12:18:14 浏览: 184
以下是实现代码:
```c++
#include "ljb.h" // 邻接表存储结构相关的头文件
int main() {
ALGraph G;
CreateGraph(G); // 建立无向图的邻接表存储结构
for (int i = 0; i < G.vexnum; i++) {
int degree = 0;
ArcNode *p = G.vertices[i].firstarc;
while (p) {
degree++;
p = p->nextarc;
}
printf("顶点 %d 的度为 %d\n", i, degree);
}
return 0;
}
```
首先,我们需要用 `CreateGraph` 函数来建立无向图的邻接表存储结构。然后,我们遍历每个顶点,计算它的度。具体来说,我们从该顶点的第一个邻接点开始,一直遍历到最后一个邻接点,计算经过的邻接点数量,即为该顶点的度。最后,我们输出每个顶点的度即可。
相关问题
1)图的邻接矩阵定义及实现: 定义图的邻接矩阵存储结构,并编写图的初始化、建立图、输出图、深度优先遍历、计算并输出图中每个顶点的度等基本操作实现函数。以下两图为例,建立一个验证操作实现的主函数进行测试。 (2)图的邻接表的定义及实现: 定义图的邻接表存储结构,并编写图的初始化、建立图、输出图、广度优先遍历、计算并输出图中每个顶点的度等基本操作实现函数。同时在主函数中调用这些函数进行验证(以下两图为例)。
好的,我已经记录下来了您的问题。让我来回答您的第一个问题:
图的邻接矩阵定义及实现:
邻接矩阵是一种用于表示图形的数据结构,它使用一个二维数组来表示图形中的节点(顶点)之间的关系。如果图形中的两个节点之间存在边,则在邻接矩阵中相应的位置上填入1或者其他表示权重的值;如果两个节点之间不存在边,则在邻接矩阵中相应的位置上填入0。邻接矩阵的大小为n*n,其中n表示图形中节点(顶点)的数量。
以下是邻接矩阵的实现代码:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 100;
//邻接矩阵存储结构
struct Graph {
int n; //节点数
int m; //边数
int mat[MAXN][MAXN]; //邻接矩阵数组
} g;
//初始化邻接矩阵
void init(Graph& g) {
memset(g.mat, 0, sizeof(g.mat)); //将邻接矩阵数组全部赋值为0
g.n = g.m = 0;
}
//建立邻接矩阵
void create(Graph& g) {
cin >> g.n >> g.m; //输入节点数和边数
for (int i = 0; i < g.m; i++) {
int u, v;
cin >> u >> v; //输入一条边的两个端点
g.mat[u][v] = g.mat[v][u] = 1; //在邻接矩阵中设置相应的位置为1
}
}
//输出邻接矩阵
void print(Graph& g) {
for (int i = 0; i < g.n; i++) {
for (int j = 0; j < g.n; j++) {
cout << g.mat[i][j] << " ";
}
cout << endl;
}
}
//深度优先遍历
void dfs(Graph& g, int u, bool vis[]) {
vis[u] = true; //标记当前节点已经被访问过
cout << u << " "; //输出当前节点
for (int v = 0; v < g.n; v++) {
if (g.mat[u][v] && !vis[v]) { //如果u和v之间存在一条边,且v未被访问过
dfs(g, v, vis); //递归访问v
}
}
}
//计算节点的度
int degree(Graph& g, int u) {
int deg = 0;
for (int i = 0; i < g.n; i++) {
if (g.mat[u][i]) { //如果存在一条边
deg++;
}
}
return deg;
}
//计算并输出每个节点的度
void printDegree(Graph& g) {
for (int i = 0; i < g.n; i++) {
cout << "degree of node " << i << " is " << degree(g, i) << endl;
}
}
//主函数
int main() {
init(g); //初始化邻接矩阵
create(g); //建立邻接矩阵
print(g); //输出邻接矩阵
bool vis[MAXN] = { false };
dfs(g, 0, vis); //深度优先遍历
cout << endl;
printDegree(g); //计算并输出每个节点的度
return 0;
}
```
以上代码可以实现邻接矩阵的基本操作,您可以根据您需要进行相应的修改。
已知邻接表的存储定义,试在此无向图的邻接表存储结构上实现图的基本操作createGraph,请参考十字链表的构造方法CrateDG的思路
邻接表的存储定义通常包括一个顶点数组和一个指向边链表的指针数组。邻接表中每一个链表的头结点都是一个存储顶点信息的结构体,其余节点则是存储边信息的结构体。邻接表的构建过程可以仿照十字链表的构造方法。
具体实现如下:
```C++
#include<iostream>
#include<vector>
using namespace std;
struct EdgeNode{
int adjvex; // 邻接点编号
int weight; // 权重
EdgeNode* next; // 指向下一个邻接点
};
struct VertexNode{
int data; // 顶点信息
EdgeNode* firstEdge; // 指向第一个邻接点
};
class Graph{
public:
Graph(int n, vector<vector<int>> edges){ // n是顶点个数,edges是边的信息
this->n = n;
graph = new VertexNode[n]; // 初始化顶点数组
for(int i=0; i<n; i++){
graph[i].data = i; // 顶点信息初始化
graph[i].firstEdge = nullptr; // 指向第一个邻接点初始化
}
// 构建邻接表
for(auto edge:edges){
int u = edge[0], v = edge[1], weight = edge[2];
EdgeNode* newEdge1 = new EdgeNode{v, weight, graph[u].firstEdge};
graph[u].firstEdge = newEdge1;
EdgeNode* newEdge2 = new EdgeNode{u, weight, graph[v].firstEdge};
graph[v].firstEdge = newEdge2;
}
}
~Graph(){
for(int i=0; i<n; i++){
EdgeNode* edge = graph[i].firstEdge;
while(edge != nullptr){
EdgeNode* temp = edge->next;
delete edge;
edge = temp;
}
}
delete[] graph;
}
void printGraph(){ // 输出邻接表
for(int i=0; i<n; i++){
cout << i << " : ";
EdgeNode* edge = graph[i].firstEdge;
while(edge != nullptr){
cout << edge->adjvex << "(" << edge->weight << ") ";
edge = edge->next;
}
cout << endl;
}
}
private:
int n; // 顶点个数
VertexNode* graph; // 邻接表
};
int main(){
vector<vector<int>> edges = {{0,1,1}, {0,2,2}, {1,2,3}, {1,3,4}, {2,3,5}};
Graph g(4, edges);
g.printGraph();
return 0;
}
```
上述代码可以构建一个无向图,并输出其邻接表。可以根据需要修改构建方式,实现有向图和带权图的构建。
阅读全文