1、自己确定一个简单无向图（顶点数>=5）利用邻接矩阵或者邻接表来实现图的构造，并完成: (1）用深度优先和广度优先两种算法对图进行遍历，输出顶点序列教据 (2）以合理的格式，输出各个顶点的邻接点。

在一个简单的无向图示例中，我们假设图由6个顶点A, B, C, D, E, F组成，它们之间有以下边连接：A-B, A-C, B-D, C-E, C-F。

**一、邻接矩阵表示：**
邻接矩阵是一个二维数组，其中行代表起点，列表示终点，值为1表示两点相连，0表示不连通。对于这个例子，邻接矩阵会是：

| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 1 | 0 |

**二、深度优先搜索 (DFS) 和广度优先搜索 (BFS):**
1. **DFS遍历结果：**
- 遍历顺序可能因起始节点不同而变化，例如从A开始：A->B->D->C->F->E
- 格式化输出：[A, B, D, C, F, E]

2. **BFS遍历结果：**
- 从A开始：A->B->C->D->E->F
- 格式化输出：[A, B, C, D, E, F]

**三、输出邻接点：**
对于每个顶点，我们可以列出其相邻的顶点：
- A的邻接点：B, C
- B的邻接点：D
- C的邻接点：E, F
- D的邻接点：A, B
- E的邻接点：C
- F的邻接点：C

相关问题

用c++自己确定一个简单无向图（顶点数>=5）利用邻接矩阵或者邻接表来实现图的构造，并完成: (1）用深度优先和广度优先两种算法对图进行遍历，输出顶点序列教据 (2）以合理的格式，输出各个顶点的邻接点。

在C++中，我们可以使用邻接矩阵或邻接表这两种数据结构来表示无向图。这里以邻接矩阵为例，因为它的操作效率适合于稠密图，即顶点间的边较多的情况。

#include <iostream>
#include <vector>

// 邻接矩阵实现
typedef std::vector<std::vector<int>> AdjMatrix;

AdjMatrix createAdjMatrix(int vertices) {
    AdjMatrix graph(vertices, std::vector<int>(vertices, 0)); // 初始化全零矩阵
    // 替换这里的代码，添加实际的边，例如：
    // graph[i][j] = 1; 表示顶点i和j之间有一条边
    return graph;
}

void depthFirstSearch(AdjMatrix& graph, int start) {
    std::vector<bool> visited(graph.size(), false);
    std::cout << "Depth First Search:\n";
    dfsUtil(graph, start, visited);
}

void dfsUtil(AdjMatrix& graph, int vertex, std::vector<bool>& visited) {
    visited[vertex] = true;
    std::cout << vertex << " ";
    
    for (int i = 0; i < graph.size(); ++i)
        if (!visited[i] && graph[vertex][i])
            dfsUtil(graph, i, visited);
}

void breadthFirstSearch(AdjMatrix& graph, int start) {
    std::vector<bool> visited(graph.size(), false);
    std::queue<int> queue;
    queue.push(start);

    std::cout << "Breadth First Search:\n";
    while (!queue.empty()) {
        int vertex = queue.front();
        queue.pop();
        visited[vertex] = true;
        
        std::cout << vertex << " ";
        
        for (int i = 0; i < graph.size(); ++i)
            if (!visited[i] && graph[vertex][i])
                queue.push(i);
    }
}

void printAdjacencyList(const AdjMatrix& graph) {
    for (int i = 0; i < graph.size(); ++i) {
        std::cout << "Adjacency list of vertex " << i << ":\n";
        for (int j = 0; j < graph.size(); ++j)
            if (graph[i][j]) {
                std::cout << j << " ";
            }
        std::cout << "\n";
    }
}

int main() {
    int vertices;
    std::cout << "Enter the number of vertices: ";
    std::cin >> vertices;

    AdjMatrix graph = createAdjMatrix(vertices);
    
    std::cout << "Enter the edges or adjacency matrix elements:\n"; // 这里添加输入边的逻辑

    depthFirstSearch(graph, 0); // 从顶点0开始深度优先搜索
    breadthFirstSearch(graph, 0); // 同样从顶点0开始广度优先搜索

    printAdjacencyList(graph);

    return 0;
}

设计一个程序，在无向图中删除一个顶点及相关边；邻接矩阵作为存储结构。算法思想： (1) 定义图的顺序存储结构； (2) 创建无向图，采用邻接矩阵表示（调用CreateUDG函数实现），具体实现如下： 输入图的顶点数和边数； 依次输入顶点的信息存入顶点表中； 初始化邻接矩阵，使每个权值初始化为0； 构造邻接矩阵；（需调用LocateVex函数获取顶点在顶点表中的下标） (3) 删除一个顶点v及相关边（调用DeleteVex函数实现）。 (4) 输出删除顶点v及其相关边后图的邻接矩阵（调用PrintUDG函数实现）。

以下是基于邻接矩阵存储结构的无向图删除顶点及相关边的程序实现：

#include <iostream>
using namespace std;

#define MAX_VERTEX_NUM 20

// 顶点表结构体
typedef struct {
    int no; // 顶点编号
    char info; // 顶点信息
}VertexType;

// 图的邻接矩阵存储结构体
typedef struct {
    VertexType vexs[MAX_VERTEX_NUM]; // 顶点表
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
    int vexnum; // 顶点数
    int arcnum; // 边数
}MGraph;

// 获取顶点在顶点表中的下标
int LocateVex(MGraph &G, int v) {
    for (int i = 0; i < G.vexnum; i++) {
        if (G.vexs[i].no == v) {
            return i;
        }
    }
    return -1;
}

// 创建无向图，采用邻接矩阵表示
void CreateUDG(MGraph &G) {
    cout << "请输入顶点数和边数：" << endl;
    cin >> G.vexnum >> G.arcnum;
    cout << "请输入每个顶点的信息：" << endl;
    for (int i = 0; i < G.vexnum; i++) {
        cout << "第" << i + 1 << "个顶点信息：";
        cin >> G.vexs[i].info;
        G.vexs[i].no = i + 1;
    }
    // 初始化邻接矩阵，使每个权值初始化为0
    for (int i = 0; i < G.vexnum; i++) {
        for (int j = 0; j < G.vexnum; j++) {
            G.arcs[i][j] = 0;
        }
    }
    // 构造邻接矩阵
    int v1, v2;
    for (int k = 0; k < G.arcnum; k++) {
        cout << "请输入一条边依附的顶点及其权值：" << endl;
        cin >> v1 >> v2;
        int i = LocateVex(G, v1);
        int j = LocateVex(G, v2);
        if (i != -1 && j != -1) {
            G.arcs[i][j] = 1;
            G.arcs[j][i] = G.arcs[i][j]; // 无向图的邻接矩阵是对称的
        }
    }
}

// 删除一个顶点v及相关边
void DeleteVex(MGraph &G, int v) {
    int i = LocateVex(G, v);
    if (i == -1) {
        cout << "不存在该顶点！" << endl;
        return;
    }
    // 删除与该顶点相关的边
    for (int j = 0; j < G.vexnum; j++) {
        if (G.arcs[i][j] == 1) {
            G.arcs[i][j] = 0;
            G.arcs[j][i] = G.arcs[i][j];
        }
    }
    // 删除该顶点
    for (int k = i; k < G.vexnum - 1; k++) {
        G.vexs[k] = G.vexs[k + 1];
        for (int m = 0; m < G.vexnum; m++) {
            G.arcs[m][k] = G.arcs[m][k + 1];
        }
    }
    for (int k = i; k < G.vexnum - 1; k++) {
        for (int n = 0; n < G.vexnum; n++) {
            G.arcs[k][n] = G.arcs[k + 1][n];
        }
    }
    G.vexnum--; // 顶点数减1
}

// 输出删除顶点v及其相关边后图的邻接矩阵
void PrintUDG(MGraph &G) {
    cout << "删除顶点v及其相关边后图的邻接矩阵为：" << endl;
    for (int i = 0; i < G.vexnum; i++) {
        for (int j = 0; j < G.vexnum; j++) {
            cout << G.arcs[i][j] << " ";
        }
        cout << endl;
    }
}

int main() {
    MGraph G;
    CreateUDG(G);
    int v;
    cout << "请输入要删除的顶点：" << endl;
    cin >> v;
    DeleteVex(G, v);
    PrintUDG(G);
    return 0;
}

运行程序，输入顶点数、边数、顶点信息、边依附的顶点及其权值，再输入要删除的顶点，程序将输出删除顶点及其相关边后的图的邻接矩阵。