利用邻接矩阵储存无向图
时间: 2023-10-18 14:28:15 浏览: 36
邻接矩阵是一种常见的储存无向图的方法。对于一个无向图G=(V,E),设V中有n个顶点,邻接矩阵A是一个n*n的矩阵,其中A[i][j]表示顶点i和顶点j之间是否有边,如果有,则A[i][j]=1,否则A[i][j]=0。由于是无向图,因此A[i][j]=A[j][i],即邻接矩阵是对称的。
邻接矩阵的优点是可以快速判断任意两个顶点之间是否有边,时间复杂度为O(1),而且储存空间比较小,只需要n*n个空间。但是当图的边数比较稀疏时,也就是说E比较小,邻接矩阵会有很多空洞,浪费了储存空间,因此不适用于稀疏图。另外,对于大型图,邻接矩阵的储存空间也会非常大,导致效率下降。
相关问题
使用邻接矩阵存储无向图
使用邻接矩阵存储无向图的步骤如下:
1. 定义一个顶点类型的一维数组,用于存储顶点。
2. 定义一个int类型的二维数组,用于存储边。对于无向图,邻接矩阵是一个对称矩阵,即edge[i][j] = edge[j][i]。
3. 定义两个int型变量,分别存储顶点数、边数。
4. 初始化邻接矩阵,将所有元素初始化为0。
5. 根据图的实际情况,将边的信息存储到邻接矩阵中。对于无向图,如果顶点i和顶点j之间有一条边,则将edge[i][j]和edge[j][i]的值都设为1。
6. 根据需要,可以输出邻接矩阵或者进行其他操作。
下面是一个使用邻接矩阵存储无向图的示例代码:
```c++
#include <iostream>
using namespace std;
const int max_vertex_num = 100;
typedef char VexType; // 顶点类型
typedef int EdgeType; // 边权值类型
class AMGraph {
public:
VexType vex[max_vertex_num]; // 存储顶点
EdgeType edge[max_vertex_num][max_vertex_num]; // 存储边
int vex_num, edge_num; // 顶点数、边数
// 初始化邻接矩阵
void Init() {
for (int i = 0; i < vex_num; i++) {
for (int j = 0; j < vex_num; j++) {
edge[i][j] = 0;
}
}
}
// 添加边
void AddEdge(int i, int j) {
edge[i][j] = 1;
edge[j][i] = 1;
}
// 输出邻接矩阵
void Print() {
for (int i = 0; i < vex_num; i++) {
for (int j = 0; j < vex_num; j++) {
cout << edge[i][j] << " ";
}
cout << endl;
}
}
};
int main() {
AMGraph g;
g.vex_num = 5;
g.edge_num = 6;
g.vex[0] = 'A';
g.vex[1] = 'B';
g.vex[2] = 'C';
g.vex[3] = 'D';
g.vex[4] = 'E';
g.Init();
g.AddEdge(0, 1);
g.AddEdge(0, 2);
g.AddEdge(1, 2);
g.AddEdge(1, 3);
g.AddEdge(2, 3);
g.AddEdge(3, 4);
g.Print();
return 0;
}
```
C语言实现利用邻接矩阵储存无向图利用DFS判断无向图是否有环,如果有环将环的顶点序列依次输出
好的,您的问题是如何用C语言实现利用邻接矩阵储存无向图,并使用DFS判断无向图是否有环,如果有环则将环的顶点序列依次输出。
首先,我们需要了解邻接矩阵的概念。邻接矩阵是一种表示图的方法,它使用一个二维数组来表示图中每个节点之间的连通性。
在C语言中,我们可以使用二维数组来表示邻接矩阵。假设我们有一个无向图G,它有n个节点,那么我们可以这样定义一个邻接矩阵:
```c
int graph[n][n];
```
其中,`graph[i][j]`表示节点i和节点j之间是否有连边,如果有连边则为1,否则为0。
接下来,我们需要使用DFS来判断无向图是否有环。DFS是一种图遍历算法,它可以遍历图中所有的节点,并且可以判断图中是否有环。
我们可以定义一个visited数组来记录每个节点是否被访问过,然后从任意一个节点开始进行DFS遍历。在遍历过程中,如果我们遇到一个已经被访问过的节点,那么说明图中存在环。
具体实现如下:
```c
int visited[n]; // 记录每个节点是否被访问过
void dfs(int u, int parent, int* cycle, int* index, int* found) {
visited[u] = 1; // 标记当前节点为已访问
// 遍历当前节点的所有邻居节点
for (int v = 0; v < n; v++) {
if (graph[u][v]) { // 如果节点u和节点v之间有连边
if (visited[v] && v != parent) { // 如果节点v已经被访问过,且不是节点u的父节点
// 找到了环,将环的顶点序列依次输出
*found = 1;
cycle[*index] = v;
(*index)++;
cycle[*index] = u;
(*index)++;
return;
} else if (!visited[v]) { // 如果节点v还没有被访问过
dfs(v, u, cycle, index, found); // 继续访问节点v
if (*found) { // 如果已经找到环,将当前节点加入环中
cycle[*index] = u;
(*index)++;
return;
}
}
}
}
}
int has_cycle(int* cycle) {
int index = 0;
int found = 0;
// 对每个节点进行DFS遍历
for (int u = 0; u < n; u++) {
if (!visited[u]) {
dfs(u, -1, cycle, &index, &found);
if (found) {
cycle[index] = cycle[0]; // 环的最后一个节点应该和第一个节点相同
return 1; // 存在环
}
}
}
return 0; // 不存在环
}
```
在上面的代码中,我们定义了一个`dfs`函数来进行DFS遍历,它的参数包括当前节点`u`、父节点`parent`、环的顶点序列`cycle`、当前下标`index`和是否找到环`found`。在遍历过程中,如果找到了环,就将环的顶点序列依次输出,并且将`found`设置为1,表示已经找到环。
然后,我们定义了一个`has_cycle`函数来判断无向图是否有环。它首先对每个节点进行DFS遍历,如果找到了环,就将环的顶点序列保存到`cycle`数组中,并返回1,表示存在环。如果遍历完所有节点都没有找到环,就返回0,表示不存在环。
最后,我们可以这样调用`has_cycle`函数来判断无向图是否有环,并输出环的顶点序列:
```c
int cycle[n]; // 保存环的顶点序列
if (has_cycle(cycle)) {
printf("The graph has a cycle: ");
for (int i = 0; i < n; i++) {
printf("%d ", cycle[i]);
}
printf("\n");
} else {
printf("The graph does not have a cycle.\n");
}
```
注意,这里的环是一个简单环,即环中的每个节点都只出现一次。如果图中存在重复的边,那么可能会输出非简单环。