SHARE
TWEET

Untitled

a guest Apr 19th, 2019 93 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Time limit: 5000ms
  2. Memory limit: 256mb
  3.  
  4. Description:
  5. There is an undirected connected graph. You need to store all edges in adjacency list and traverse the graph in a DFS manner. Suppose there are 100 nodes (node id in 0-99) at most.
  6.  
  7. In this exercise, you are required to fulfill the following two tasks.
  8.  
  9. 1. Construct an adjacency list.
  10. Initially, the adjacency list is empty. Then given a sequence of distinct edges (a,b), you need to insert them into the adjacency list one by one. Note that for every edge (a,b), you need to insert both (a,b) and (b,a). The nodes in each adjacency list must be stored in ascending order.  Lecture notes show more details.
  11.  
  12. 2. Output nodes in DFS manner.
  13. We have defined the oder of edges in task 1, so we have a unique result of DFS. We always start from node 0 to traverse the graph.
  14.  
  15. The main function has been provided. It first asks the user to input the total number of edges m, and input all these edges to construct the adjacency list. Then it invokes the recursive function dfs to output the node sequence.
  16.  
  17. You need to complete two functions.
  18.  
  19. void insert(int v1, int v2);
  20.  
  21. void dfs(int v);
  22.  
  23.  
  24.  
  25. Sample Input 1:   //the graph is empty, no edge,  no node.
  26. 0
  27.  
  28. Sample Output 1:
  29. Input the number of edges:
  30. Input these edges:
  31.  
  32. Sample Input 2:
  33. 10
  34. 0 1
  35. 0 2
  36. 1 3
  37. 1 4
  38. 3 7
  39. 4 7
  40. 2 5
  41. 2 6
  42. 5 7
  43. 6 7
  44.  
  45. Sample Output 2:
  46. Input the number of edges:
  47. Input these edges:
  48. 0 1 3 7 4 5 2 6
  49.  
  50.  
  51. Code Template:
  52.  
  53. #include <stdio.h>
  54. #include <stdlib.h>
  55.  
  56. #define MAX_NODES 100
  57.  
  58. typedef struct _adjlist {
  59.      int node;
  60.      struct _adjlist *link;
  61. } adjlist;
  62.  
  63. adjlist graph[MAX_NODES];
  64.  
  65. int visited[MAX_NODES];    // 0:unvisited    1:visited
  66.  
  67. void insert(int v1, int v2);
  68.  
  69. void dfs(int v);
  70.  
  71.  
  72.  
  73. void insert(int v1, int v2)
  74. {
  75.     /*
  76.                 insert edge (v1,v2) into adajacency list in ascending order.
  77.         Fill in your code here...
  78.     */
  79. }
  80.  
  81. void dfs(int v)
  82. {
  83.     /*
  84.         Fill in your code here...
  85.         visit v and traverse all its edges recursively.
  86.     */
  87. }
  88.  
  89. int main()
  90. {
  91.     int m,a,b;
  92.    
  93.     // initialize
  94.     for(int i=0;i<MAX_NODES;i++)
  95.     {
  96.                 graph[i].link=NULL;
  97.                 visited[i]=0;  // unvisited
  98.     }
  99.  
  100.  
  101.     printf("Input the number of edges:\n");
  102.     scanf("%d",&m);
  103.     printf("Input these edges:\n");
  104.     for(int i=0; i<m; i++)
  105.     {
  106.         scanf("%d %d", &a, &b);
  107.         insert(a,b);
  108.           insert(b,a);
  109.     }
  110.     dfs(0);
  111.     return 0;
  112. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top