时间戳

首页 > 解决方案 > 图：用于邻接矩阵

c - 图：用于邻接矩阵

问题描述

我必须编写一个程序，它将以邻接表和邻接矩阵的形式显示图形结果。我已经通过 YT 上的教程指导自己如何实现邻接列表，并使用当前存储的数据（用户正在介绍自己，例如节点数、边数、边连接的边数以及哪一个）我想知道/了解如何使用已经存储的数据来构建邻接矩阵。

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

struct node
{
    int data;
    struct node *next;
};
void read_graf(struct node *ad[], int no_of_nodes);

void print_graf(struct node *ad[], int no_of_nodes);

int main()
{
   int op;
   int i,j,k, nodes;
   begin:
   printf("Type in the number of edges: ");
   scanf("%d", &nodes);
   struct node *adj[nodes];
   for (i=0;i<nodes;i++)
        adj[i] = NULL;
   read_graf(adj,nodes);
   print_graf(adj,nodes);

   printf("\nDo you want to try again? 1 for yes and 0 for no: ");
   scanf("%d", &op);
   if (op==1)
    goto begin;
   else
    {
    printf("Thank you for visiting! :)");
    exit(0);
    }
   return 0;
}

void read_graf(struct node *ad[], int no_of_nodes)
{
    struct node *new_node;
    int i,j,k, val;
    for (i=0;i<no_of_nodes;i++)
    {
        struct node *last= NULL;
        printf("\n To how many edges is edge %d connected to: ", i+1);
        scanf("%d", &k);
        for (j=0;j<k;j++)
        {
            printf("To which edges is it connected : ");
            scanf("%d", &val);
            new_node = (struct node *)malloc(sizeof(struct node*));
            new_node->data = val;
            new_node->next = NULL;
            if(ad[i]==NULL)
                ad[i]= new_node;
            else
            last->next = new_node;
            last = new_node;
        }
    }
}

void print_graf(struct node *ad[], int no_of_nodes)
{
    struct node *ptr = NULL;
    int i,j;
    for(i=0;i<no_of_nodes;i++)
    {
        ptr = ad[i];
        printf("\n x%d : ", i+1);
        while(ptr != NULL)
        {
            printf("%d,\t", ptr->data);
            ptr = ptr->next;
        }
        printf("0");
    }
}

标签： cpointersmatrixgraph

解决方案

如果您只需要打印出邻接矩阵并假设 a1表示节点i和节点j之间的连接，则只需稍微修改print_graf函数内部的内部循环。

void print_as_mat(struct node *ad[], int no_of_nodes)
{
    struct node *ptr = NULL;
    
    for(int i = 0; i < no_of_nodes; ++i)
    {
        ptr = ad[i];

        // Loop over all the possible nodes
        for(int j = 0; j < no_of_nodes; ++j)
        {
            if ( ptr  &&  ptr->data == j ) {
                //        ^^^^^^^^^^^^^^ Check if the index correspond to the 
                //                       current node in the adjacency list.
                printf(" 1");

                // update the current node in the list, but only here.
                ptr = ptr->next;
            }
            else {
                printf(" 0");
            }
        }
        // The row is completed.
        putchar('\n');
    }
}

推荐阅读