建立一个无向图，采用邻接矩阵做存储结构pta

好的，那么您需要先确定图的节点数和边数，然后才能开始构建邻接矩阵。

假设有 $n$ 个节点和 $m$ 条边，我们可以先创建一个 $n \times n$ 的矩阵，初始值全部为 0。然后对于每一条边 $(u,v)$，我们将矩阵中第 $u$ 行第 $v$ 列和第 $v$ 行第 $u$ 列的值设为 1，表示这两个节点之间有一条边。

下面是一个简单的 C++ 代码示例：

const int N = 100; // 最大节点数
int n, m;
int g[N][N]; // 邻接矩阵

int main() {
    // 读入节点数和边数
    cin >> n >> m;

    // 构建邻接矩阵
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u][v] = g[v][u] = 1;
    }

    // 输出邻接矩阵
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << g[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

希望这能帮到您，如果您还有其他问题，可以继续问我哦。

相关问题

邻接矩阵存储图的深度优先遍历pta

### 使用邻接矩阵存储图并进行深度优先遍历

对于使用邻接矩阵存储图并执行深度优先遍历的操作，在处理过程中，主要涉及两个方面：一是构建邻接矩阵表示的图结构；二是基于该结构实施DFS（Depth First Search）。通过这种方式可以有效地探索所有节点及其连接情况。

#### 构建邻接矩阵

假设有一个无向图G=(V,E)，其中V代表顶点集合而E则为边集。为了创建一个大小为n×n(n=|V|)的邻接矩阵`adjMatrix`用于描述此图：

- 如果存在一条由i指向j的边，则设置`adjMatrix[i][j]=1`(或权重w_ij);
- 否则设其等于0；

当涉及到有权重的情况时，可以用具体的权值代替上述条件中的1[^3]。

// 初始化 n*n 的零矩阵作为邻接矩阵
vector<vector<int>> adjMatrix(n, vector<int>(n, 0));

#### 深度优先遍历实现

一旦有了邻接矩阵形式的地图表达方式之后，就可以着手编写递归版本或是迭代版式的DFS算法了。这里给出一种常见的递归方法来完成这项工作:

void DFS(int v, bool visited[], const vector<vector<int>>& adjMatrix){
    cout << "Visited vertex: " << v << endl;
    visited[v] = true;

    for (int i = 0; i < adjMatrix.size(); ++i){
        if (!visited[i] && adjMatrix[v][i]){
            DFS(i, visited, adjMatrix);
        }
    }
}

这段代码定义了一个名为`DFS`的过程接收三个参数——起始访问结点编号v、布尔型数组标记哪些结点已被访问过以及传入之前建立好的邻接矩阵。每当遇到未被访问过的相邻结点就调用自己继续深入下去直到不能再前进为止。

#### 完整示例程序

下面提供一段完整的C++代码片段展示如何初始化数据结构、填充测试案例的数据，并最终启动一次从特定起点出发的深度优先搜索过程。

#include <iostream>
#include <vector>

using namespace std;

void DFS(int v, bool visited[], const vector<vector<int>>& adjMatrix);

int main(){
    int n = 5; // 假设有五个顶点
    
    // 创建并初始化邻接矩阵
    vector<vector<int>> adjMatrix(n, vector<int>(n, 0));

    // 添加一些假定存在的边到我们的图中...
    adjMatrix[0][1] = adjMatrix[1][0] = 1;
    adjMatrix[0][2] = adjMatrix[2][0] = 1;
    adjMatrix[1][3] = adjMatrix[3][1] = 1;
    adjMatrix[2][4] = adjMatrix[4][2] = 1;

    // 准备好记录已访问状态的空间
    bool* visited = new bool[n];
    fill_n(visited, n, false);

    // 开始于第一个顶点
    DFS(0, visited, adjMatrix);

    delete[] visited;
    
    return 0;
}

void DFS(int v, bool visited[], const vector<vector<int>>& adjMatrix){
    cout << "Visited vertex: " << v << endl;
    visited[v] = true;

    for (int i = 0; i < adjMatrix.size(); ++i){
        if (!visited[i] && adjMatrix[v][i]){
            DFS(i, visited, adjMatrix);
        }
    }
}

pta 邻接矩阵存储图的深度优先遍历

### 邻接矩阵存储图的深度优先遍历 (DFS)

对于采用邻接矩阵表示法的图结构，可以利用递归的方式实现其深度优先遍历(DFS)[^1]。具体来说，在创建好无向图之后，通过`DFStraverse`函数来执行遍历操作。

#### 创建无向图

为了构建基于邻接矩阵的无向图，需先初始化一个二维数组用于保存节点间的连接关系。设该图为G，则可通过如下伪代码完成建图过程：

#define MAX_VERTICES 100 // 假定最大顶点数不超过100

// 定义边的数量以及读取每条边的信息并更新到matrix中
void create_Graph(int matrix[MAX_VERTICES][MAX_VERTICES], int edges){
    memset(matrix, 0, sizeof(matrix)); // 初始化矩阵全零
    
    while(edges--){
        scanf("%d %d", &startVertex, &endVertex);
        matrix[startVertex][endVertex] = 1;
        matrix[endVertex][startVertex] = 1; // 对于无向图而言，双向都要设置为相连状态
    }
}

此部分负责接收输入数据，并据此填充代表各顶点间关联性的布尔值至指定位置处。

#### 执行深度优先遍历

一旦完成了上述准备工作后，便能够调用专门针对此类图形化对象而编写的DFS算法来进行探索活动了。这里给出了一种可能的方法论描述及其对应的源码片段:

bool visited[MAX_VERTICES];

// 辅助功能：单次递归调用形式下的DFS流程控制逻辑
void dfs_recursive(int graph[][MAX_VERTICES], int vertexCount, int currentVertex){
    visit(currentVertex); // 访问当前顶点
    visited[currentVertex] = true;

    for(int nextVertex=0 ;nextVertex<vertexCount;++nextVertex){
        if(graph[currentVertex][nextVertex]==1 && !visited[nextVertex]){
            dfs_recursive(graph, vertexCount, nextVertex);
        }
    }
}

// 主导接口：启动整个DFS进程
void DFStraverse(int graph[][MAX_VERTICES], int vertexCount){
    memset(visited,false,sizeof(bool)*vertexCount);

    for(int startVertex=0;startVertex<vertexCount;++startVertex){
        if(!visited[startVertex])
            dfs_recursive(graph, vertexCount, startVertex);
    }
}

这段程序首先会重置所有已知地点的状态标志位；接着尝试从未被触及过的起点出发，依次深入探寻每一个可达区域直至无法继续前进为止——即实现了所谓的“尽可能深地沿某一分支向下挖掘”的核心思想[^2]。