Внедрение 2D Grid Network (Graph) и матрицы смежности в C - PullRequest
Новая
       65

Внедрение 2D Grid Network (Graph) и матрицы смежности в C

0 голосов
/ 26 ноября 2018

Я хочу создать 2-мерную сетку с 10000 узлами (фактически 100 * 100) с периодическими условиями в Си.Я не знаю точно, как мне это сделать?

после этого я хочу получить матрицу смежности этого графа, и снова я понятия не имею об этом.

Я легко делаю эти вещи на python с Networkx.но в CI не знаю, как это сделать.пожалуйста, помогите.

1 Ответ

0 голосов
/ 26 ноября 2018

Матрица смежности

Матрица смежности - это способ представления графа G = {V, E} в виде матрицы логических значений.

Размерматрица равна VxV, где V - количество вершин в графе, а значение записи Aij равно либо 1, либо 0, в зависимости от того, существует ли ребро от вершины i до вершины j.

enter image description here

В случае ориентированного графа матрица симметрична относительно диагонали, так как для каждого ребра (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, дороги, когдас использованием представления матрицы смежности.

Список смежности

Список смежности представляет график в виде массива связанного списка.

Индекс массивапредставляет вершину, и каждый элемент в его связанном списке представляет другие вершины, которые образуют ребро с вершиной.

enter image description here

enter image description here

Псевдокод: 

#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 ', вы не можете'Не нужно указывать размер, нужно только указать максимальный узел.

Ввод: 

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;
}
...