MyDataStructureHomework/week7/ADTGraph.cpp at master · AtomFirst/MyDataStructureHomework · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#ifndef _ADTGRAPH
#define _ADTGRAPH 1

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

typedef int status;
#define OK 1
#define ERROR 0
#define OVERFLOW -1

class Graph{
public:
    Graph(int maxn=200):maxn(maxn),val(new int[maxn+1]),vis(new bool[maxn+1]){
        adj = new int*[maxn+1];
        for(int i=0; i<=maxn; i++)
            adj[i] = new int[maxn+1];
    }
    Graph(initializer_list<pair<int,int>>edge){
        maxn = 0;
        for(auto [u,v]:edge)
            maxn = max(maxn, max(u,v));
        maxn;
        val = new int[maxn+1];
        vis = new bool[maxn+1];
        adj = new int*[maxn+1];
        for(int i=0; i<=maxn; i++)
            adj[i] = new int[maxn+1];
        for(auto [u,v]:edge)
            adj[u][v] = adj[v][u] = 1;
    }
    Graph(const Graph& g){
        maxn = g.maxn;
        val = new int[maxn+1];
        vis = new bool[maxn+1];
        adj = new int*[maxn+1];
        for(int i=0; i<=maxn; i++){
            adj[i] = new int[maxn+1];
            for(int j=0; j<=maxn; j++)
                adj[i][j] = g.adj[i][j];
        }
    }
    ~Graph(){
        delete[] val;
        for(int i=0; i<=maxn; i++)
            delete[] adj[i];
        delete[] adj;
    }
    int getVex(int i){
        return val[i];
    }
    int firstAdjVex(int i){
        for(int j=1; j<=maxn; j++)
            if(adj[i][j])
                return j;
        return -1;
    }
    int nextAdjVex(int i, int j){
        for(int k=j+1; k<=maxn; k++)
            if(adj[i][k])
                return k;
        return -1;
    }
    void dfsTraverse(int i,auto&& work){
        memset(vis,0,sizeof(bool)*maxn);
        dfs(i,work);
    }
    void bfsTraverse(int i,auto&& work){
        memset(vis,0,sizeof(bool)*maxn);
        queue<int>q;
        q.push(i);
        vis[i] = true;
        while(!q.empty()){
            int u = q.front(); q.pop();
            work(u);
            for(int j=firstAdjVex(u); j!=-1; j=nextAdjVex(u,j))
                if(!vis[j]){
                    q.push(j);
                    vis[j] = true;
                }
        }
    }
    void insertVex(int i,int v){
        val[i] = v;
    }
    void insertArc(int i,int j,bool undirected=false){
        adj[i][j] = 1;
        if(undirected)
            adj[j][i] = 1;
    }
    void deleteVex(int i){
        val[i] = 0;
        for(int j=1; j<=maxn; j++)
            adj[i][j] = 0;
        for(int j=1; j<=maxn; j++)
            adj[j][i] = 0;
    }
    void deleteArc(int i,int j,bool undirected=false){
        adj[i][j] = 0;
        if(undirected)
            adj[j][i] = 0;
    }
    int size(){
        return maxn;
    }
private:
    void dfs(int i,auto&& work){
        vis[i] = true; work(i);
        for(int j=firstAdjVex(i); j!=-1; j=nextAdjVex(i,j))
            if(!vis[j])
                dfs(j,work);
    }

    int maxn;
    int* val;
    int** adj;
    bool* vis;
};

#endif