用邻接表实现图的存储遍历
时间: 2023-08-15 22:18:51 浏览: 73
邻接表是一种常见的图的存储方式,它通过一个数组和每个数组元素对应的链表来表示图。
具体实现过程如下:
1. 定义一个邻接表的结构体,包括一个数组和一个链表。
```
struct Graph {
int V; // 顶点数
struct ListNode** adjList; // 邻接表
};
```
2. 定义链表节点的结构体。
```
struct ListNode {
int dest; // 目标顶点
struct ListNode* next; // 指向下一个节点的指针
};
```
3. 初始化邻接表。
```
struct Graph* createGraph(int V) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
graph->adjList = (struct ListNode**)malloc(V * sizeof(struct ListNode*));
int i;
for (i = 0; i < V; ++i) {
graph->adjList[i] = NULL;
}
return graph;
}
```
4. 添加边,将边插入到相应的链表中。
```
void addEdge(struct Graph* graph, int src, int dest) {
// 添加一条边从src到dest
struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->dest = dest;
newNode->next = graph->adjList[src];
graph->adjList[src] = newNode;
// 无向图还需添加一条从dest到src的边
newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->dest = src;
newNode->next = graph->adjList[dest];
graph->adjList[dest] = newNode;
}
```
5. 遍历图,可以使用深度优先搜索(DFS)或广度优先搜索(BFS)。
DFS:
```
void DFS(struct Graph* graph, int v, bool visited[]) {
visited[v] = true;
printf("%d ", v);
struct ListNode* temp = graph->adjList[v];
while (temp) {
if (!visited[temp->dest]) {
DFS(graph, temp->dest, visited);
}
temp = temp->next;
}
}
void DFS_traversal(struct Graph* graph, int start) {
bool* visited = new bool[graph->V];
for (int i = 0; i < graph->V; i++) {
visited[i] = false;
}
DFS(graph, start, visited);
}
```
BFS:
```
void BFS_traversal(struct Graph* graph, int start) {
bool* visited = new bool[graph->V];
for (int i = 0; i < graph->V; i++) {
visited[i] = false;
}
list<int> queue;
visited[start] = true;
queue.push_back(start);
while (!queue.empty()) {
int v = queue.front();
printf("%d ", v);
queue.pop_front();
struct ListNode* temp = graph->adjList[v];
while (temp) {
if (!visited[temp->dest]) {
visited[temp->dest] = true;
queue.push_back(temp->dest);
}
temp = temp->next;
}
}
}
```
以上就是使用邻接表实现图的存储和遍历的过程。