以邻接矩阵形式创建一个无向图和 以邻接表的形式创建一个无向图。
时间: 2023-11-24 12:09:05 浏览: 77
邻接矩阵形式创建无向图:
假设我们有一个无向图,其顶点集合为V={V1,V2,V3,V4},边集合为E={(V1,V2),(V2,V3),(V3,V4),(V4,V1)}。那么我们可以用一个4x4的矩阵表示这个无向图,矩阵中的每个元素表示两个顶点之间是否存在一条边。如果存在,则为1,否则为0。
```
V1 V2 V3 V4
V1 0 1 0 1
V2 1 0 1 0
V3 0 1 0 1
V4 1 0 1 0
```
邻接表形式创建无向图:
我们还可以使用邻接表来表示无向图。邻接表是由各个顶点的邻居列表所组成的一张表。对于每个顶点Vi,我们可以用一个链表来存储它的邻居。例如,对于上面的无向图,它的邻接表如下所示:
```
V1: V2 -> V4
V2: V1 -> V3
V3: V2 -> V4
V4: V1 -> V3
```
其中 "->" 表示链表的指向关系。在这个邻接表中,每个顶点的邻居都被保存在一个链表中,我们可以轻松地查找每个顶点的所有邻居。
相关问题
以邻接矩阵形式创建一个无向图; 以邻接表的形式创建一个无向图。
1. 以邻接矩阵形式创建一个无向图
假设我们要创建一个无向图,该图有5个节点,节点之间的连接关系如下所示:
```
1 -- 2
| |
3 -- 4
```
则该无向图的邻接矩阵为:
```
0 1 0 1 0
1 0 1 0 0
0 1 0 1 0
1 0 1 0 0
0 0 0 0 0
```
其中,矩阵中的每一个元素表示两个节点之间是否有连接关系,如果有,则为1,否则为0。比如,第一行第二列的元素为1,表示节点1和节点2之间有连接关系。
2. 以邻接表的形式创建一个无向图
同样以上面的无向图为例,该无向图的邻接表表示如下:
```
1: 2, 3
2: 1, 4
3: 1, 4
4: 2, 3
5:
```
其中,每一行表示一个节点及其相邻节点的列表,比如第一行表示节点1与节点2、3有连接关系。如果一个节点没有任何相邻节点,则表示为空列表。
C++以邻接矩阵形式创建一个无向图
下面是使用邻接矩阵创建无向图的C++代码示例:
```c++
#include <iostream>
using namespace std;
const int MAX = 100;
class Graph {
private:
int numVertices;
int adjMatrix[MAX][MAX];
public:
Graph(int numVertices) {
this->numVertices = numVertices;
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
adjMatrix[i][j] = 0;
}
}
}
void addEdge(int i, int j) {
adjMatrix[i][j] = 1;
adjMatrix[j][i] = 1;
}
void removeEdge(int i, int j) {
adjMatrix[i][j] = 0;
adjMatrix[j][i] = 0;
}
void printGraph() {
for (int i = 0; i < numVertices; i++) {
cout << "Vertex " << i << " is connected to: ";
for (int j = 0; j < numVertices; j++) {
if (adjMatrix[i][j] == 1) {
cout << j << " ";
}
}
cout << endl;
}
}
};
int main() {
Graph g(5);
g.addEdge(0, 1);
g.addEdge(0, 4);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.printGraph();
return 0;
}
```
在上面的代码中,我们首先定义了一个Graph类,该类包含两个私有成员变量:numVertices表示图中顶点的数量,adjMatrix是一个二维数组,表示邻接矩阵。接下来,我们定义了构造函数和一些函数来添加和删除边以及打印图。在main函数中,我们创建了一个Graph对象,并添加了一些边。最后,我们打印了整个图的邻接表形式。