用C语言写图的建立-邻接矩阵

好的，我们来看一下用C语言写图的邻接矩阵的代码：

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

#define MAXV 100  // 图中最多顶点数目

int mat[MAXV][MAXV];    // 图的邻接矩阵
int n;  // 顶点数

int main()
{
    scanf("%d", &n);    // 读入顶点数
    int i, j;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            scanf("%d", &mat[i][j]);    // 读入边权值
        }
    }

    // 打印邻接矩阵
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            printf("%d ", mat[i][j]);
        }
        printf("\n");
    }

    return 0;
}

这段代码首先读入了图的顶点数n，然后通过嵌套的for循环接收各个边的权重，并将它们存储到邻接矩阵mat[][]中。最后再通过另一个for循环打印邻接矩阵的内容。

相关问题

用C语言写图的建立-邻接矩阵，涉及算法

，你能给我讲讲吗？

当使用邻接矩阵表示图时，需要声明一个二维数组。数组的行和列分别表示图中所有节点的编号。如果两个节点之间有连边，则在相应位置上记录边的权值。如果两个节点之间没有连边，则在相应的位置上记录一个特定的值，例如0或无穷大。

具体实现时，可以使用类似下面的代码：

#define MAX_N 100 //最大节点个数

int graph[MAX_N][MAX_N];

//初始化邻接矩阵
void initGraph() {
    //将所有的值设为0或者无穷大
    for(int i = 0; i < MAX_N; i++) {
        for(int j = 0; j < MAX_N; j++) {
            graph[i][j] = 0;
        }
    }
}

//添加一条边
void addEdge(int u, int v, int w) {
    graph[u][v] = w; //有向图
    graph[v][u] = w; //无向图
}

//遍历节点u的所有邻居节点
void traverseNeighbors(int u) {
    for(int v = 0; v < MAX_N; v++) {
        if(graph[u][v] != 0) {
            //v是u的邻居节点
        }
    }
}

算法实现上，常见的操作包括求解图的连通性、最短路、最小生成树等等，它们都可以在邻接矩阵上高效地实现。不同的算法涉及不同的细节和优化，这里就不再进一步展开了。

用c语言写一个用邻接矩阵存储图的prim

以下是使用邻接矩阵存储图的Prim算法的C语言代码：

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

#define V 5

int minKey(int key[], int visited[]) {
    int min = INT_MAX, min_index;

    for (int i = 0; i < V; i++) {
        if (visited[i] == 0 && key[i] < min) {
            min = key[i];
            min_index = i;
        }
    }

    return min_index;
}

void printMST(int parent[], int graph[V][V]) {
    printf("Edge \tWeight\n");
    for (int i = 1; i < V; i++) {
        printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);
    }
}

void primMST(int graph[V][V]) {
    int parent[V];
    int key[V];
    int visited[V];

    for (int i = 0; i < V; i++) {
        key[i] = INT_MAX;
        visited[i] = 0;
    }

    key[0] = 0;
    parent[0] = -1;

    for (int i = 0; i < V - 1; i++) {
        int u = minKey(key, visited);
        visited[u] = 1;

        for (int v = 0; v < V; v++) {
            if (graph[u][v] && visited[v] == 0 && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }

    printMST(parent, graph);
}

int main() {
    int graph[V][V] = { { 0, 2, 0, 6, 0 },
                        { 2, 0, 3, 8, 5 },
                        { 0, 3, 0, 0, 7 },
                        { 6, 8, 0, 0, 9 },
                        { 0, 5, 7, 9, 0 } };

    primMST(graph);

    return 0;
}

这里使用 `minKey` 函数来找到最小关键字的顶点，然后使用 `printMST` 函数来打印最小生成树的结果。 `primMST` 函数是主函数，其中 `key` 数组用于存储每个顶点的关键字、 `visited` 数组用于表示每个顶点是否已经被访问过、 `parent` 数组用于存储每个顶点的父结点。