c++实现图的邻接表或邻接矩阵表示,并创建图
时间: 2023-11-25 11:23:05 浏览: 46
好的,下面是 C++ 实现图的邻接表或邻接矩阵表示,并创建图的基本步骤:
1. 定义图的结构体,包括节点数目、边数目、邻接表或邻接矩阵等信息。
2. 对于邻接表,定义一个节点的结构体,包括顶点编号和指向下一个节点的指针。对于邻接矩阵,定义一个二维数组,表示节点之间的连通情况。
3. 根据输入的节点数目和边数目,动态分配邻接表或邻接矩阵的空间。
4. 根据输入的边的信息,依次在邻接表或邻接矩阵中添加边。
5. 完成图的创建后,可以进行遍历操作,比如深度优先遍历或广度优先遍历。
下面是一个示例代码,演示如何使用邻接表表示图,实现图的创建和深度优先遍历:
```c++
#include <iostream>
#include <vector>
using namespace std;
// 定义邻接表节点的结构体
struct AdjListNode {
int dest;
struct AdjListNode* next;
};
// 定义图的结构体
struct Graph {
int V; // 节点数目
int E; // 边数目
struct AdjListNode** adjList; // 邻接表
vector<bool> visited; // 记录节点是否被访问过
};
// 创建一个新的邻接表节点
struct AdjListNode* newAdjListNode(int dest) {
struct AdjListNode* newNode = new AdjListNode;
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
// 创建一个新的图
struct Graph* createGraph(int V, int E) {
struct Graph* graph = new Graph;
graph->V = V;
graph->E = E;
graph->adjList = new AdjListNode*[V];
graph->visited = vector<bool>(V, false);
for (int i = 0; i < V; ++i)
graph->adjList[i] = NULL;
return graph;
}
// 添加一条边到邻接表
void addEdge(struct Graph* graph, int src, int dest) {
struct AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->adjList[src];
graph->adjList[src] = newNode;
}
// 深度优先遍历
void DFS(struct Graph* graph, int v) {
graph->visited[v] = true;
cout << v << " ";
struct AdjListNode* node = graph->adjList[v];
while (node != NULL) {
int dest = node->dest;
if (!graph->visited[dest])
DFS(graph, dest);
node = node->next;
}
}
int main() {
int V = 5; // 节点数目
int E = 6; // 边数目
struct Graph* graph = createGraph(V, E);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 2, 0);
addEdge(graph, 2, 3);
addEdge(graph, 3, 3);
cout << "Depth First Traversal (starting from vertex 2) \n";
DFS(graph, 2);
return 0;
}
```
希望这个示例代码对你有所帮助。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)