已知邻接表的存储定义,试在此无向图的邻接表存储结构上实现图的基本操作createGraph,请参考十字链表的构造方法CrateDG的思路
时间: 2024-05-10 13:16:07 浏览: 107
邻接表的存储定义通常包括一个顶点数组和一个指向边链表的指针数组。邻接表中每一个链表的头结点都是一个存储顶点信息的结构体,其余节点则是存储边信息的结构体。邻接表的构建过程可以仿照十字链表的构造方法。
具体实现如下:
```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;
}
```
上述代码可以构建一个无向图,并输出其邻接表。可以根据需要修改构建方式,实现有向图和带权图的构建。
阅读全文