Difficulties during the exam, ask for help! !! !! !! !!

yeteng6988

The tour of the graph in the data structure can be stored using an adjacency matrix or an adjacency table. You can use breadth-first and depth-first algorithms when traveling around. Thank you all for my urgent need.

zjwzjw

// ========================================
// The breadth of the graph is traversed first
// ========================================
#include <stdlib.h>
#define MAXQUEUE 10 // The maximum capacity of the storage node queue during the traversal process
#define MAX 9
struct node // graph vertex structure
{
   int vertex; // vertex information
   struct node * nextnode; // refers to the next vertex
};
typedef struct node * graph; // Structure declaration of graph
struct node head [9]; // array of graph vertex structures
int visited [9]; // traverse the record array

int queue [MAXQUEUE]; // Array of queues
int front = -1; // front of the queue
int rear = -1; // The back of the queue

// ----------------------------------------
// Create graphics
// ----------------------------------------
void creategraph (int * node, int num)
{
   graph newnode; // new vertex
   graph ptr;
   int from; // The starting point of the edge
   int to; // end of the line
   int i;

   for (i = 0; i <num; i ++) // read the loop of the edge
   {
      from = node [i * 2]; // starting point of the edge
      to = node [i * 2 + 1]; // end point of the edge
      
      newnode = (graph) malloc (sizeof (struct node));
      newnode-> vertex = to; // build vertex content
      newnode-> nextnode = NULL; // Set the initial value of the indicator
      ptr =&(head [from]); // vertex position
      while (ptr-> nextnode! = NULL) // Traverse to the end of the list
         ptr = ptr-> nextnode; // Next vertex
      ptr-> nextnode = newnode; // Insert end
   }
}


// Deposit of the queue

int enqueue (int value)
{
   if (rear> = MAXQUEUE) // Check if the queue is full
      return -1; // unable to deposit
   rear ++; // Back-end indicators move forward
   queue [rear] = value; // store in queue
   return;
}


// Extraction of the queue data

int dequeue ()
{
   if (front == rear) // Check if the queue is empty
      return -1; // Cannot take out
         front ++; // Front-end indicators move forward
   return queue [front]; // Take out the queue
}


// The breadth-first search method of graphics

void bfs (int current)
{
   graph ptr;

   // handle the first vertex
   enqueue (current); // Store the vertex in the queue
   visited [current] = 1; // Record has been traversed
   printf ("Head [% d]", current); // Print out the traversal vertex value
   while (front! = rear) // Whether the queue is empty
   {
      current = dequeue (); // Remove the vertex from the queue
      ptr = head [current] .nextnode; // Vertex position
      while (ptr! = NULL) // traverse to the end of the list
      {
         if (visited [ptr-> vertex] == 0) // If it has not been traversed, traverse and enter the team
         {
            enqueue (ptr-> vertex);
            visited [ptr-> vertex] = 1; // Record has been traversed
            
            printf ("Head [% d]", ptr-> vertex);
         }
         ptr = ptr-> nextnode; // Next vertex
      }
   }
}


void main ()
{
   graph ptr;
   int node [20] [2] = {{1, 2}, {2, 1}, // Declaration of undirected graph
                       {1, 3}, {3, 1},
                       {2, 4}, {4, 2},
                       {2, 5}, {5, 2},
                       {3, 6}, {6, 3},
                       {3, 7}, {7, 3},
                       {4, 8}, {8, 4},
                       {5, 8}, {8, 5},
                       {6, 8}, {8, 6},
                       {7, 8}, {8, 7}};
   int i;

   for (i = 1; i <= 8; i ++)
   {
      head [i] .vertex = i; // set the vertex value
      head [i] .nextnode = NULL; // clear graph node
      visited [i] = 0; // Set the initial value of traversal
   }
   creategraph (node, 20); // Create graph
   printf ("Graph Adjacency List:\n"); // The content of the graph's adjacent list
   for (i = 1; i <= MAX-1; i ++)
   {
      printf ("Head (% d)->", head [i] .vertex); // vertex value
      ptr = head [i] .nextnode; // vertex position
      while (ptr! = NULL) // Traverse to the end of the list
      {
         printf ("% d", ptr-> vertex); // print out the vertex content
         ptr = ptr-> nextnode; // next vertex
      }
      printf ("\n");
   }
   printf ("Bfs Graph Treaver:\n"); // The width of the graph traverses the content first
   bfs (1); // traverse from the stored first vertex breadth and print out the traversal process
   printf ("\n");
}

zjwzjw

/ * ======================================== * /
/ * Traversal of graphics * /
/ * ======================================== * /
#include <stdlib.h>
#define MAXQUEUE 70 / * The maximum capacity of the queue * /

struct node / * graphics vertex structure declaration * /
{
   int vertex; / * Vertex data * /
   struct node * nextnode; / * refers to the index of the next vertex * /
};
typedef struct node * graph; / * New structure of graph structure * /
struct node head [61]; / * graph vertex structure array * /
int visited [61]; / * Traverse the record array * /

int queue [MAXQUEUE]; / * Array declaration of queue * /
int front = -1; / * front of queue * /
int rear = -1; / * rear end of the queue * /

/ * ---------------------------------------- * /
/ * Create graphics * /
/ * ---------------------------------------- * /
void creategraph (int * node, int num)
{
   graph newnode; / * New vertex indicator * /
   graph ptr;
   int from; / * starting point of the edge * /
   int to; / * end of the line * /
   int i;

   for (i = 0; i <num; i ++) / * read the edge circuit * /
   {
      from = node [i * 2]; / * starting point of the edge * /
      to = node [i * 2 + 1]; / * the end of the line * /
      / * Create new vertex memory * /
      newnode = (graph) malloc (sizeof (struct node));
      newnode-> vertex = to; / * Create vertex content * /
      newnode-> nextnode = NULL; / * set the initial value of the indicator * /
      ptr =&(head [from]); / * vertex position * /
      while (ptr-> nextnode! = NULL) / * Traverse to the end of the list * /
         ptr = ptr-> nextnode; / * next vertex * /
      ptr-> nextnode = newnode; / * Insert end * /
   }
}

/ * ---------------------------------------- * /
/ * Queue data storage * /
/ * ---------------------------------------- * /
int enqueue (int value)
{
   if (rear> = MAXQUEUE) / * Check if the queue is full * /
      return -1; / * unable to deposit * /
   rear ++; / * Back-end indicators move forward * /
   queue [rear] = value; / * Deposit into queue * /
}

/ * ---------------------------------------- * /
/ * Extraction of queue data * /
/ * ---------------------------------------- * /
int dequeue ()
{
   if (front == rear) / * Check if the queue is empty * /
      return -1; / * unable to take out * /
   front ++; / * The front-end indicator moves forward * /
   return queue [front]; / * Queue out * /
}

/ * ---------------------------------------- * /
/ * The breadth-first search method of graphics * /
/ * ---------------------------------------- * /
void bfs (int current)
{
   graph ptr;

   / * Process the first vertex * /
   enqueue (current); / * Store vertex in queue * /
   visited [current] = 1; / * The record has been traversed * /
   printf ("[% d]", current); / * print out the traversal vertex value * /
   while (front! = rear) / * Whether the queue is empty * /
   {
      current = dequeue (); / * take the vertex from the queue * /
      ptr = head [current] .nextnode; / * vertex position * /
      while (ptr! = NULL) / * Traverse to the end of the list * /
      {
         if (visited [ptr-> vertex] == 0) / * If it has never been traversed * /
         {
            enqueue (ptr-> vertex); / * recursive traversal call * /
            visited [ptr-> vertex] = 1; / * The record has been traversed * /
            / * Print out the traversal vertex value * /
     printf ("[% d]", ptr-> vertex);
         }
         ptr = ptr-> nextnode; / * next vertex * /
      }
   }
}

zjwzjw

/ * ======================================== * /
/ * Traversal of graphics * /
/ * ======================================== * /
#include <stdlib.h>
#define MAXQUEUE 70 / * The maximum capacity of the queue * /

struct node / * graphics vertex structure declaration * /
{
   int vertex; / * Vertex data * /
   struct node * nextnode; / * refers to the index of the next vertex * /
};
typedef struct node * graph; / * New structure of graph structure * /
struct node head [61]; / * graph vertex structure array * /
int visited [61]; / * Traverse the record array * /

int queue [MAXQUEUE]; / * Array declaration of queue * /
int front = -1; / * front of queue * /
int rear = -1; / * rear end of the queue * /

/ * ---------------------------------------- * /
/ * Create graphics * /
/ * ---------------------------------------- * /
void creategraph (int * node, int num)
{
   graph newnode; / * New vertex indicator * /
   graph ptr;
   int from; / * starting point of the edge * /
   int to; / * end of the line * /
   int i;

   for (i = 0; i <num; i ++) / * read the edge circuit * /
   {
      from = node [i * 2]; / * starting point of the edge * /
      to = node [i * 2 + 1]; / * the end of the line * /
      / * Create new vertex memory * /
      newnode = (graph) malloc (sizeof (struct node));
      newnode-> vertex = to; / * Create vertex content * /
      newnode-> nextnode = NULL; / * set the initial value of the indicator * /
      ptr =&(head [from]); / * vertex position * /
      while (ptr-> nextnode! = NULL) / * Traverse to the end of the list * /
         ptr = ptr-> nextnode; / * next vertex * /
      ptr-> nextnode = newnode; / * Insert end * /
   }
}

/ * ---------------------------------------- * /
/ * Queue data storage * /
/ * ---------------------------------------- * /
int enqueue (int value)
{
   if (rear> = MAXQUEUE) / * Check if the queue is full * /
      return -1; / * unable to deposit * /
   rear ++; / * Back-end indicators move forward * /
   queue [rear] = value; / * Deposit into queue * /
}

/ * ---------------------------------------- * /
/ * Extraction of queue data * /
/ * ---------------------------------------- * /
int dequeue ()
{
   if (front == rear) / * Check if the queue is empty * /
      return -1; / * unable to take out * /
   front ++; / * The front-end indicator moves forward * /
   return queue [front]; / * Queue out * /
}

/ * ---------------------------------------- * /
/ * The breadth-first search method of graphics * /
/ * ---------------------------------------- * /
void bfs (int current)
{
   graph ptr;

   / * Process the first vertex * /
   enqueue (current); / * Store vertex in queue * /
   visited [current] = 1; / * The record has been traversed * /
   printf ("[% d]", current); / * print out the traversal vertex value * /
   while (front! = rear) / * Whether the queue is empty * /
   {
      current = dequeue (); / * take the vertex from the queue * /
      ptr = head [current] .nextnode; / * vertex position * /
      while (ptr! = NULL) / * Traverse to the end of the list * /
      {
         if (visited [ptr-> vertex] == 0) / * If it has never been traversed * /
         {
            enqueue (ptr-> vertex); / * recursive traversal call * /
            visited [ptr-> vertex] = 1; / * The record has been traversed * /
            / * Print out the traversal vertex value * /
     printf ("[% d]", ptr-> vertex);
         }
         ptr = ptr-> nextnode; / * next vertex * /
      }
   }
}

/ * ---------------------------------------- * /
/ * Depth-first search method for graphics * /
/ * ---------------------------------------- * /
void dfs (int current)
{
   graph ptr;

   visited [current] = 1; / * The record has been traversed * /
   printf ("[% d]", current); / * print out the traversal vertex value * /
   ptr = head [current] .nextnode; / * vertex position * /
   while (ptr! = NULL) / * Traverse to the end of the list * /
   {
      if (visited [ptr-> vertex] == 0) / * If it has not been traversed before * /
         dfs (ptr-> vertex); / * recursive traversal call * /
      ptr = ptr-> nextnode; / * next vertex * /
   }
}

zjwzjw

/ * ---------------------------------------- * /
/ * Main program: After creating the graphics, print the traversal content. * /
/ * ---------------------------------------- * /
void main ()
{clrscr ();

while (1)
{
   char c, a;
   graph ptr;
   int i;
   int node [60] [2] = {{1, 10}, {10, 1}, / * edge array * /
         {2, 10}, {10, 2},
         {2, 3}, {3, 2},
         {3, 4}, {4, 3},
         {3, 12}, {12, 3},
         {4, 13}, {13, 4},
         {4, 5}, {5, 4},
         {5, 6}, {6, 5},
         {5, 7}, {7, 5},
         {7, 8}, {8, 7},
         {9, 10}, {10, 9},
         {10, 11}, {11, 10},
         {11, 14}, {14, 11},
         {11, 12}, {12, 11},
         {12, 15}, {15, 12},
         {12, 13}, {13, 12},
         {13, 16}, {16, 13},
         {14, 17}, {17, 14},
         {14, 18}, {18, 14},
         {15, 19}, {19, 15},
         {16, 20}, {20, 16},
         {17, 18}, {18, 17},
         {18, 23}, {23, 18},
         {18, 19}, {19, 18},
         {19, 23}, {23, 19},
         {19, 24}, {24, 19},
         {19, 20}, {20, 19},
         {20, 21}, {21, 20},
         {22, 23}, {23, 22},
         {24, 25}, {25,24}
         };
clrscr ();
printf ("\n\n\n");
printf ("/ * --------------------------------------------- --------- * /\n ");
printf ("/ * Welcome to use this program * /\n");
printf ("/ * --------------------------------------------- --------- * /\n ");
printf ("This program is an algorithmic demonstration of the traversal of related graphs,\n");
printf ("If there are any shortcomings, please forgive me!\n\n");
printf ("Please ask if you want to run the following program:\n\n");
printf ("Depth and breadth traversal of the graph? Y / N?\n");
c = getch ();
if (c! = 'y'&&'Y')
exit (0);
 clrscr ();

printf ("\n\n");
printf ("Please note the following code for each city:\n\n");

printf ("1: Urumqi; 2: Hohhot; 3: Beijing; 4: Tianjin; 5: Shenyang;\n");
printf ("6: Dalian; 7: Changchun; 8: Harbin; 9: Xining; 10: Lanzhou;\n");
printf ("11: Xi'an; 12: Zhengzhou; 13: Xuzhou; 14: Chengdu; 15: Wuhan;\n");
printf ("16: Shanghai; 17: Kunming; 18: Guiyang; 19: Zhuzhou; 20: Nanchang;\n");
printf ("21: Fuzhou; 22: Nanning; 23: Liuzhou; 24: Guangzhou; 25: Shenzhen.\n");

   for (i = 1; i <= 25; i ++)
   {
      head [i] .vertex = i; / * set the vertex value * /
      head [i] .nextnode = NULL; / * clear graph indicator * /
      visited [i] = 0; / * set the initial value of traversal * /
   }
   creategraph (node, 60); / * Create graph * /
   printf ("The content of the adjacency list of the graph:\n");
   for (i = 1; i <= 25; i ++)
   {if (i% 3 == 0) printf ("\n");
      printf ("Vertex% d =>", head [i] .vertex); / * Vertex value * /
      ptr = head [i] .nextnode; / * vertex position * /
      while (ptr! = NULL) / * Traverse to the end of the list * /
      {
  printf ("% d", ptr-> vertex); / * print out vertex content * /
  ptr = ptr-> nextnode; / * next vertex * /
      }
   }
printf ("\n\n");
printf ("Please select the operation you need\n");
printf ("1, the breadth of the graph is traversed first, please enter: 'g' or 'G'\n");
printf ("2. Depth-first traversal of graphics, please enter: 's' or' S'\n");
 c = getch ();
  switch (c)
{
  case'g ': case'G':
   printf ("\n please input the starting point you need:\n");
   scanf ("% d",&i);
   clrscr ();
   printf ("\n\n");
   printf ("Please note the following code for each city:\n\n");
   printf ("1: Urumqi; 2: Hohhot; 3: Beijing; 4: Tianjin; 5: Shenyang;\n");
   printf ("6: Dalian; 7: Changchun; 8: Harbin; 9: Xining; 10: Lanzhou;\n");
   printf ("11: Xi'an; 12: Zhengzhou; 13: Xuzhou; 14: Chengdu; 15: Wuhan;\n");
   printf ("16: Shanghai; 17: Kunming; 18: Guiyang; 19: Zhuzhou; 20: Nanchang;\n");
   printf ("21: Fuzhou; 22: Nanning; 23: Liuzhou; 24: Guangzhou; 25: Shenzhen.\n");

   printf ("The breadth of the graph is preferably traversed at the top point of the content:\n");
   bfs (i); / * Print out the traversal process * /
   printf ("\n"); / * newline * /
   break;
 case's ': case'S':
    printf ("\n, please enter the starting point you need:\n");
    scanf ("% d",&i);
    clrscr ();
   printf ("\n\n");
    printf ("Please note the following code for each city:\n\n");
    printf ("1: Urumqi; 2: Hohhot; 3: Beijing; 4: Tianjin; 5: Shenyang;\n");
    printf ("6: Dalian; 7: Changchun; 8: Harbin; 9: Xining; 10: Lanzhou;\n");
    printf ("11: Xi'an; 12: Zhengzhou; 13: Xuzhou; 14: Chengdu; 15: Wuhan;\n");
    printf ("16: Shanghai; 17: Kunming; 18: Guiyang; 19: Zhuzhou; 20: Nanchang;\n");
    printf ("21: Fuzhou; 22: Nanning; 23: Liuzhou; 24: Guangzhou; 25: Shenzhen.\n");

    printf ("The depth of the graph is traversed first, the top point content:\n");
    dfs (i); / * Print out the traversal process * /
    printf ("\n"); / * newline * /
     break;
}
printf ("\n please ask if you want to continue: y / n");
a = getch ();
if (a! = 'y'&&'Y')
exit (0);
}
}

zjwzjw

The above procedure is for reference only ～～

squall_wl

So long

wenbinjiao

zjwzjwworked hard!

yeteng6988

After working hard, is there a simpler one with depth priority alone? It is best represented by an adjacency matrix.