实现图的存储,输出存储结构示意图; 输出对建立的图进行深度优先搜索和广度优先搜索所得的遍历序列。

实现图的存储可以使用邻接矩阵或邻接表两种方式。

邻接矩阵是一个二维数组，数组中的元素表示顶点之间的关系，比如顶点i和顶点j之间是否有边相连。如果存在边相连，则对应位置的元素为1，否则为0。该方式存储简单易于理解，但是对于稀疏图会造成空间浪费。

邻接表是一种链式存储结构，每个节点表示一个顶点，每个节点中存储该顶点所能到达的其他顶点的信息。该方式存储灵活，适用于稀疏图。

下面是邻接表的示意图：

         0——>1——>2
        /    / |   |
       /    /  |   |
      3——>4———5   |
       \  /   |   |
        \/    |   |
         6<———7<——8

下面是实现图的深度优先搜索和广度优先搜索的C++代码：

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>

using namespace std;

const int MAXN = 100;

// 图的邻接表表示
struct Node{
    int v, w; // v表示顶点编号，w表示边权重
};

vector<Node> G[MAXN]; // G[i]表示顶点i所能到达的其他顶点

// 深度优先搜索
void DFS(int u, bool vis[]){
    vis[u] = true;
    cout << u << " ";
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i].v;
        if(!vis[v]){
            DFS(v, vis);
        }
    }
}

// 广度优先搜索
void BFS(int s){
    queue<int> q;
    bool vis[MAXN];
    memset(vis, false, sizeof(vis));
    q.push(s);
    vis[s] = 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].v;
            if(!vis[v]){
                vis[v] = true;
                q.push(v);
            }
        }
    }
}

int main(){
    // 添加边
    G.push_back({1,1});
    G.push_back({3,1});
    G.push_back({2,1});
    G.push_back({4,1});
    G.push_back({5,1});
    G.push_back({4,1});
    G.push_back({6,1});
    G.push_back({5,1});
    G.push_back({7,1});
    G.push_back({7,1});
    G.push_back({8,1});

    // 深度优先搜索
    bool vis[MAXN];
    memset(vis, false, sizeof(vis));
    cout << "深度优先搜索遍历序列：";
    DFS(0, vis);
    cout << endl;

    // 广度优先搜索
    cout << "广度优先搜索遍历序列：";
    BFS(0);
    cout << endl;

    return 0;
}