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

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

1. 邻接矩阵

邻接矩阵是一个二维数组，其中第 i 行第 j 列的元素表示第 i 个顶点到第 j 个顶点是否有边相连。如果有，则值为边的权值；如果没有，则值为0。

示意图：

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

2. 邻接表

邻接表是一个数组，每个元素是一个链表，链表中存储该顶点连向的其他顶点。

示意图：

1 -> 2 -> 3
2 -> 1 -> 3 -> 4
3 -> 1 -> 2 -> 4
4 -> 2 -> 3

深度优先搜索（DFS）和广度优先搜索（BFS）都是用来遍历图的算法。

1. 深度优先搜索

深度优先搜索从起点开始，尽可能深地访问每个顶点，直到无法继续深入，然后回溯到上一个顶点，继续访问其他顶点，直到所有顶点都被访问。

遍历序列：1 2 3 4

2. 广度优先搜索

广度优先搜索从起点开始，依次访问起点的所有邻居顶点，然后访问邻居的邻居，以此类推，直到所有顶点都被访问。

遍历序列：1 2 3 4

注：由于此处的图是无向图，因此深度优先搜索和广度优先搜索的遍历序列是相同的。如果是有向图，则可能不同。

相关问题

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

C语言可以通过邻接矩阵和邻接表两种方式实现图的存储。

1. 邻接矩阵

邻接矩阵是一种二维数组，数组中的每个元素表示两个顶点之间是否有边相连，通常用 0 和 1 表示。如果第 i 行第 j 列的元素为 1，则表示第 i 个顶点和第 j 个顶点之间有一条边相连；如果为 0，则表示没有边相连。邻接矩阵可以方便地进行深度优先搜索和广度优先搜索。

下面是邻接矩阵的存储结构示意图：

       1   2   3   4
    ---------------
  1|  0   1   1   0
  2|  1   0   1   1
  3|  1   1   0   1
  4|  0   1   1   0

其中，行号和列号表示顶点的编号，如果某个元素为 1，则表示对应的两个顶点之间有一条边相连。

2. 邻接表

邻接表是一种链表的形式，每个顶点对应一个链表，链表中存储了该顶点所有相邻的顶点。邻接表可以节省存储空间，但是在进行深度优先搜索和广度优先搜索时需要进行更多的操作。

下面是邻接表的存储结构示意图：

    1 --> 2 --> 3
    |     |     |
    v     v     v
    2 --> 1 --> 3 --> 4
    |           |
    v           v
    3 --> 1 --> 2 --> 4
    |
    v
    4 --> 2 --> 3

其中，每个顶点对应一个链表，链表中存储了该顶点所有相邻的顶点。

对于给定的图，我们可以通过深度优先搜索和广度优先搜索来遍历整个图。深度优先搜索会首先遍历一个顶点的所有相邻顶点，再依次遍历相邻顶点的相邻顶点，直到遍历完整个图。广度优先搜索则是从一个起始顶点开始，依次遍历该起始顶点的所有相邻顶点，再依次遍历相邻顶点的相邻顶点，直到遍历完整个图。

以下是对于给定图进行深度优先搜索和广度优先搜索所得的遍历序列：

深度优先搜索遍历序列：1 -> 2 -> 3 -> 4

广度优先搜索遍历序列：1 -> 2 -> 3 -> 4

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

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

邻接矩阵是一个二维数组，数组中的元素表示顶点之间的关系，比如顶点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;
}