有向图

有向图是图的一种类型，其中的边具有方向性。这意味着从一个顶点（节点）到另一个顶点的连接是有方向的。有向图广泛应用于各种场景，如网络路由、拓扑排序和任务调度。

文章目录

基本概念

顶点 (Vertex) :
- 有向图中的基本单元，通常用字母表示，如A, B, C等。
边 (Edge) :
- 连接两个顶点的线段，具有方向性。例如，从顶点A到顶点B的边记作(A, B)。
入度 (In-degree) :
- 顶点作为目标（终点）的边的数量。例如，如果顶点B有三条指向它的边，则B的入度为3。
出度 (Out-degree) :
- 顶点作为源（起点）的边的数量。例如，如果顶点A有两条从它出发的边，则A的出度为2。
路径 (Path) :
- 顶点序列，其中每对连续的顶点之间存在一条边。例如，A -> B -> C 是一个路径。
环 (Cycle) :
- 至少有一个顶点重复出现的路径。例如，A -> B -> A 是一个环。
强连通图 (Strongly Connected Graph) :
- 如果对于每一对顶点u和v，存在从u到v和从v到u的路径，则该图是强连通的。
拓扑排序 (Topological Sorting) :
- 仅适用于有向无环图（DAG），将所有顶点排成一个线性序列，使得对于每条边(u, v)，顶点u在顶点v之前。

表示方法

邻接矩阵 (Adjacency Matrix) :
- 使用二维数组表示图。如果顶点i和j之间有一条边，则matrix[i][j] = 1；否则为0。
- 优点：查找任意两个顶点之间的边非常快速（O(1)）。
- 缺点：空间复杂度高，尤其是对于稀疏图。
邻接表 (Adjacency List) :
- 使用数组和链表的组合来表示图。每个顶点有一个链表，记录所有与该顶点相连的其他顶点。
- 优点：节省空间，适用于稀疏图。
- 缺点：查找任意两个顶点之间的边需要O(V)的时间复杂度（V是顶点的数量）。

常见算法

深度优先搜索 (DFS) :

使用栈或递归来遍历图的所有节点。常用于检测环、连通性分析和拓扑排序。

def dfs(graph, vertex, visited):
    if vertex not in visited:
        print(vertex)
        visited.add(vertex)
        for neighbor in graph[vertex]:
            dfs(graph, neighbor, visited)

广度优先搜索 (BFS) :

使用队列来遍历图的所有节点。常用于最短路径算法。

from collections import deque

def bfs(graph, start):
    queue = deque([start])
    visited = set()
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            print(vertex)
            visited.add(vertex)
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    queue.append(neighbor)

拓扑排序 (Topological Sorting) :

仅适用于有向无环图（DAG）。可以使用Kahn算法或深度优先搜索来实现。

def topological_sort(graph):
    in_degree = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1

    queue = [u for u in in_degree if in_degree[u] == 0]
    topo_order = []

    while queue:
        vertex = queue.pop(0)
        topo_order.append(vertex)

        for neighbor in graph[vertex]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return topo_order

示例

假设我们有一个有向图，顶点为A, B, C, D，边如下：

A -> B
A -> C
B -> D
C -> D

我们可以用邻接表表示这个图：

graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}

使用DFS遍历该图：

visited = set()
dfs(graph, 'A', visited)
# 输出: A B D C 或者 A C D B，取决于实现细节

使用BFS遍历该图：

bfs(graph, 'A')
# 输出: A B C D

使用拓扑排序：

topo_order = topological_sort(graph)
print(topo_order)
# 输出: ['A', 'B', 'C', 'D']

深度优先搜索（Depth-First Search, DFS）是一种用于遍历或搜索图或树的算法。它从一个起始节点开始，尽可能深入地访问每个分支，直到无法继续为止，然后回溯并访问其他未访问的节点。

有向图的DFS

在有向图中，DFS可以通过递归或栈来实现。以下是详细的步骤：

初始化:
- 创建一个布尔数组 visited 来记录每个节点是否被访问过。
- 根据需要选择起始节点。
递归DFS:
- 从起始节点开始，标记该节点为已访问。
- 遍历该节点的所有邻接节点（即出边），如果某个邻接节点未被访问，则递归调用DFS函数。
栈实现的DFS:
- 使用一个栈来存储待访问的节点。
- 从起始节点开始，将它压入栈中。
- 当栈不为空时，执行以下操作：
  - 弹出栈顶节点，标记为已访问。
  - 将该节点的所有未访问邻接节点压入栈中。

C语言实现

下面是使用递归和栈两种方法在有向图中进行DFS的C语言实现：

递归实现

#include <stdio.h>
#include <stdlib.h>

// 定义一个节点结构体
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 定义一个邻接表中的列表结构体
typedef struct List {
    Node* head;
} List;

// 定义一个图结构体
typedef struct Graph {
    int numVertices;
    List* adjLists;
    int* visited;  // 访问标记数组
};

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 创建图
Graph* createGraph(int numVertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = numVertices;

    // 动态分配邻接表和访问标记数组
    graph->adjLists = (List*)malloc(numVertices * sizeof(List));
    graph->visited = (int*)malloc(numVertices * sizeof(int));

    for (int i = 0; i < numVertices; i++) {
        graph->adjLists[i].head = NULL;
        graph->visited[i] = 0;  // 初始化为未访问
    }

    return graph;
}

// 添加边
void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src].head;
    graph->adjLists[src].head = newNode;

    // 如果需要有向图，不需要下面的两行代码
    /* 
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest].head;
    graph->adjLists[dest].head = newNode; 
    */
}

// 递归DFS函数
void DFS_recursive(Graph* graph, int vertex) {
    struct Node* adjList = graph->adjLists[vertex].head;
    struct Node* temp = adjList;

    graph->visited[vertex] = 1;  // 标记当前节点为已访问
    printf("Visited %d \n", vertex);

    while (temp != NULL) {
        int connectedVertex = temp->data;
        if (!graph->visited[connectedVertex]) {  // 如果邻接节点未被访问，则递归调用DFS
            DFS_recursive(graph, connectedVertex);
        }
        temp = temp->next;
    }
}

int main() {
    Graph* graph = createGraph(4);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 0);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 3);

    printf("DFS recursive traversal starting from vertex 2:\n");
    DFS_recursive(graph, 2);

    return 0;
}

栈实现

#include <stdio.h>
#include <stdlib.h>

// 定义一个节点结构体
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 定义一个邻接表中的列表结构体
typedef struct List {
    Node* head;
} List;

// 定义一个图结构体
typedef struct Graph {
    int numVertices;
    List* adjLists;
    int* visited;  // 访问标记数组
};

// 定义一个栈节点结构体
typedef struct StackNode {
    int data;
    struct StackNode* next;
} StackNode;

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 创建图
Graph* createGraph(int numVertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = numVertices;

    // 动态分配邻接表和访问标记数组
    graph->adjLists = (List*)malloc(numVertices * sizeof(List));
    graph->visited = (int*)malloc(numVertices * sizeof(int));

    for (int i = 0; i < numVertices; i++) {
        graph->adjLists[i].head = NULL;
        graph->visited[i] = 0;  // 初始化为未访问
    }

    return graph;
}

// 添加边
void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src].head;
    graph->adjLists[src].head = newNode;

    // 如果需要有向图，不需要下面的两行代码
    /* 
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest].head;
    graph->adjLists[dest].head = newNode; 
    */
}

// 创建栈节点
StackNode* createStackNode(int data) {
    StackNode* stackNode = (StackNode*)malloc(sizeof(StackNode));
    stackNode->data = data;
    stackNode->next = NULL;
    return stackNode;
}

// 压入栈
void push(StackNode** root, int data) {
    StackNode* stackNode = createStackNode(data);
    stackNode->next = *root;
    *root = stackNode;
}

// 弹出栈顶元素
int pop(StackNode** root) {
    if (*root == NULL) return -1;  // 栈空
    int popped = (*root)->data;
    StackNode* temp = *root;
    *root = (*root)->next;
    free(temp);
    return popped;
}

// 检查栈是否为空
int isEmpty(StackNode* root) {
    return !root;
}

// 栈实现的DFS函数
void DFS_iterative(Graph* graph, int startVertex) {
    StackNode* stack = NULL;

    // 将起始节点压入栈中
    push(&stack, startVertex);
    while (!isEmpty(stack)) {
        // 弹出栈顶元素并标记为已访问
        int vertex = pop(&stack);
        if (!graph->visited[vertex]) {
            graph->visited[vertex] = 1;
            printf("Visited %d \n", vertex);
        }

        struct Node* adjList = graph->adjLists[vertex].head;
        while (adjList != NULL) {
            int connectedVertex = adjList->data;
            if (!graph->visited[connectedVertex]) {
                push(&stack, connectedVertex);  // 将未访问的邻接节点压入栈中
            }
            adjList = adjList->next;
        }
    }
}

int main() {
    Graph* graph = createGraph(4);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 0);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 3);

    printf("DFS iterative traversal starting from vertex 2:\n");
    DFS_iterative(graph, 2);

    return 0;
}

广度优先搜索（Breadth-First Search, BFS）是一种用于遍历或搜索图或树的算法。它从一个起始节点开始，逐层访问每个节点的所有邻接节点，直到所有节点都被访问过。

有向图的BFS

在有向图中，BFS通常使用队列来实现。以下是详细的步骤：

初始化:
- 创建一个布尔数组 visited 来记录每个节点是否被访问过。
- 根据需要选择起始节点，并将其标记为已访问。
队列实现的BFS:
- 使用一个队列来存储待访问的节点。
- 从起始节点开始，将它加入队列并标记为已访问。
- 当队列不为空时，执行以下操作：
  - 弹出队列的第一个节点，并访问它（打印或处理）。
  - 将该节点的所有未访问邻接节点加入队列中。

C语言实现

下面是使用队列实现的有向图BFS的C语言代码：

#include <stdio.h>
#include <stdlib.h>

// 定义一个节点结构体
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 定义一个邻接表中的列表结构体
typedef struct List {
    Node* head;
} List;

// 定义一个图结构体
typedef struct Graph {
    int numVertices;
    List* adjLists;
    int* visited;  // 访问标记数组
};

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 创建图
Graph* createGraph(int numVertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = numVertices;

    // 动态分配邻接表和访问标记数组
    graph->adjLists = (List*)malloc(numVertices * sizeof(List));
    graph->visited = (int*)malloc(numVertices * sizeof(int));

    for (int i = 0; i < numVertices; i++) {
        graph->adjLists[i].head = NULL;
        graph->visited[i] = 0;  // 初始化为未访问
    }

    return graph;
}

// 添加边
void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src].head;
    graph->adjLists[src].head = newNode;

    // 如果需要有向图，不需要下面的两行代码
    /* 
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest].head;
    graph->adjLists[dest].head = newNode; 
    */
}

// 队列节点结构体
typedef struct QueueNode {
    int data;
    struct QueueNode* next;
} QueueNode;

// 创建队列节点
QueueNode* createQueueNode(int data) {
    QueueNode* queueNode = (QueueNode*)malloc(sizeof(QueueNode));
    queueNode->data = data;
    queueNode->next = NULL;
    return queueNode;
}

// 定义队列结构体
typedef struct Queue {
    QueueNode *front, *rear;
} Queue;

// 初始化队列
void initQueue(Queue* q) {
    q->front = q->rear = NULL;
}

// 检查队列是否为空
int isEmpty(Queue* q) {
    return (q->front == NULL);
}

// 将元素入队
void enqueue(Queue* q, int data) {
    QueueNode* temp = createQueueNode(data);

    if (isEmpty(q)) {
        q->front = q->rear = temp;
        return;
    }

    q->rear->next = temp;
    q->rear = temp;
}

// 从队列中取出元素
int dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }

    QueueNode* temp = q->front;
    int data = temp->data;

    q->front = q->front->next;

    if (q->front == NULL)
        q->rear = NULL;

    free(temp);

    return data;
}

// BFS函数
void BFS(Graph* graph, int startVertex) {
    Queue queue;
    initQueue(&queue);

    // 将起始节点标记为已访问并入队
    graph->visited[startVertex] = 1;
    enqueue(&queue, startVertex);

    while (!isEmpty(&queue)) {
        // 出队
        int vertex = dequeue(&queue);
        printf("Visited %d \n", vertex);

        struct Node* adjList = graph->adjLists[vertex].head;

        // 遍历所有邻接节点
        while (adjList != NULL) {
            int connectedVertex = adjList->data;

            // 如果邻接节点未被访问，标记为已访问并入队
            if (!graph->visited[connectedVertex]) {
                graph->visited[connectedVertex] = 1;
                enqueue(&queue, connectedVertex);
            }
            adjList = adjList->next;
        }
    }
}

int main() {
    Graph* graph = createGraph(4);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 0);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 3);

    printf("BFS traversal starting from vertex 2:\n");
    BFS(graph, 2);

    return 0;
}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30

基本概念

表示方法

常见算法

示例

有向图的DFS

C语言实现

递归实现

栈实现

有向图的BFS

C语言实现

赞过：

发表评论取消回复