c - 用 C 实现 2D 网格网络(图)及其邻接矩阵

Question

我想在 C 中创建一个具有 10000 个节点(实际上是 100*100 )和周期性条件的 2d 网格图。我不知 Prop 体该怎么做？

之后我想获得该图的邻接矩阵，但我对此一无所知。

我可以使用 Networkx 在 python 中轻松完成这些操作。但在 C 中我不知道该怎么做。请帮忙。

Answer 1

邻接矩阵

邻接矩阵是将图 G = {V, E} 表示为 bool 矩阵的一种方式。

矩阵的大小为 VxV，其中 V 是图中的顶点数，条目 Aij 的值为 1 > 或 0 取决于是否存在从顶点 i 到顶点 j 的边。

在有向图的情况下，矩阵关于对角线对称，因为每条边 (i,j) 也有一条边 (j,i)。

伪代码:

int Node,Edge;
int matrix[100][100];
scanf("%d%d",&Node,&Edge);
for(i=0;i<Edge;i++)
{
int n1,n2,cost;
scanf("%d%d%d",&n1,&n2,&cost);
matrix[n1][n2]=cost;
matrix[n2][n1]=cost;
}

邻接矩阵的缺点

邻接矩阵的 VxV 空间要求使其成为内存消耗大户。野外图形通常没有太多连接，这就是邻接表对于大多数任务来说是更好选择的主要原因。

虽然基本操作很简单，但使用邻接矩阵表示时，像 inEdges 和 outEdges 这样的操作会很昂贵。

邻接列表

邻接表将图表示为链表数组。

数组的索引代表一个顶点，其链表中的每个元素代表与该顶点形成边的其他顶点。

伪代码:

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

struct node
{
    int vertex;
    struct node* next;
};
struct node* createNode(int);

struct Graph
{
    int numVertices;
    struct node** adjLists;
};

struct Graph* createGraph(int vertices);
void addEdge(struct Graph* graph, int src, int dest);
void printGraph(struct Graph* graph);

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

    printGraph(graph);

    return 0;
}




    struct node* createNode(int v)
    {
        struct node* newNode = malloc(sizeof(struct node));
        newNode->vertex = v;
        newNode->next = NULL;
        return newNode;
    }


    struct Graph* createGraph(int vertices)
    {
        struct Graph* graph = malloc(sizeof(struct Graph));
        graph->numVertices = vertices;



    graph->adjLists = malloc(vertices * sizeof(struct node*));

    int i;
    for (i = 0; i < vertices; i++)
        graph->adjLists[i] = NULL;

    return graph;
}

void addEdge(struct Graph* graph, int src, int dest)
{
    // Add edge from src to dest
    struct node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // Add edge from dest to src
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

void printGraph(struct Graph* graph)
{
    int v;
    for (v = 0; v < graph->numVertices; v++)
    {
        struct node* temp = graph->adjLists[v];
        printf("\n Adjacency list of vertex %d\n ", v);
        while (temp)
        {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("\n");
    }
}

使用 vector 的邻接表:

通过使用“Vector”，您不需要提及大小，只需要提及最大节点。

输入:

6 8 //node-edge
1 2 //node1-node2
1 4
2 4
2 5
4 5
5 3
3 6
6 6

代码是这样的。

伪代码:

#include<cstdio>
#include<vector>
using namespace std;
#define MAX 100000 //maximum node
vector<int>edges[MAX];
vector<int>cost[MAX]; //parallel vector to store costs;
int main()
{
int N,E,i;

scanf("%d%d",&N,&E);
for(i=1;i<=E;i++)
{
int x,y;
scanf("%d%d",&x,&y);
edges[x].push_back(y);
edges[y].push_back(x);
cost[x].push_back(1);
cost[y].push_back(1);
}
return 0;
}