以邻接矩阵的形式创建一个无向图;以邻接表的形式创建一个无向图
时间: 2023-11-10 13:13:12 浏览: 75
1. 以邻接矩阵的形式创建一个无向图:
假设我们有一个无向图,其中节点数为5,边数为7,其图示如下:
```
1 --- 2
/ | \
3--4 5
```
邻接矩阵的形式如下:
```
1 2 3 4 5
1 0 1 1 1 0
2 1 0 0 0 1
3 1 0 0 1 0
4 1 0 1 0 0
5 0 1 0 0 0
```
其中,矩阵的行和列分别代表图中的节点编号,矩阵中的元素表示两个节点之间是否有边相连。如果节点 i 和节点 j 之间有边相连,则矩阵中的第 i 行第 j 列和第 j 行第 i 列均为 1;否则,两个位置都为 0。
2. 以邻接表的形式创建一个无向图:
同样以上述无向图为例,邻接表的形式如下:
```
1 -> 2 -> 3 -> 4
2 -> 1 -> 5
3 -> 1 -> 4
4 -> 1 -> 3
5 -> 2
```
其中,每个节点都对应着一个链表,链表中的每个元素表示与该节点相邻的节点编号。例如,1 对应的链表中依次为 2、3、4,即节点 1 与节点 2、3、4 相邻。对于无向图中的每条边,我们需要在两个节点的链表中分别添加对方的节点编号。
相关问题
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对象,并添加了一些边。最后,我们打印了整个图的邻接表形式。
c语言,以邻接矩阵形式创建一个无向图的算法分析
创建一个无向图的邻接矩阵的算法如下:
1. 首先,需要定义一个二维数组来表示邻接矩阵,假设该数组名为adj_matrix。
2. 然后,需要输入图的顶点数n和边数m。
3. 接下来,需要初始化邻接矩阵,将其中所有元素都置为0。
4. 读入每一条边的信息,包括边的起点和终点。
5. 对于每一条边,将其对应的邻接矩阵中的元素设为1,表示该边存在。
6. 最后,输出邻接矩阵adj_matrix。
算法分析:
时间复杂度为O(n^2),因为需要初始化整个邻接矩阵,并且需要遍历所有的边。空间复杂度为O(n^2),因为需要存储整个邻接矩阵。这种方法适用于边数比较少的情况,对于边数很大的图,邻接矩阵会变得非常稀疏,造成空间浪费。此时,可以考虑使用邻接表来表示图。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)