2021-1 从文件构造无向图 邻接表 指定节点边数生成随机图 c++

Graph API

必要的说明

• 算法第四版 人民邮电出版社，原书是java实现
• 节点内容只有一个整型数标识符ID，可以更清楚写typedef int ID
• 邻接表采用链表数组，头插法

耐人寻味的细节

• 邻接表在java里这样写Bag<Integer>[] adj,我想c++至少有这几种方法：

  一、固定大小的数组list<int> adj[MAX_V];

  二、灵活的数组vector<list<int>> adj;

  三、指针，内存在堆vector<list<int>>* adj; vector<list<int>*> adj; vector<list<int>*>* adj;

  哪个好呢？这里用了和原文不同的写法，用了第二种，但adj.emplace_back(*new list<int>());虽然链表还是在堆上开辟，但vector实体在函数栈内。

  严格说，和原文Bag<Integer>[] adj等价的写法是vector<list<int>*>* adj;图类的实例只保存一个指针，所有数据都在堆上申请，调用时需要用的指针或者解引，像adj->at(i)或(*adj)[i]有点麻烦。

  已修改，typedef list<int>* ListPtr; vector<ListPtr>* m_adj。

  测试实例如左图，开头两行是节点数和边数。
  

当构造函数再调用其他构造函数

JAVA是可以的，但是，C++似乎不行，所以，用一个私有函数完成构造函数的活儿。

package source;public class Hero {
    private int hp;private double damage;private String name;Hero(String name){
    this.name = name;}Hero(String name,int hp,double damage){
    this(name);//调用第一个构造函数this.hp = hp;this.damage = damage;}
}

Graph.h

#pragma once
#include<string>
#include<fstream>
#include<iostream>
#include<list>
#include<vector>
using namespace std;#define out(x) cout<<x<<" "
#define hh printf_s("\n")
#define random(x) rand()%(x)typedef  list<int>* ListPtr;/*********************如无必要，勿增实体************************/
class Graph
{
    public:Graph(int V);Graph(string file);//从文件读入图数据int V();int E();void addEdge(int v, int w);//向图中添加边v-w,顶点已存在list<int> adj(int v); // 和v相邻的所有顶点string toString();//对象的字符串表示private:int m_V=0;//节点数int m_E=0;//边数vector<ListPtr>* m_adj=nullptr;//邻接表void initGraph(int V);//创建一个有V个顶点但不含有边的图string intToStr(int n);bool isParallel_edges_self_loop(int v,int w);//检测平行边和自环
};void testG();
void setGraphTxt(int V,int E);//随机生成图的构造文件graph.txt

Graph.cpp

#include "Graph.h"Graph::Graph(int V)
{
    m_V = V;m_E = 0;m_adj = new vector<ListPtr>(V, nullptr);for (int i = 0; i < V; i++){
    m_adj->at(i) = new list<int>(0);}
}Graph::Graph(string file)
{
    ifstream in(file, ios::in);if (!in) {
    printf_s("file open error.");return;}in >> m_V;initGraph(m_V);int E = 0;in >> E;//不一定等于最后的边数，因为可能不包含自环和平行边int w, v;for (int i = 0; i < E; i++){
    in >> w >> v;addEdge(w, v);}in.close();
}int Graph::V()
{
    return m_V;
}int Graph::E()
{
    return m_E;
}void Graph::addEdge(int v, int w)
{
    if (isParallel_edges_self_loop(v, w)) return;m_adj->at(v)->push_front(w);m_adj->at(w)->push_front(v);++m_E;
}list<int> Graph::adj(int v)
{
    ListPtr p = m_adj->at(v);return *(p);
}string Graph::toString()
{
    string s = intToStr(m_V) + " vertices, " +intToStr(m_E) + " edges\n";for (int i = 0; i < m_V; i++){
    s += intToStr(i) + ": ";for(auto adj:*(m_adj->at(i))){
    s += intToStr(adj) + " ";}s += "\n";}return s;
}void
inline Graph::initGraph(int V)
{
    m_V = V;m_E = 0;m_adj = new vector<ListPtr>(V, nullptr);for (int i = 0; i < V; i++){
    m_adj->at(i)= new list<int>(0);}
}string 
inline Graph::intToStr(int n)
{
    char int_s[20] = {
     0 };//末尾加上'\0'_itoa_s(n, int_s, 10);// 10 表示十进制return string(int_s);
}bool Graph::isParallel_edges_self_loop(int v,int w)
{
    if (v == w) return true;for (auto& n : *(m_adj->at(v))) {
    if (n == w) {
    return true;}}return false;
}void GFile(int V, int E)
{
    //指定节点边数生成随机图 ofstream write("graph.txt");if (!write) {
    out("file opens error !"), hh;return;}write << V << endl;write << E << endl;srand((unsigned)time(0));for (int i = 0; i < E; ++i) {
    int from = random(V);int to = random(V);write << from << " " << to << endl;}write.close();
}void testG()
{
    GFile(19, 135);Graph G("graph.txt");cout << (G.toString()) << endl;
}

data.txt

13
13
0 1
0 2
0 5
0 6
5 3
5 4
3 4
4 6
7 8
9 10
9 11
9 12
11 12

补充

• 注意对非法数据的处理，边数和顶点数非负

• 节点i的度数，m_adj->at(i)->size()