Question

c++中带权图的邻接表用stl怎么表示

c++中带权图的邻接表用stl怎么表示

Answer 1

#include <iostream>
using namespace std;
struct Node { //定义表结点
int adjvex; //该边所指向的顶点的位置
int weight;// 边的权值
Node *next; //下一条边的指针
};
struct HeadNode{ // 定义头结点
int nodeName; // 顶点信息
int inDegree; // 入度
Node *link; //指向第一条依附该顶点的边的指针
};
//G表示指向头结点数组的第一个结点的指针
//nodeNum表示结点个数
//arcNum表示边的个数
void createGraph(HeadNode *G, int nodeNum, int arcNum) {
cout << "开始创建图(" << nodeNum << ", " << arcNum << ")" << endl;
//初始化头结点
for (int i = 0; i < nodeNum; i++) {
G[i].nodeName = i+1; //位置0上面存储的是结点v1,依次类推
G[i].inDegree = 0; //入度为0
G[i].link = NULL;
}
for (int j = 0; j < arcNum; j++) {
int begin, end, weight;
cout << "请依次输入 起始边 结束边 权值: ";
cin >> begin >> end >> weight;
// 创建新的结点插入链接表
Node *node = new Node;
node->adjvex = end - 1;
node->weight = weight;
++G[end-1].inDegree; //入度加1
//插入链接表的第一个位置
node->next = G[begin-1].link;
G[begin-1].link = node;
}
}
void printGraph(HeadNode *G, int nodeNum) {
for (int i = 0; i < nodeNum; i++) {
cout << "结点v" << G[i].nodeName << "的入度为";
cout << G[i].inDegree << ", 以它为起始顶点的边为: ";
Node *node = G[i].link;
while (node != NULL) {
cout << "v" << G[node->adjvex].nodeName << "(权:" << node->weight << ")" << " ";
node = node->next;
}
cout << endl;
}
}
int main() {
HeadNode *G;
int nodeNum, arcNum;
cout << "请输入顶点个数，边长个数: ";
cin >> nodeNum >> arcNum;
G = new HeadNode[nodeNum];
createGraph(G, nodeNum, arcNum);
cout << G[0].nodeName << endl;
cout << "下面开始打印图信息..." << endl;
printGraph(G, nodeNum);
return 0;
}

Answer 2

引用我的小名叫仙女的回答：
#include <iostream>
using namespace std;
struct Node { //定义表结点
int adjvex; //该边所指向的顶点的位置
int weight;// 边的权值
Node *next; //下一条边的指针
};
struct HeadNode{ // 定义头结点
int nodeName; // 顶点信息
int inDegree; // 入度
Node *link; //指向第一条依附该顶点的边的指针
};
//G表示指向头结点数组的第一个结点的指针
//nodeNum表示结点个数
//arcNum表示边的个数
void createGraph(HeadNode *G, int nodeNum, int arcNum) {
cout << "开始创建图(" << nodeNum << ", " << arcNum << ")" << endl;
//初始化头结点
for (int i = 0; i < nodeNum; i++) {
G[i].nodeName = i+1; //位置0上面存储的是结点v1,依次类推
G[i].inDegree = 0; //入度为0
G[i].link = NULL;
}
for (int j = 0; j < arcNum; j++) {
int begin, end, weight;
cout << "请依次输入 起始边 结束边 权值: ";
cin >> begin >> end >> weight;
// 创建新的结点插入链接表
Node *node = new Node;
node->adjvex = end - 1;
node->weight = weight;
++G[end-1].inDegree; //入度加1
//插入链接表的第一个位置
node->next = G[begin-1].link;
G[begin-1].link = node;
}
}
void printGraph(HeadNode *G, int nodeNum) {
for (int i = 0; i < nodeNum; i++) {
cout << "结点v" << G[i].nodeName << "的入度为";
cout << G[i].inDegree << ", 以它为起始顶点的边为: ";
Node *node = G[i].link;
while (node != NULL) {
cout << "v" << G[node->adjvex].nodeName << "(权:" << node->weight << ")" << " ";
node = node->next;
}
cout << endl;
}
}
int main() {
HeadNode *G;
int nodeNum, arcNum;
cout << "请输入顶点个数，边长个数: ";
cin >> nodeNum >> arcNum;
G = new HeadNode[nodeNum];
createGraph(G, nodeNum, arcNum);
cout << G[0].nodeName << endl;
cout << "下面开始打印图信息..." << endl;
printGraph(G, nodeNum);
return 0;
}

这根本没有用stl，普通的链表实现而已