图论邻接表和邻接矩阵

图论中，邻接矩阵和邻接表是两种常见的图的表示方法。邻接矩阵是一个二维数组，其中行和列分别表示图中的顶点，而数组中的元素表示这两个顶点之间是否有边相连。而邻接表则是由每个顶点的邻接点列表组成的数组，其中每个邻接点列表包含了与该顶点相连的所有顶点。邻接表可以解决邻接矩阵空间浪费的问题，并且邻接表本身并没有什么大的缺陷。但是对于有向图而言，同时表示一个顶点的出度和入度比较麻烦，需要有邻接表和逆邻接表同时表示。邻接矩阵和邻接表各有优缺点，应根据具体情况选择使用。

相关问题

用c语言实现建立一个具有n个结点的无向图的邻接矩阵和邻接表。 （1）、设计一个将邻接矩阵转换为邻接表的算法 （2）、设计一个将邻接表转换为邻接矩阵的算法 （3）、设计以邻接表为存储结构的图的广度优先搜索算法。 （4）、设计以邻接矩阵为存储结构的图的深度优先搜索算法。

这是一个比较复杂的问题，需要涉及到图的基本概念和算法，需要一定的编程基础和图论知识。我会提供一些参考代码，但是不保证完全正确和完整，请仔细阅读并自行理解。

1、邻接矩阵转换为邻接表的算法：

// 邻接矩阵转换为邻接表
void matrixToList(int matrix[][MAX], int n, Node *list[]) {
    int i, j;
    for (i = 0; i < n; i++) {
        // 创建一个新的节点
        Node *newNode = (Node*)malloc(sizeof(Node));
        newNode->data = i;
        newNode->next = NULL;
        list[i] = newNode;
        Node *temp = newNode;
        for (j = 0; j < n; j++) {
            if (matrix[i][j] == 1 && i != j) {
                // 创建一个新的邻接节点
                Node *adjNode = (Node*)malloc(sizeof(Node));
                adjNode->data = j;
                adjNode->next = NULL;
                temp->next = adjNode;
                temp = adjNode;
            }
        }
    }
}

2、邻接表转换为邻接矩阵的算法：

// 邻接表转换为邻接矩阵
void listToMatrix(Node *list[], int n, int matrix[][MAX]) {
    int i, j;
    for (i = 0; i < n; i++) {
        Node *temp = list[i]->next;
        while (temp != NULL) {
            j = temp->data;
            matrix[i][j] = 1;
            temp = temp->next;
        }
    }
}

3、以邻接表为存储结构的图的广度优先搜索算法：

void BFS(Node *list[], int start, int n) {
    int visited[MAX] = {0};
    Queue *q = createQueue();
    visited[start] = 1;
    printf("%d ", start);
    enqueue(q, start);
    while (!isEmpty(q)) {
        int v = dequeue(q);
        Node *temp = list[v]->next;
        while (temp != NULL) {
            int w = temp->data;
            if (!visited[w]) {
                visited[w] = 1;
                printf("%d ", w);
                enqueue(q, w);
            }
            temp = temp->next;
        }
    }
}

4、以邻接矩阵为存储结构的图的深度优先搜索算法：

void DFS(int matrix[][MAX], int visited[], int v, int n) {
    int i;
    visited[v] = 1;
    printf("%d ", v);
    for (i = 0; i < n; i++) {
        if (matrix[v][i] && !visited[i]) {
            DFS(matrix, visited, i, n);
        }
    }
}

void DFSTraverse(int matrix[][MAX], int n) {
    int visited[MAX] = {0};
    int i;
    for (i = 0; i < n; i++) {
        if (!visited[i]) {
            DFS(matrix, visited, i, n);
        }
    }
}

以上是参考代码，可能还需要根据实际情况进行调整和修改。

邻接矩阵和邻接表的画法

邻接矩阵和邻接表是图论中常用的两种表示图的数据结构。

1. **邻接矩阵**：它是一个二维数组，其中行代表起点，列表示终点。如果两个顶点之间有边相连，对应的矩阵元素值通常是1（无向图）或0/1（带权重）。对于每个顶点i，它的列索引就是连接到的其他所有顶点，使得A[i][j]=1。例如，如果A[i][j] = 1，表示顶点i与j直接相连。

- 矩阵形式直观易懂，查找两点间是否有边的时间复杂度为O(1)。
- 但空间效率不高，当图非常稀疏（即边数远小于顶点数的平方）时，会浪费大量存储空间。

2. **邻接表**：它是一个链表的集合，每个顶点对应一个链表，链表中的节点包含了与该顶点相邻的所有其他顶点。这种数据结构通常包含一个额外的哈希表或数组来快速查找特定顶点的邻接顶点。

- 当图是稠密的（边数接近于顶点数的平方），邻接表更节省空间。
- 查找任意两点间的边需要遍历链表，时间复杂度为O(deg(v))，deg(v)是目标顶点的度数。