6. (15pt) Recall that we used the following structures to represent a graph usin

Question

6. (15pt) Recall that we used the following structures to represent a graph using adjacency list. tide fine MAXV 6 typedef struct edgenode int y; int w; struct edgenode next 6 l edgenodeT; typedef struct f edgenodeT *edges [MAXV+1] int degree [MAXV+1]; int nvertices int nedges; bool directed; graphT; graphT gi nvertices 6 nedges8 directed One of the disadvantages of the above representation is that the maximum number of nodes is fixed to MAXV. So we waste some spaces when we don't have that many nodes or we cannot use this program if we have more nodes than MAXV. Accordingly, we want to remove fixed size array and use a link list to dynamically store nodes, their IDs, degrees etc. So we need to modify graphT and define a new cell structure to store nodes in a linked list. We like to keep edgenodeT as is. Now you are asked to first give the new form of graphT and nodeT structures such that we can conceptually represent the above same graph as follows 9 1 2 2 3 vertex nvertices 6 nedges 8 directed 0 4 3 5 3 6| 2 |NULL 10

Explanation / Answer

typedef struct edgenode
{
  
    int y;
    int w;
    struct edgenode* next;
};

typedef struct
{
      struct AdjList* array;
    int * degree;
    int nVertices;
    int nedges
    bool directed;
}graphT;
graphT *g;

print_closest_neighbor(graphT * g)
{
int t, v = 0;
   
    for (t = 0; t < g->nvertices; t++) {
        int e = nearest_neighbour(edgenodeT, g->nedges t, v);
        printf("Vertex: %d ",e);
    }
}

int nearest_neighbour(const edgenodeT *edges, int size, int t, int v)
{
     int min_distance = 0;
     int nearest_neighbour;
     int i;
    for (i = 0; i < size; i++) {
        if ((edges[i].y == v) && (min_distance == 0 || edges[i].w < min_distance))              
        {
            min_distance = edges[i].w;
            nearest_neighbour = i;
        }
    }
    return nearest_neighbour;
}

7.

#define INFINITY 9999
#define MAX 10

void dijkstra(int G[MAX][MAX],int n,int startnode)
{

    int Wait[MAX][MAX],distance[MAX],Supp[MAX];
    int visited[MAX],count,mindistance,nextnode,i,j;
   

    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            if(G[i][j]==0)
                Wait[i][j]=INFINITY;
            else
                Wait[i][j]=G[i][j];
   
   
    for(i=0;i<n;i++)
    {
        distance[i]=Wait[startnode][i];
        Supp[i]=startnode;
        visited[i]=0;
    }
   
    distance[startnode]=0;
    visited[startnode]=1;
    count=1;
   
    while(count<n-1)
    {
        mindistance=INFINITY;
       
        //nextnode gives the node at minimum distance
        for(i=0;i<n;i++)
            if(distance[i]<mindistance&&!visited[i])
            {
                mindistance=distance[i];
                nextnode=i;
            }
           
            //check if a better path exists through nextnode           
            visited[nextnode]=1;
            for(i=0;i<n;i++)
                if(!visited[i])
                    if(mindistance+cost[nextnode][i]<distance[i])
                    {
                        distance[i]=mindistance+cost[nextnode][i];
                        Supp[i]=nextnode;
                    }
        count++;
    }

    //print the path and distance of each node
    for(i=0;i<n;i++)
        if(i!=startnode)
        {
            printf(" Distance of node%d=%d",i,distance[i]);
            printf(" Path=%d",i);
           
            j=i;
            do
            {
                j=Supp[j];
                printf("<-%d",j);
            }while(j!=startnode);
    }
}

Related Questions

Navigate

• Browse (All)
• Browse 6
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.