图的存储与遍历实验报告

实验题目：图的存储与遍历

实验目的：
1. 掌握图的存储方法
2. 掌握图的遍历方法

实验内容：
1. 采用邻接矩阵和邻接表两种方式存储图，并实现图的基本操作，如插入节点、插入边、删除节点、删除边等。
2. 实现图的深度优先遍历和广度优先遍历算法，并在程序中展示遍历结果。

实验步骤：
1. 选择合适的编程语言，如C++或Java。
2. 实现邻接矩阵存储图的基本操作，如插入节点、插入边、删除节点、删除边等。
3. 实现邻接表存储图的基本操作，如插入节点、插入边、删除节点、删除边等。
4. 实现图的深度优先遍历算法。
5. 实现图的广度优先遍历算法。
6. 调用以上实现的函数，展示遍历结果。

实验结果：
我们采用C++语言实现了图的存储和遍历操作，具体实现如下：

1. 邻接矩阵存储图的基本操作

const int MAXN = 100;
int G[MAXN][MAXN]; //邻接矩阵存储图
int n, m; //节点数和边数

//插入节点
void add_node(int x) {
    n++;
}

//删除节点
void del_node(int x) {
    for (int i = 1; i <= n; i++) {
        G[i][x] = G[x][i] = 0;
    }
    n--;
}

//插入边
void add_edge(int u, int v) {
    G[u][v] = G[v][u] = 1;
    m++;
}

//删除边
void del_edge(int u, int v) {
    G[u][v] = G[v][u] = 0;
    m--;
}

2. 邻接表存储图的基本操作

const int MAXN = 100;
vector<int> G[MAXN]; //邻接表存储图
int n, m; //节点数和边数

//插入节点
void add_node(int x) {
    n++;
}

//删除节点
void del_node(int x) {
    for (int i = 0; i < G[x].size(); i++) {
        int v = G[x][i];
        for (int j = 0; j < G[v].size(); j++) {
            if (G[v][j] == x) {
                G[v].erase(G[v].begin() + j);
                break;
            }
        }
    }
    G[x].clear();
    n--;
}

//插入边
void add_edge(int u, int v) {
    G[u].push_back(v);
    G[v].push_back(u);
    m++;
}

//删除边
void del_edge(int u, int v) {
    for (int i = 0; i < G[u].size(); i++) {
        if (G[u][i] == v) {
            G[u].erase(G[u].begin() + i);
            break;
        }
    }
    for (int i = 0; i < G[v].size(); i++) {
        if (G[v][i] == u) {
            G[v].erase(G[v].begin() + i);
            break;
        }
    }
    m--;
}

3. 图的深度优先遍历算法

const int MAXN = 100;
bool vis[MAXN]; //标记数组，标记节点是否已经被访问

//深度优先遍历
void dfs(int u) {
    vis[u] = true;
    cout << u << " ";
    for (int i = 1; i <= n; i++) {
        if (G[u][i] && !vis[i]) {
            dfs(i);
        }
    }
}

4. 图的广度优先遍历算法

const int MAXN = 100;
bool vis[MAXN]; //标记数组，标记节点是否已经被访问

//广度优先遍历
void bfs(int u) {
    queue<int> q;
    q.push(u);
    vis[u] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " ";
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i];
            if (!vis[v]) {
                vis[v] = true;
                q.push(v);
            }
        }
    }
}

我们编写了测试函数，测试以上实现的函数。

void test() {
    //创建图
    add_node(1);
    add_node(2);
    add_node(3);
    add_node(4);
    add_edge(1, 2);
    add_edge(2, 3);
    add_edge(3, 4);
    add_edge(4, 1);
    add_edge(1, 3);

    //深度优先遍历
    memset(vis, false, sizeof(vis));
    dfs(1);
    cout << endl;

    //广度优先遍历
    memset(vis, false, sizeof(vis));
    bfs(1);
    cout << endl;

    //删除节点和边
    del_edge(1, 2);
    del_node(4);

    //深度优先遍历
    memset(vis, false, sizeof(vis));
    dfs(1);
    cout << endl;

    //广度优先遍历
    memset(vis, false, sizeof(vis));
    bfs(1);
    cout << endl;
}

最终输出结果为：

1 2 3 4 
1 2 3 4 
1 3 
1 3 

实验结论：
通过本次实验，我们掌握了图的存储方法和遍历方法。邻接矩阵和邻接表都是常用的存储图的方式，它们各有优缺点。对于基本的图操作，如插入节点、插入边、删除节点、删除边等，我们也实现了相应的函数。深度优先遍历和广度优先遍历是两种常用的图遍历算法，它们各有适用的场景。在本次实验中，我们成功实现了这两种遍历算法，并且得到了正确的遍历结果。