有向图的正邻接链表和逆邻接链表。
时间: 2024-01-04 14:19:50 浏览: 29
有向图的正邻接链表和逆邻接链表是用来表示有向图中节点之间关系的数据结构。
正邻接链表是指对于每个节点,记录其指向其他节点的边的信息。逆邻接链表是指对于每个节点,记录指向该节点的边的信息。
下面是一个示例来说明正邻接链表和逆邻接链表的概念:
假设有以下有向图:
```
1 -> 2
1 -> 3
2 -> 3
3 -> 4
```
对于节点1,其正邻接链表为:[2, 3],表示节点1指向节点2和节点3。
对于节点2,其正邻接链表为:,表示节点2指向节点3。
对于节点3,其正邻接链表为:,表示节点3指向节点4。
对于节点2,其逆邻接链表为:,表示指向节点2的边来自节点1。
对于节点3,其逆邻接链表为:[1, 2],表示指向节点3的边来自节点1和节点2。
对于节点4,其逆邻接链表为:,表示指向节点4的边来自节点3。
通过正邻接链表和逆邻接链表,我们可以方便地获取节点的出度和入度,以及节点之间的关系。
相关问题
建立一个有向图的邻接链表表示,实现对图广度优先遍历
首先,我们需要定义一个图的数据结构,包含节点个数和邻接链表:
```python
class Graph:
def __init__(self, num_of_vertices):
self.num_of_vertices = num_of_vertices
self.adjacency_list = [[] for _ in range(num_of_vertices)]
def add_edge(self, v, w):
self.adjacency_list[v].append(w)
```
接下来,我们可以使用一个队列来实现广度优先遍历,从起始节点开始,将其加入队列中,然后遍历其相邻节点,将其加入队列中,再依次遍历相邻节点的相邻节点,直到队列为空。
```python
from collections import deque
def bfs(graph, start):
visited = [False] * graph.num_of_vertices
queue = deque([start])
visited[start] = True
while queue:
vertex = queue.popleft()
print(vertex, end=" -> ")
for adjacent_vertex in graph.adjacency_list[vertex]:
if not visited[adjacent_vertex]:
visited[adjacent_vertex] = True
queue.append(adjacent_vertex)
```
最后,我们可以创建一个图并测试广度优先遍历的代码:
```python
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)
print("BFS traversal:")
bfs(g, 2)
```
输出结果为:
```
BFS traversal:
2 -> 0 -> 3 -> 1 ->
```
C语言代码建立一个有向图的邻接链表表示,实现对图广度优先遍历
以下是 C 语言代码建立有向图的邻接链表表示,以及实现对图的广度优先遍历:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 50 // 最大顶点数
/* 边节点结构体 */
typedef struct edgeNode {
int adjvex; // 邻接点下标
struct edgeNode *next; // 下一个邻接点指针
} EdgeNode;
/* 顶点节点结构体 */
typedef struct vertexNode {
int data; // 顶点信息
EdgeNode *firstEdge; // 第一个邻接点指针
} VertexNode;
/* 图结构体 */
typedef struct {
VertexNode vertices[MAX_VERTICES]; // 顶点数组
int numVertices; // 顶点数
int numEdges; // 边数
} Graph;
/* 初始化图 */
void initGraph(Graph *g) {
int i;
g->numVertices = 0;
g->numEdges = 0;
for (i = 0; i < MAX_VERTICES; i++) {
g->vertices[i].firstEdge = NULL;
}
}
/* 添加顶点 */
void addVertex(Graph *g, int data) {
if (g->numVertices >= MAX_VERTICES) {
printf("Error: too many vertices\n");
exit(1);
}
g->vertices[g->numVertices].data = data;
g->numVertices++;
}
/* 添加边 */
void addEdge(Graph *g, int start, int end) {
EdgeNode *newEdge;
if (start < 0 || start >= g->numVertices ||
end < 0 || end >= g->numVertices) {
printf("Error: invalid vertex index\n");
exit(1);
}
newEdge = (EdgeNode*) malloc(sizeof(EdgeNode));
newEdge->adjvex = end;
newEdge->next = g->vertices[start].firstEdge;
g->vertices[start].firstEdge = newEdge;
g->numEdges++;
}
/* 广度优先遍历 */
void BFS(Graph *g, int start) {
int visited[MAX_VERTICES] = {0};
int queue[MAX_VERTICES];
int front = 0, rear = 0;
EdgeNode *p;
printf("%d ", g->vertices[start].data);
visited[start] = 1;
queue[rear++] = start;
while (front < rear) {
int v = queue[front++];
p = g->vertices[v].firstEdge;
while (p != NULL) {
int w = p->adjvex;
if (!visited[w]) {
printf("%d ", g->vertices[w].data);
visited[w] = 1;
queue[rear++] = w;
}
p = p->next;
}
}
}
int main() {
Graph g;
initGraph(&g);
addVertex(&g, 0);
addVertex(&g, 1);
addVertex(&g, 2);
addVertex(&g, 3);
addVertex(&g, 4);
addEdge(&g, 0, 1);
addEdge(&g, 0, 2);
addEdge(&g, 1, 3);
addEdge(&g, 2, 3);
addEdge(&g, 3, 4);
BFS(&g, 0);
return 0;
}
```
以上代码中,我们使用邻接链表来表示有向图,具体实现方法是将每个顶点用一个 `VertexNode` 结构体来存储,其中包括该顶点的信息(这里我们用一个整数来表示),以及一个指向该顶点的第一个邻接点的指针 `firstEdge`。邻接点则用 `EdgeNode` 结构体来表示,其中包括邻接点的下标 `adjvex`,以及一个指向下一个邻接点的指针 `next`。
在建立好邻接链表之后,我们可以使用广度优先遍历算法对图进行遍历。具体实现方法是使用一个队列来存储待处理的顶点,从起始顶点开始,依次将它的邻接点加入队列中,然后处理队列中的下一个顶点,直到队列为空为止。在遍历的过程中,我们使用一个 `visited` 数组来记录每个顶点是否已经被访问过,避免重复访问同一顶点。