0

I know this may sound a lot naive, but can someone please explain me how can i implement graphs in C language. I have read the theory, but I am not able to get off the blocks with graph programming.

I would really appreciate if someone could explain how would to create a graph using adjacency lists and adjacency matrix and how would you perform breadth first search and depth first search in C code with some explanations

And before anything, I would like to tell you that this is not a homework. I really want to learn graphs but can't afford a tutor.

4

2 回答 2

2

我假设这里的图是顶点和边的集合。为此，您需要一个指向结构的指针数组。这是图的邻接表表示。这些结构至少有一个值，即节点号和指向另一个结构的指针。在将新节点插入图形时，只需转到数组的适当索引并在开始时推送节点。这是插入的 O(1) 时间。我的实现可能会帮助您了解它的实际工作原理。如果你在 C 方面有很好的技能，那么理解代码不会花费太多时间。

//  Graph implementation by adjacency list

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

#define MAX_SIZE 1000

typedef struct node{
    int number;
    struct node * next;
} Node;


//  U is starting node, V is ending node
void addNode (Node *G[], int U, int V, int is_directed)
{
    Node * newnode = (Node *)malloc(sizeof(Node));
    newnode->number = V;
    newnode->next = G[U];
    G[U] = newnode;

//  0 for directed, 1 for undirected
    if (is_directed)
    {
        Node * newnode = (Node *)malloc(sizeof(Node));
        newnode->number = U;
        newnode->next = G[V];
        G[V] = newnode;
    }
}

void printgraph(Node *G[], int num_nodes)
{
    int I;
    for (I=0; I<=num_nodes; I++)
    {
        Node *dum = G[I];
        printf("%d : ",I);
        while (dum != NULL)
        {
            printf("%d, ",dum->number);
            dum =dum->next;
        }
        printf("\n");
    }

}



void dfs (Node *G[], int num_nodes, int start_node)
{
    int stack[MAX_SIZE];
    int color[num_nodes+1];
    memset (color, 0, sizeof(color));
    int top = -1;
    stack[top+1] = start_node;
    top++;
    while (top != -1)
    {
        int current = stack[top];
        printf("%d  ",current);
        top--;
        Node *tmp = G[current];
        while (tmp != NULL)
        {
            if (color[tmp->number] == 0)
            {
                stack[top+1] = tmp->number;
                top++;
                color[tmp->number] = 1;
            }
            tmp = tmp->next;
        }
    }

}

void bfs (Node *G[], int num_nodes, int start_node)
{
    int queue[MAX_SIZE];
    int color[num_nodes+1];
    memset (color, 0, sizeof (color));
    int front=-1, rear=-1;
    queue[rear+1] = start_node;
    rear++;printf("\n\n");
    while (front != rear)
    {
        front++;
        int current = queue[front];
        printf("%d  ",current);

        Node *tmp = G[current];
        while (tmp != NULL)
        {
            if (color[tmp->number] == 0)
            {
                queue[rear+1] = tmp->number;
                rear++;
                color[tmp->number] = 1;
            }
            tmp = tmp->next;
        }
    }

}  

int main(int argc, char **argv)
{
    int num_nodes;
    // For Demo take num_nodes = 4
    scanf("%d",&num_nodes);
    Node *G[num_nodes+1];
    int I;
    for (I=0; I<num_nodes+1 ;I++ )
        G[I] = NULL;

    addNode (G, 0, 2, 0);
    addNode (G, 0, 1, 0);
    addNode (G, 1, 3, 0);
    addNode (G, 2, 4, 0);
    addNode (G, 2, 1, 0);
    printgraph( G, num_nodes);
    printf("DFS on graph\n");
    dfs(G, num_nodes, 0);
    printf("\n\nBFS on graph\n");
    bfs(G, num_nodes, 0);

    return 0;
}
于 2012-07-18T16:36:32.657 回答
0

好吧，一个真正幼稚和基本的答案是，可以使用包含指向其他此类数据结构的指针的数据结构在 C 中表示图形。图实际上只是双向链表，可以从单个节点具有多个链接。如果您还没有消化链表和双向链表，那将是一个很好的起点。

假设你有一个邻接表，{a,b},{b,c},{d},{b,e}。首先，你解析它并列出你所有的独特项目。（一个常规的链表、数组等等，它只是一个临时结构来帮助你。你可以绕过它，即时执行它，并且可能会获得加速，但这很简单。）遍历该列表，你会生成一个每个项目的节点。对于每个节点，您再次遍历邻接列表并在它看到自己时创建一条边。这是节点内部指向另一个节点的指针。

最后，您拥有所有节点的常规列表，因此您不会丢失那个单独挂出的“d”节点。您还拥有所有节点的图表，因此您可以了解它们之间的关系。

搜索
跨图搜索是一个非常基本的想法。从一个节点开始，比较，移动到它的一个邻居，然后再做一次。虽然有很多陷阱。就像进入一个无限循环并知道何时停止。

如果您想要比您已经在网上找到的更好的解释，您将不得不提出更具体的问题。

于 2012-07-18T16:49:40.923 回答