图

数据结构-图的基本操作(邻接矩阵存储)

来自这个

https://www.bilibili.com/video/BV1pA411G7xX/?spm_id_from=333.788&vd_source=d84f08a0531e04d6d41c38180cce9fb5

#include <iostream>
#include <queue>
#define MAXVEX 20
#define INF 99
using namespace std;
//面向对象的方法
class MGraph {
public:
    //初始化
    void Init() {
        for (int i = 0; i < MAXVEX; i++) {
            Visited[i] = 0;
            for (int j = 0; j < MAXVEX; j++) {
                arc[i][j] = INF;
            }
        }
    }
    //Visited数组初始化
    void InitVisited() {
        for (int i = 0; i < MAXVEX; i++)
            Visited[i] = 0;
    }
    //创建邻接矩阵
    void Create() {
        int i, j, k, w;
        cout << "Please enter the number of vertices and edges:" << endl;
        cin >> vexnum >> edgenum;
        cout << "Please enter vertex information:" << endl;
        for (i = 0; i < vexnum; i++) {
            Vertex[i] = i;    //存储序号
            cin >> Vername[i];//输入顶点名字
        }
        for (k = 0; k < edgenum; k++) {
            cout << "Please enter the subscripts i, j and weight w of the edge (vi, vj):";
            cin >> i >> j >> w;
            arc[i][j] = arc[j][i] = w;
        }
    }
    //输出邻接矩阵
    void Print() {
        cout << "Adjacency matrix:" << endl;
        for (int i = 0; i < vexnum; i++) {
            for (int j = 0; j < vexnum; j++)
                printf("%4d", arc[i][j]);
            cout << endl;
        }
    }
    //返回顶点在图的位置
    int LocateVex(char ch) {
        int i;
        for (i = 0; i < vexnum; i++) {
            if (Vername[i] == ch)
                break;
        }
        if (i == vexnum) return -1;
        else
            return i;
    }
    //增加某个顶点
    void InsertVex(char ch) {
        Vername[vexnum] = ch;
        Vertex[vexnum] = vexnum;
        vexnum++;//别忘了顶点数自增
    }
    //删除某个顶点
    void DeleteVex(char ch) {
        int i, j, k;
        //遍历寻找节点位置
        for (i = 0; i < vexnum; i++) {
            if (Vername[i] == ch) break;
        }
        //Vername数组循环左移
        for (j = i + 1; j < vexnum; j++) {
            Vername[j - 1] = Vername[j];//覆盖
            Vertex[j - 1] = Vertex[j];  //覆盖
        }
        //arc数组循环左移和上移
        //上移
        for (j = i + 1; j < vexnum; j++)
            for (k = 0; k < vexnum; k++) {
                arc[j - 1][k] = arc[j][k];//覆盖
            }
        //左移
        for (j = 0; j < vexnum - 1; j++)
            for (k = i + 1; k < vexnum; k++) {
                arc[j][k - 1] = arc[j][k];//覆盖
            }
        vexnum--;
    }
    //增加某条边
    void InsertEdge(int i, int j, int w) {
        arc[i][j] = arc[j][i] = w;
        edgenum++;//别忘了
    }
    //删除某条边
    void RemoveEdge(int i, int j) {
        arc[i][j] = arc[j][i] = INF;
        edgenum--;//别忘了
    }
    //返回第一个邻接顶点
    char FirstNeighbor(char ch) {
        int i;
        for (i = 0; i < vexnum; i++)
            if (Vername[i] == ch) break;
        int j;
        for (j = 0; j < vexnum; j++)
            if (arc[i][j] != INF) break;
        if (j == vexnum) return '\0';
        else
            return Vername[j];
    }

    //自己照着书上写的
    bool Adjacent(int i, int j) {
        return arc[i][j] != INF;
    }//O(1)
    //自己照着书上写的,下面是错的，不管了
    //    int *Neighbors(int i) {
    //        int arr[MAXVEX] = {0};
    //        for (int j = 0; j < vexnum; j++)
    //            if (arc[i][j] != INF)
    //                arr[j] = 1;
    //        return arr;
    //    }//

    //深度优先遍历
    void DFS(char ch) {
        //InitVisited();//这是递归写的，进入下一层的时候又会InitVisited(),导致循环。所以不能写InitVisited()
        int i;
        int l = LocateVex(ch);
        //        cout << "The current vertex position is: " << l << endl;
        cout << Vername[l] << " ";//输出当前顶点
        Visited[l] = 1;           //表示访问过该顶点
        for (i = 0; i < vexnum; i++) {
            if (Visited[i] == 0 && arc[l][i] != INF)
                DFS(Vername[i]);
        }
    }
    
    void DFSTraverse() {
        InitVisited();
        for (int i = 0; i < vexnum; i++)
            if (!Visited[i])
                DFSmyself(Vername[i]);
    }
    void DFSmyself(char ch) {
        int l = LocateVex(ch);
        visit(l);
        Visited[l] = 1;
        for (int i = 0;  i < vexnum; i++) {
            if (!Visited[i] && arc[l][i] != INF)
                DFSmyself(Vername[i]);
        }
    }
    
    //广度优先遍历
    void BFS(char ch) {
        queue<int> q;//定义队列
        int i;
        int l = LocateVex(ch);
        cout << Vername[l] << " ";//输出当前顶点， 访问初始顶点
        InitVisited();
        Visited[l] = 1;//表示访问过该顶点
        q.push(l);
        while (!q.empty()) {
            l = q.front();//获取对头 信息
            q.pop();
            for (i = 0; i < vexnum; i++) {
                if (Visited[i] == 0 && arc[l][i] != INF) {
                    cout << Vername[i] << " ";//输出当前顶点， 访问初始顶点
                    Visited[i] = 1;           //表示访问过该顶点
                    q.push(i);
                }
            }
        }
    }
    //自己写一遍广度优先遍历，而且是完全版ben，便利所有连通分量
    void BFSTraverse() {
        InitVisited();
        queue<int> q;
        for (int i = 0; i < vexnum; i++)
            if (!Visited[i])
                BFSmyself(Vername[i], q);

    }


    void BFSmyself(char ch, queue<int> &q) {
        /*InitVisited();*/
        //queue<int> q;//队列放的是顶点数组的下标
        int l = LocateVex(ch);//ch是我们输入的，要便利的第一个节点，也就是出发的节点
        visit(l);
        Visited[l] = 1;
        q.push(l);//这三部经典操作
        while (!q.empty()) {
           /* DeQueue(q, l);*/
            l = q.front();
            q.pop();//stl里面pop是void的类型，不返回出队元素，考研里面Dequeue返回出队元素。
            for (int i = 0; i < vexnum; i++) {
                if (!Visited[i] && arc[l][i] != INF) {
                    visit(i);
                    Visited[i] = 1;
                    q.push(i);//这三部经典操作
                }
            }
        }
    }
    void visit(int l ) {
        printf("%c  ", Vername[l]);//不是%d

    }
private:
    int Vertex[MAXVEX];     //存储结点的序号
    char Vername[MAXVEX];   //存储结点的名字
    int arc[MAXVEX][MAXVEX];//邻接矩阵
    int vexnum;             //顶点数
    int edgenum;            //边数
    int Visited[MAXVEX];    //是否访问过
};
int main() {
    MGraph MyGraph;
    MyGraph.Init();
    MyGraph.Create();
    MyGraph.Print();

    //    //增加顶点
    //    char ch;
    //    cout << "Please enter the vertex information to be added:";
    //    cin >> ch;
    //    MyGraph.InsertVex(ch);
    //    MyGraph.Print();
    //    //删除顶点
    //    cout << "Please enter the vertex information to be deleted:";
    //    cin >> ch;
    //    MyGraph.DeleteVex(ch);
    //    MyGraph.Print();
    //
    //    //返回第一个邻接顶点
    //    cout << "Please enter the vertex you are looking for:";
    //    cin >> ch;
    //    ch = MyGraph.FirstNeighbor(ch);
    //    if (ch == '\0') cout << "is not exist FirstNeighbor" << endl;
    //    else
    //        cout << "FirstNeighbor is: " << ch << endl;


    //深度优先遍历R
    /*cout << "Please enter the information of the starting point:";
    char ch;
    cin >> ch;*/
    cout << "depth first traversal:" << endl;
    MyGraph.DFSTraverse();
    cout << endl;

    //广度优先遍历
    //cout << "Please enter the information of the starting point:";
    //    char ch;
    //cin >> ch;
    cout << "B first traversal:" << endl;
    MyGraph.BFSTraverse();
    cout << endl;



    return 0;
}

测试

11 13
a b c d e f g h i j k
0 1 1
0 4 1
1 5 1
2 5 1
2 6 1
2 3 1
3 6 1
3 7 1
5 6 1
6 7 1
8 9 1
8 10 1
9 10 1

注

用Clion不能把测试全部复制进去，要一行一行复制

用Visual Studio 2022就可以全部复制

后续会更新的