C++用邻接表实现图

//file: Arc.h
#ifndef UNTITLED_ARC_H
#define UNTITLED_ARC_H
//图的边
class Arc{
public:
    int vexIndex;//保持节点的下标值
    double weight;//边的权重值
    Arc* next;//指向下一条边
public:
    Arc();
};

Arc::Arc() {
    this->weight = 0;
    this->next = nullptr;
    this->vexIndex = -1;//空
}

#endif //UNTITLED_ARC_H

//file: Node.h
#ifndef UNTITLED_NODE_H
#define UNTITLED_NODE_H
/*说明：
 * 节点的边插入是按顺序插入的，这样查找的时候只有找到大于或空就可以停止了。
 */
#include "Arc.h"
//图节点
class Node{
public:
    double data;//节点值
    Arc *first;//指向下一个节点
public:
    Node();//构造函数
    ~Node();//释放内存
    bool searchArc(int x);//搜索本节点中是否有指向x节点的指针
    void deleteAllArc();//删除所有的边
    bool deleteArc(int x);//删除node中指向x的边
    bool insertArc(int x, double w = 0);//插入边
    bool setWeight(int x, double v);//设置指向x的边的权值
    Arc *searchNext(int x);//搜索边x的下一条边
    bool modifyVex(int x, int y);//修改节点中指向x的节点变成指向y的节点
    Node &operator=(const Node &n);//拷贝复制函数
};

//构造函数
Node::Node() {
    this->first = nullptr;
    this->data = 0;
}
//释放内存
Node::~Node() {
    Arc *p = this->first;
    Arc *q = nullptr;
    while (p) {
        q = p->next;
        delete p;
        p = q;
    }
}
//搜索本节点中是否有指向x节点的指针
bool Node::searchArc(int x) {
    Arc *p = this->first;
    while (p){
        if (p->vexIndex == x)
            return true;
        else
            p = p->next;
    }
    return false;
}
//删除所有的边
void Node::deleteAllArc() {
    Arc *p = this->first;
    Arc *q = nullptr;
    while (p){
        q = p->next;
        delete p;
        p = q;
    }
    this->first = nullptr;
    this->data = 0;
}
//删除指向x的边
bool Node::deleteArc(int x) {
    Arc *p = this->first;
    Arc *q = nullptr;
    if (!p) {
        return false;
    }
    if (p->vexIndex == x) {
        this->first = p->next;
        delete p;
        return true;
    }
    while (p) {
        if (p->next != nullptr && p->next->vexIndex == x) {
            q = p->next->next;
            delete p->next;
            p->next = q;
            return true;
        }
        else
            p = p->next;
    }
    return false;
}

//插入边->x
bool Node::insertArc(int x, double w) {
    Arc *p = first;
    if (!p) {
        first = new Arc;
        first->next = nullptr;
        first->weight = w;
        first->vexIndex = x;
        return true;
    }

    p = first;
    Arc *q = p->next;
    while (p) {
        if (!q) {
            q = new Arc;
            q->next = nullptr;
            q->weight = w;
            q->vexIndex = x;
            p->next = q;
            return true;
        }
        else if (q->vexIndex == x){
            return false;
        }
        else if (q->vexIndex > x){
            q = new Arc;
            q->weight = w;
            q->vexIndex = x;
            q->next = p->next;
            p->next = q;
            return true;
        } else{
            p = p->next;
            q = p->next;
        }
    }
    return false;
}

//插入权值
bool Node::setWeight(int x, double v) {
    Arc *p = this->first;
    while (p){
        if (p->vexIndex == x) {
            p->weight = v;
            return true;
        } else
            p = p->next;
    }
    return false;
}

//搜索边x的下一条边
Arc *Node::searchNext(int x) {
    Arc *p = this->first;
    while (p){
        if (p->vexIndex == x)
            return p->next;
        else
            p = p->next;
    }
    return nullptr;
}

//修改节点中指向x的节点变成指向y的节点
bool Node::modifyVex(int x, int y) {
    Arc *p = this->first;
    while (p) {
        if (p->vexIndex == x) {
            p->vexIndex = y;
            return true;
        }
        else
            p = p->next;
    }
    return false;
}

//拷贝复制函数
Node &Node::operator=(const Node &n) {
    //清空内存
    deleteAllArc();
    //分配空间并复制
    this->data = n.data;
    Arc *p = n.first;//指向n的指针
    Arc *q;//指向this的指针
    if(p) {//处理头节点
        q = new Arc;
        q->weight = p->weight;
        q->vexIndex = p->vexIndex;
        this->first = q;
        p = p->next;
    }
    while (p) {//连续处理
        q->next = new Arc;
        q = q->next;
        q->weight = p->weight;
        q->vexIndex = p->vexIndex;
        p = p->next;
    }
    q->next = nullptr;//尾指针置空
    return *this;//返回this指针
}
#endif //UNTITLED_NODE_H

//file: Graph.h
#ifndef NETWORK_H
#define NETWORK_H
#include <iostream>

//自定义头文件
#include "Arc.h"
#include "Node.h"
#include "Stack.h"
#include "Queue.h"
using namespace std;

class Graph{
public:
    Node *Network;//邻接表
    int vexNums;//顶点数
    int arcNums;//弧数
    int maxVexNums;//最大可用节点数

public:
    Graph(int inputMaxVexNums = 20);//构造函数
    ~Graph();//析构函数

    //图的基本操作
    int firstEdge(int x);//返回节点x的第一个邻接点
    int nextEdge(int x, int y);//返回边x->y的下一个下一个邻接点
    int locateVerPos(int x);//得到值为x的节点下标
    int reArcNums(int x);//返回节点x的弧数
    double getWeight(int x, int y);//得到边的权值x-y
    bool adjacent(int x, int y);//判断节点x和y之间是否有边？
    bool insertVertex(int x);//在图g中插入节点x
    bool removeVertex(int x);//删除节点x
    bool insertEdge(int x , int y);//在节点x和y之间插入边: x->y
    bool removeEdge(int x, int y);//删除边: x->y
    void inputGraph();//手动输入建立图
    void outputGraph(bool vision = true) const;//打印输出整个图
    void modifySize(int inputMaxVexNums);//调整网络大小
    void BFSTraverse();//广度优先遍历
    void DFSTraverse();//深度优先遍历
    void visit(int i);//优先遍历访问节点输出函数
    friend ofstream &operator<<(ofstream &out, Graph &g);//<<输出图
    void bfs(Queue<int>&q, int x, bool *visited);
    void dfs(int x, bool *visited);
};

//构造函数
Graph::Graph(int inputMaxVexNums) {
    Network = new Node[inputMaxVexNums];
    if(!Network)
        cerr << "Graph() 构造函数分配空间失败!\n";
    maxVexNums = inputMaxVexNums;
    arcNums = 0;
    vexNums = 0;
}

//析构函数
Graph::~Graph(){
    delete [] Network;
    maxVexNums = 0;
}

//调整网络大小
void Graph::modifySize(int inputMaxVexNums) {
    if(Network && inputMaxVexNums) {//非空析构
        delete[] Network;
    }
    if (inputMaxVexNums && !Network)//非0分配
        Network = new Node[inputMaxVexNums];
    if(Network)
        cerr << "modifySize() 分配空间失败!\n";
    maxVexNums = inputMaxVexNums;
    arcNums = 0;
    vexNums = 0;
}

//返回边的权值x->y，没找到返回-1
double Graph::getWeight(int x, int y) {
    Arc *p = this->Network[x].first;
    while (p){
        if (p->vexIndex == y)
            return p->weight;
    }
    return -1;//没找到
}

//返回x->y是否存在？
bool Graph::adjacent(int x, int y) {
    if (x >= 0 && x < this->vexNums) {
        Node *p = &this->Network[x];
        return p->searchArc(y);
    }
    else
        return false;
}

//在节点x和y之间插入边: x->y
bool Graph::insertEdge(int x, int y) {
    if (x >= this->vexNums || y >= this->vexNums)
        return false;
    bool r = Network[x].insertArc(y);
    if(r)
        arcNums++;
    return r;
}

//删除边: x->y
bool Graph::removeEdge(int x, int y) {
    if (x >= this->vexNums || y >= this->vexNums)
        return false;
    bool r = this->Network[x].deleteArc(y);
    if (r) {
        arcNums--;
    }
    return true;
}

//返回节点x的弧数
int Graph::reArcNums(int x) {
    Arc *p = Network[x].first;
    int r = 0;
    while (p){
        ++r;
        p = p->next;
    }
    return r;
}
//返回节点x的第一个邻接点
int Graph::firstEdge(int x) {
    if(!Network[x].first)
        return -1;
    else
        return Network[x].first->vexIndex;
}

//int nextEdge(int x, int y);//返回边x->y的下一个下一个邻接点
int Graph::nextEdge(int x, int y) {
    if (x >= this->vexNums || y >= this->vexNums)
        return -1;
    Node *p = &this->Network[x];
    Arc *t = p->searchNext(y);
    if (!t)
        return -1;
    else
        return t->vexIndex;
}

//返回值为x的节点下标
int Graph::locateVerPos(int x) {
    for (int i = 0; i < vexNums; ++i) {
        if (Network[i].data == x){
            return i;
        }
    }
    cerr << "没有这个节点\n";
    return -1;
}

//<<输出图
ofstream &operator<<(ofstream &out, Graph &g) {
    g.outputGraph();
    return out;
}

//打印输出整个图
void Graph::outputGraph(bool vision) const {
    cout << "打印图，结果如下：(1-0-2)表示1->2且权重为0)\n" << "顶点数：" << vexNums << endl;
    cout << "边数：" << arcNums << endl;
    for (int i = 0; i < vexNums; ++i) {
        cout << "[Node: " << i
        << "] data: " << Network[i].data
        << " arc: " << " [" ;
        Arc *p = Network[i].first;
        int flag = 1;//控制输出的空格
        while (p){
            if (flag) {
                cout << "(" << Network[i].data << "-";
                if (vision) {
                    cout << p->weight << "-";
                }
                cout << Network[p->vexIndex].data << ")";
                p = p->next;
                flag = 0;
            } else{
                cout << " (" << Network[i].data << "-";
                if (vision) {
                    cout << p->weight << "-";
                }
                cout << Network[p->vexIndex].data << ")";
                p = p->next;
            }

        }
        cout << "]" << endl;
    }
}

//手动输入建立图
void Graph::inputGraph() {
    //通过从输入流对象in输入n的顶点和e条五项边的信息建立邻接矩阵表示的图G。邻接矩阵初始化工作在构造函数完成
    int t, n, m;
    cout << "请输入顶点数: " << endl;
    cin >> n; //输入点数n
    if (n > maxVexNums) {
        cerr << "你输入的节点数超过了最大可接受节点数，请重新输入" << endl;
        cin >> n;
    }

    Graph graphNet(n);
    cout << "请依次输入顶点值: " << endl;
    for (int i = 0; i < n; ++i) {
        cin >> t;
        this->Network[i].data = t;
        vexNums++;
    }
    cout << "请输入边数：" << endl;
    cin >> m;
    if (m > (vexNums - 1) * vexNums) {
        cerr << "你输入的边数数超过了最大可接受边数，请重新输入" << endl;
        cin >> m;
    }
    cout << "请依次输入边：（形如 v1 v2，其中v1和v2是节点的值!）" << endl;
    while (m){
        cin >> t >> n;
        int a = locateVerPos(t);
        int b = locateVerPos(n);
        if(a==-1 || b==-1)
            continue;
        Network[a].insertArc(b);
        arcNums++;
        m--;
    }
}

//在图g中插入节点x
bool Graph::insertVertex(const int x) {
    if (vexNums == maxVexNums)
        return false;//满了
    Network[vexNums++].data = x;
    return true;
}

//删除节点x
bool Graph::removeVertex(int x) {
    if (x >= vexNums || x >= maxVexNums) {
        cerr << "removeVertex(x)中的x输入超过界限!\n";
        return false;
    }
    cout << "removeVertex start" << endl;
    //删除与节点x相连的边
    for (int i = 0; i < vexNums; ++i) {
       bool r = Network[i].deleteArc(x);
       if (r){
           cout << "node: " << i << " deleteArc ok : " << x << endl;
           cout << "arcNums = " << arcNums << endl;
           --arcNums;
       }
    }
    //删除x发出的边
    //this->Network[x].deleteAllArc();//node的拷贝构造会清空就不用重复了

    //调整其他节点
    int r = vexNums-1;
    int l = reArcNums(x);
    this->Network[x] = this->Network[r];//拷贝复制最后一个节点
    Network[r].deleteAllArc();//删除最后一个节点
    arcNums = arcNums - l;//更新弧数
    cout << "arcNums = " << arcNums << " reArcNums = " << l << endl;
    vexNums--;//节点数减一

    //将原来指向r的调整为指向x
    for (int j = 0; j < vexNums; ++j) {
        Network[j].modifyVex(r, x);
    }

    cout << "removeVertex end" << endl;
    return true;
}

//优先遍历访问节点输出函数
void Graph::visit(int i) {
    cout << " data = " << i << endl;
}

//广度优先遍历
void Graph::BFSTraverse() {
    bool visited[vexNums];
    memset(visited, 0, sizeof(visited));
    Queue<int> queue;

    for (int i = 0; i < vexNums; ++i) {
        if(!visited[i])
            bfs(queue, i, visited);
    }
}
void Graph::bfs(Queue<int>&q, int x, bool *visited) {
    visit(x);
    visited[x] = true;
    q.push(x);
    while (q.empty()){
        int i = q.pop();
        for (int j = firstEdge(i); j >= 0; j = nextEdge(i, j)) {
            if(!visited[j]){
                visit(j);
                visited[j] = true;
                q.push(j);
            }
        }
    }
}

//深度优先遍历
void Graph::DFSTraverse() {
    bool visited[vexNums];
    memset(visited, 0, sizeof(visited));

    for (int i = 0; i < vexNums; ++i) {
        if(!visited[i])
            dfs(i, visited);
    }
}
void Graph::dfs(int x, bool *visited) {
    visit(x);
    visited[x] = true;
    for (int i = firstEdge(x); i >= 0; i = nextEdge(x, i)) {
        if (!visited[i])
            dfs(i, visited);
    }
}

#endif

#include <iostream>
#include "Graph.h"
using namespace std;

int main(){
    int a, b;
    Graph graphNet(5);//ok
    graphNet.inputGraph();//ok
    graphNet.outputGraph(false);//ok

    cout << "输入要删除的边："<< endl;
    cin >> a >> b;
    graphNet.removeEdge(a, b);//ok
    graphNet.outputGraph(false);

    cout << "输入要删除的节点:" <<endl;
    cin >> a;
    graphNet.removeVertex(a);//ok
    graphNet.outputGraph(false);

    graphNet.BFSTraverse();

    bool visited[graphNet.vexNums];
    memset(visited, 0, sizeof(visited));
    graphNet.BFSTraverse();

    graphNet.DFSTraverse();
}

C:\User\Project\untitled\cmake-build-debug\untitled.exe
请输入顶点数:
5
请依次输入顶点值:
1 2 3 4 5
请输入边数：
10
请依次输入边：（形如 v1 v2，其中v1和v2是节点的值!）
2 1
3 2
5 1
5 2
5 3
5 4
4 1
4 2
4 3
3 4
打印图，结果如下：(1-0-2)表示1->2且权重为0)
顶点数：5
边数：10
[Node: 0] data: 1 arc:  []
[Node: 1] data: 2 arc:  [(2-1)]
[Node: 2] data: 3 arc:  [(3-2) (3-4)]
[Node: 3] data: 4 arc:  [(4-1) (4-2) (4-3)]
[Node: 4] data: 5 arc:  [(5-1) (5-2) (5-3) (5-4)]
输入要删除的边：
1 0
打印图，结果如下：(1-0-2)表示1->2且权重为0)
顶点数：5
边数：9
[Node: 0] data: 1 arc:  []
[Node: 1] data: 2 arc:  []
[Node: 2] data: 3 arc:  [(3-2) (3-4)]
[Node: 3] data: 4 arc:  [(4-1) (4-2) (4-3)]
[Node: 4] data: 5 arc:  [(5-1) (5-2) (5-3) (5-4)]
输入要删除的节点:
0
removeVertex start
node: 3 deleteArc ok : 0
arcNums = 9
node: 4 deleteArc ok : 0
arcNums = 8
arcNums = 7 reArcNums = 0
removeVertex end
打印图，结果如下：(1-0-2)表示1->2且权重为0)
顶点数：4
边数：7
[Node: 0] data: 5 arc:  [(5-2) (5-3) (5-4)]
[Node: 1] data: 2 arc:  []
[Node: 2] data: 3 arc:  [(3-2) (3-4)]
[Node: 3] data: 4 arc:  [(4-2) (4-3)]
 data = 0
 data = 1
 data = 2
 data = 3
 data = 0
 data = 1
 data = 2
 data = 3
 data = 0
 data = 1
 data = 2
 data = 3

Process finished with exit code 0