图的邻接矩阵定义及实现: 定义图的邻接阵存储结构,并编写图的初始化、建立图、输出图、深度优先/广度优先遍历、计算并输出图中每个顶点的度(入度+出度)等基本操作的实现函数。以下图为例,建立一个验证操作实现的主函数进行测试。
时间: 2024-11-04 10:17:07 浏览: 227
数据结构课程设计-图的邻接矩阵.doc
图的邻接矩阵是一种常见的图数据结构,它是一个二维数组,其中的每个元素表示两个顶点之间是否存在边。如果第i行第j列的元素值为1(或非零),则表示顶点i与顶点j之间有边相连;否则,无连接。
**定义与实现:**
- **邻接矩阵表示法**:
- 矩阵的行和列表示图中的顶点,矩阵[i][j] = 1 表示顶点i和顶点j间有边,0表示无边。
- **初始化函数** (假设`AdjMatrixGraph`为邻接矩阵图类型):
```cpp
void initializeGraph(AdjMatrixGraph &graph, int vertices) {
graph.resize(vertices, vector<int>(vertices, 0)); // 初始化全零矩阵
}
```
- **建立图**:
```cpp
void addEdge(AdjMatrixGraph &graph, int src, int dest) {
graph[src][dest] = 1; // 如果src到dest有边,则邻接矩阵对应位置设为1
graph[dest][src] = 1; // 对于无向图,需要两边都设置
}
```
- **输出图**:
```cpp
void printGraph(const AdjMatrixGraph &graph, int vertices) {
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
cout << graph[i][j] << " ";
}
cout << "\n";
}
}
```
- **深度优先搜索(Depth First Search, DFS)和广度优先搜索(Breadth First Search, BFS)**:
```cpp
void dfs(AdjMatrixGraph &graph, int start, vector<bool> &visited) { ... } // 实现细节省略
void bfs(AdjMatrixGraph &graph, int start, vector<bool> &visited) { ... } // 实现细节省略
```
- **计算并输出顶点度**:
```cpp
void vertexDegree(AdjMatrixGraph &graph, int vertices) {
for (int i = 0; i < vertices; i++) {
int degree = count_if(graph[i].begin(), graph[i].end(), [](int x) { return x == 1; }); // 对于无向图算入度加出度
cout << "Vertex " << i << " has degree: " << degree << endl;
}
}
```
- **测试主函数**:
```cpp
int main() {
int vertices = 5;
AdjMatrixGraph g;
initializeGraph(g, vertices);
// 添加边...
printGraph(g, vertices);
dfs(g, 0, vector<bool>(vertices, false));
bfs(g, 0, vector<bool>(vertices, false));
vertexDegree(g, vertices);
return 0;
}
```
阅读全文