1067: 有向图的邻接表存储强连通判断

邻接表是一种常用的有向图存储结构，可以用于判断有向图是否强连通。具体方法如下：

1. 对于有向图G，构建其邻接表表示。

2. 对于每个顶点v，进行深度优先遍历（DFS），标记所有可以到达的顶点。

3. 对于每个顶点u，如果存在一个顶点v不能到达u，或者存在一个顶点w不能从u到达，那么图G不是强连通图。

4. 如果所有顶点都可以到达任意一个顶点，那么图G是强连通图。

5. 如果图G不是强连通图，可以通过对图的反向图进行上述操作，判断反向图是否强连通。

6. 如果反向图也不是强连通图，那么图G就不是强连通图。

以上就是使用邻接表存储有向图进行强连通判断的方法。

相关问题

已知无向图的邻接表，判断该邻接表是否连通的c语言代码

可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来判断邻接表是否连通。以下是使用DFS的示例代码：

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

#define MAX_VERTEX_NUM 100

typedef struct ArcNode {
    int adjvex; // 相邻结点的下标
    struct ArcNode *nextarc; // 指向下一个相邻结点的指针
} ArcNode;

typedef struct VertexNode {
    int data; // 顶点的数据
    ArcNode *firstarc; // 指向第一个相邻结点的指针
} VertexNode;

typedef struct Graph {
    VertexNode vertex[MAX_VERTEX_NUM]; // 图的顶点数组
    int vexnum, arcnum; // 顶点数和边数
} Graph;

int visited[MAX_VERTEX_NUM]; // 标记顶点是否被访问过

void DFS(Graph *G, int v) {
    visited[v] = 1; // 标记顶点v已被访问
    ArcNode *p = G->vertex[v].firstarc;
    while (p != NULL) {
        int w = p->adjvex; // w是v的相邻结点
        if (!visited[w]) { // 如果w未被访问，则对w进行DFS
            DFS(G, w);
        }
        p = p->nextarc;
    }
}

int main() {
    // 读入邻接表
    Graph G;
    scanf("%d%d", &G.vexnum, &G.arcnum);
    for (int i = 0; i < G.vexnum; i++) {
        G.vertex[i].data = i; // 顶点数据为下标
        G.vertex[i].firstarc = NULL; // 初始时没有相邻结点
    }
    for (int i = 0; i < G.arcnum; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        // 在u和v之间建立一条边
        ArcNode *p = (ArcNode *) malloc(sizeof(ArcNode));
        p->adjvex = v;
        p->nextarc = G.vertex[u].firstarc;
        G.vertex[u].firstarc = p;
        // 由于是无向图，还需要在v和u之间建立一条边
        p = (ArcNode *) malloc(sizeof(ArcNode));
        p->adjvex = u;
        p->nextarc = G.vertex[v].firstarc;
        G.vertex[v].firstarc = p;
    }

    // DFS遍历图，并判断是否连通
    for (int i = 0; i < G.vexnum; i++) {
        visited[i] = 0; // 初始化所有顶点未被访问
    }
    DFS(&G, 0); // 从任意一个顶点开始遍历
    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            printf("该图不连通\n");
            return 0;
        }
    }
    printf("该图连通\n");

    return 0;
}

该程序使用邻接表存储图，并对每个顶点进行DFS遍历。如果遍历过程中发现有未被访问的顶点，则图不是连通的。

输入：一个基于邻接表或邻接矩阵存储的无向图 实现：用非递归算法实现深度或广度遍历一个无向图，并输出遍历结果，其中如果图不联通，可能需要多次遍历。

以下是基于邻接表存储的无向图的非递归算法实现深度优先遍历的代码：

def DFS(graph):
    visited = set()  # 用一个集合记录已经访问过的节点
    for start_node in graph.keys():  # 遍历所有节点，防止有不连通的情况
        if start_node not in visited:
            stack = [start_node]  # 用一个栈来实现非递归遍历
            while stack:
                node = stack.pop()
                if node not in visited:
                    visited.add(node)
                    print(node)
                    for neighbor in graph[node]:
                        stack.append(neighbor)

以下是基于邻接矩阵存储的无向图的非递归算法实现广度优先遍历的代码：

from collections import deque

def BFS(graph):
    visited = set()
    for start_node in graph.keys():
        if start_node not in visited:
            queue = deque([start_node])  # 用一个双端队列来实现非递归遍历
            while queue:
                node = queue.popleft()
                if node not in visited:
                    visited.add(node)
                    print(node)
                    for neighbor_idx, is_connected in enumerate(graph[node]):
                        if is_connected:
                            queue.append(list(graph.keys())[neighbor_idx])

需要注意的是，如果图不连通，需要多次调用遍历函数。具体实现可以在每次调用前判断是否还有未访问过的节点即可。