利用数据结构建立一个图的邻接矩阵存储结构(数组表示),并将邻接矩阵输出。
时间: 2024-03-06 20:47:26 浏览: 76
好的,我可以为您介绍一下如何利用数据结构建立一个图的邻接矩阵存储结构,并将其输出。
首先,我们需要定义一个结构体来表示图中的顶点和边,如下所示:
```c++
struct Graph {
int vertices; // 顶点的数量
int** adjMatrix; // 邻接矩阵
};
```
其中,vertices表示图中顶点的数量,adjMatrix是一个二维数组,表示邻接矩阵。
接下来,我们需要编写一个函数来创建邻接矩阵。这个函数需要输入图中的顶点数量和边的信息,然后根据这些信息构建邻接矩阵。下面是一个示例代码:
```c++
Graph createGraph(int vertices, int edges[][2], int numEdges) {
Graph graph;
graph.vertices = vertices;
graph.adjMatrix = new int*[vertices];
for(int i = 0; i < vertices; i++) {
graph.adjMatrix[i] = new int[vertices];
for(int j = 0; j < vertices; j++) {
graph.adjMatrix[i][j] = 0; // 初始化邻接矩阵
}
}
// 添加边的信息到邻接矩阵中
for(int i = 0; i < numEdges; i++) {
int src = edges[i][0];
int dst = edges[i][1];
graph.adjMatrix[src][dst] = 1;
graph.adjMatrix[dst][src] = 1; // 无向图需要在两个方向上都添加边
}
return graph;
}
```
这个函数使用动态数组来创建邻接矩阵,并将边的信息添加到邻接矩阵中。注意,对于无向图来说,需要在两个方向上都添加边。
接下来,我们可以编写一个函数来输出邻接矩阵。下面是一个示例代码:
```c++
void printGraph(Graph graph) {
for(int i = 0; i < graph.vertices; i++) {
for(int j = 0; j < graph.vertices; j++) {
cout << graph.adjMatrix[i][j] << " ";
}
cout << endl;
}
}
```
这个函数使用两层循环来遍历邻接矩阵,并将每个元素输出到屏幕上。
最后,我们可以在主函数中调用这些函数来创建和输出邻接矩阵。下面是一个示例代码:
```c++
int main() {
int vertices = 5;
int edges[][2] = {{0, 1}, {0, 4}, {1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}};
int numEdges = 7;
Graph graph = createGraph(vertices, edges, numEdges);
printGraph(graph);
return 0;
}
```
这个示例代码创建了一个无向图,包含5个顶点和7条边。然后调用createGraph函数创建邻接矩阵,并调用printGraph函数输出邻接矩阵。输出结果为:
```
0 1 0 0 1
1 0 1 1 0
0 1 0 1 1
0 1 1 0 1
1 0 1 1 0
```
希望这个例子能够帮助您理解如何利用数据结构建立一个图的邻接矩阵存储结构,并将其输出。
阅读全文