Создание списка смежности

Question

У меня проблема с созданием соседнего списка в правильном порядке.Я думаю, что есть некоторая проблема в методе CreateAdjList (void).У меня заканчиваются идеи.Пожалуйста, дайте мне несколько советов.В основном у меня есть график и создание списка смежности по соединенным ребрам.

#include <stdio.h>
#include <stdlib.h>
#define maxV 100                               
typedef struct graphnode{                        
    int vertex;
    struct graphnode *next;
}Node;
Node **node;                             
Node **nodeT; 

FILE *fp;

void initial(int nv);                            
void AdjList(void);                              
void PrintAdjList(int nv);                           


int main()
{
    int nv;

    fp= fopen("input.txt","r");
    fscanf(fp,"%d",&nv);
    initial(nv);
    CreateAdjList();
    PrintAdjList(nv);

    return 0;
}



void initial(int nv)
{
    int i;
    node = new Node *[maxV];

    for(i=1;i<=nv;i++){
        node[i] = (Node *)malloc(sizeof(Node));
        node[i]->next=NULL;


    }

}


//CREATE ADJACENCY  LIST - 
void CreateAdjList(void)
{
    int v1,v2;
    Node *ptr;

while(fscanf(fp,"%d%d",&v1,&v2)!=EOF){

        ptr = (Node *)malloc(sizeof(Node));
        ptr->vertex = v2;
        ptr->next = node[v1]->next;    //Problem could be here
        node[v1]->next = ptr;

    }

    fclose(fp);
}




//PRINT LIST
void PrintAdjList(int nv)
{
    int i;
    Node *ptr;

    for(i=1; i<=nv; i++){
        ptr = node[i]->next;
        printf("    node[%2d]  ",i);
        while(ptr != NULL){
            printf("  -->%2d", ptr->vertex);
            ptr=ptr->next;
        }
        printf("\n");
    }
    printf("\n");

}

РЕАЛЬНЫЙ ВЫХОД ПРОГРАММЫ - НЕПРАВИЛЬНЫЙ ЗАКАЗ.Я прикрепил выходной список в печатном виде.

Ввод:

8
1 2
2 3
2 5
2 6
3 4
3 7
4 3
4 8
5 1
5 6
6 7
7 6
7 8
8 8
0 0

Expected Output:
Adjacency list represenation:
1: 2 
2: 3 5 6 
3: 4 7 
4: 3 8 
5: 1 6 
6: 7 
7: 6 8 
8: 8

Мой фактический вывод отображается в неправильном порядке.Если вы посмотрите на узел, правильный порядок должен быть 2 -> 3-> 6-> 5

 node[ 1]    --> 2
 node[ 2]    --> 6  --> 5  --> 3
 node[ 3]    --> 7  --> 4
 node[ 4]    --> 8  --> 3
 node[ 5]    --> 6  --> 1
 node[ 6]    --> 7
 node[ 7]    --> 8  --> 6
 node[ 8]    --> 8

Answer 1

У меня были проблемы с этим, потому что прошло много времени с тех пор, как я сделал C:)

То, что вам нужно, - это нечто большее, как показано ниже - обратите внимание, было несколько ошибок, которые я могуне вижу, как это сработало бы.С '0 0' в конце файла и тем фактом, что вы использовали 1-> nv в циклах, никогда не было бы элемента node [0] и, следовательно, всегда бы произошел сбой.

В моем примере я оставляю массив разреженным (выделяя только те узлы, которые действительно существуют), удовлетворяя при этом другим условиям.Мне также все равно, в каком порядке они входят, так что входной файл может быть неупорядоченным.Также обратите внимание, что метод печати может нуждаться в обновлении, если данные файла имели разреженные данные (т. Е. Первое число было 10, и в нем отсутствовало что-либо вроде '9 x').

void initial(int nv)
{
    node = (Node **)malloc(maxV * sizeof(Node *));
}

//CREATE ADJACENCY  LIST - 
void CreateAdjList(void)
{
    int v1,v2;
    Node *ptr;

    while(fscanf(fp,"%d %d",&v1,&v2)!=EOF){

        ptr = (Node *)malloc(sizeof(Node));
        ptr->vertex = v2;

        if (node[v1]==NULL) {
            node[v1] = (Node *)malloc(sizeof(Node));
            node[v1]->vertex = v1;
            node[v1]->next = NULL;
        }

        Node *next = node[v1];
        while (next->next!=NULL)
            next = next->next;

        next->next = ptr;

        //ptr->next = &(*(node[v1])->next);    //Problem could be here
        //node[v1]->next = ptr;
    }

    fclose(fp);
}

Answer 2

Список смежности может представлять график очень эффективным способом.Он поддерживает индексированный массив вершин списка, чтобы представить ребра и вершины графа, как показано на рисунке ниже:

Массив ArrayList

Массив ArrayList может использоваться для реализации списка смежности графа.Ниже приведена программа, описывающая использование Array of ArrayList.

package com.vaibhav.graph;

import java.util.ArrayList;

public class Graph {
    private final int V;
    private ArrayList<Integer>[] adj;

    public Graph(int V) {
        this.V = V;
        adj = new  ArrayList[V];
        for(int i=0; i < V; i++) {
            adj[i] = new ArrayList<Integer>();
        }
    }
}

Это было прекрасно объяснено здесь: Нажмите здесь