[Case Study]Depth-First-Search using C

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

DFS(Depth-First-Search)深度优先搜索算法是图的遍历算法中非常常见的一类算法。分享给大家供大家参考。具体方法如下：

1. #include <iostream>
   
2. #include <algorithm>
   
3. #include <iterator>
   
4. 
   
5. using namespace std;  
   
6. 
   
7. #define MAX_VERTEX_NUM 10
   
8. 
   
9. struct Node
   
10. {
    
11. int adjvex;
    
12. struct Node *next;
    
13. int info;
    
14. };
    
15. 
    
16. typedef struct VNode
    
17. {
    
18. char data;
    
19. Node *first;
    
20. }VNode, AdjList[MAX_VERTEX_NUM];
    
21. 
    
22. struct Graph
    
23. {
    
24. AdjList vertices;
    
25. int vexnum, arcnum;
    
26. };
    
27. 
    
28. int visited[MAX_VERTEX_NUM];
    
29. 
    
30. int locateVex(Graph G, char u)
    
31. {
    
32. int i;
    
33. for (i = 0; i < G.vexnum; i++)
    
34. {
    
35. if (u == G.vertices[i].data)
    
36.   return i;
    
37. }
    
38. 
    
39. if (i == G.vexnum)
    
40. {
    
41. printf("Error u!\n");
    
42. exit(1);
    
43. }
    
44. 
    
45. return 0;
    
46. }
    
47. 
    
48. void createGraph(Graph &G)
    
49. {
    
50. int i, j, k, w;
    
51. char v1, v2, enter;
    
52. 
    
53. Node *p;
    
54. printf("input vexnum & arcnum:\n");
    
55. scanf("%d", &G.vexnum);
    
56. scanf("%d", &G.arcnum);
    
57. printf("input vertices:\n");
    
58. for (i = 0; i < G.vexnum; i++)
    
59. {
    
60. scanf("%c%c", &enter, &G.vertices[i].data);
    
61. G.vertices[i].first = NULL;
    
62. }
    
63. 
    
64. printf("input Arcs(v1, v2, w):\n");
    
65. for (k = 0; k < G.arcnum; k++)
    
66. {
    
67. scanf("%c%c", &enter, &v1);
    
68. scanf("%c%c", &enter, &v2);
    
69. scanf("%d", &w);
    
70. i = locateVex(G, v1);
    
71. j = locateVex(G, v2);
    
72. p = (Node *)malloc(sizeof(Node));
    
73. p->adjvex = j;
    
74. p->info = w;
    
75. p->next = G.vertices[i].first;
    
76. G.vertices[i].first = p;
    
77. }
    
78. }
    
79. 
    
80. void DFS(Graph &G, int v)
    
81. {
    
82. Node *p;
    
83. printf("%c", G.vertices[v].data);
    
84. visited[v] = 1;
    
85. p = G.vertices[v].first;
    
86. 
    
87. while (p)
    
88. {
    
89. if (!visited[p->adjvex])
    
90.   DFS(G, p->adjvex);
    
91. p = p->next;
    
92. }
    
93. }
    
94. 
    
95. void DFSTranverse(Graph &G)
    
96. {
    
97. for (int v = 0; v < G.vexnum; v++)
    
98. visited[v] = 0;
    
99. for (int v = 0; v < G.vexnum; v++)
    
100. {
     
101. if (!visited[v])
     
102.   DFS(G, v);
     
103. }
     
104. }
     
105. 
     
106. int main()
     
107. {
     
108. Graph G;
     
109. createGraph(G);
     
110. DFSTranverse(G);
     
111. }

复制代码

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：Case study search Using First study include

1. #include <iostream>
   
2. #include <string>
   
3. 
   
4. using namespace std;
   
5. 
   
6. #define MAXLEN 10
   
7. 
   
8. struct Node
   
9. {
   
10. int data;
    
11. Node *next;
    
12. };
    
13. 
    
14. struct Link
    
15. {
    
16. int count;
    
17. string name;
    
18. Node *head;
    
19. };
    
20. 
    
21. struct Graph
    
22. {
    
23. Link link[MAXLEN];
    
24. int vexnum;
    
25. int arcnum;
    
26. };
    
27. 
    
28. int findIndex(Graph &G, string name)
    
29. {
    
30. int index = -1;
    
31. 
    
32. for (int i = 0; i < G.vexnum; i++)
    
33. {
    
34. if (G.link[i].name == name)
    
35. {
    
36.   index = i;
    
37.   break;
    
38. }
    
39. }
    
40. 
    
41. if (index == -1)
    
42. cout << "error" << endl;
    
43.   
    
44. return index;
    
45. }
    
46. 
    
47. void constructGraph(Graph &G)
    
48. {
    
49. cout << "construct graph yooo" << endl;
    
50. cout << "enter vexnum" << endl;
    
51. cin >> G.vexnum;
    
52. 
    
53. string array[] = {"v1", "v2", "v3", "v4", "v5", "v6", "v7", "v8"};
    
54. const int size = sizeof array / sizeof *array;
    
55. 
    
56. for (int i = 0; i < G.vexnum; i++)
    
57. {
    
58. G.link[i].name = array[i];
    
59. G.link[i].head = NULL;
    
60. }
    
61. 
    
62. string leftName;
    
63. string rightName;
    
64. 
    
65. cout << "enter a pair" << endl;
    
66. cin >> leftName >> rightName;
    
67. while (leftName != "end" && rightName != "end")
    
68. {
    
69. int leftIndex = findIndex(G, leftName);
    
70. int rightIndex = findIndex(G, rightName);
    
71. 
    
72. Node *node = new Node;
    
73. node->data = rightIndex;
    
74. node->next = NULL;
    
75. 
    
76. node->next = G.link[leftIndex].head;
    
77. G.link[leftIndex].head = node;
    
78. 
    
79. cout << "enter a pair" << endl;
    
80. cin >> leftName >> rightName;
    
81. }
    
82. }
    
83. 
    
84. bool flag[MAXLEN];
    
85. 
    
86. void DFSTranverse(Graph &G, int num)
    
87. {
    
88. cout << G.link[num].name << " ";
    
89. flag[num] = true;
    
90. 
    
91. Node *head = G.link[num].head;
    
92. while (head != NULL)
    
93. {
    
94. int index = head->data;
    
95. if (!flag[index])
    
96.   DFSTranverse(G, index);
    
97. head = head->next;
    
98. }
    
99. }
    
100. 
     
101. void main()
     
102. {
     
103. Graph G;
     
104. constructGraph(G);
     
105. for (int i = 0; i < MAXLEN; i++)
     
106. flag[i] = false;
     
107. DFSTranverse(G, 0);
     
108. }

复制代码

1. DFS的迭代遍历算法如下：
   
2. 
   
3. void DFS(Graph &G)
   
4. {
   
5. stack<int> istack;
   
6. istack.push(0);
   
7. 
   
8. cout << G.link[0].name << " ";
   
9. flag[0] = true;
   
10. 
    
11. while (!istack.empty())
    
12. {
    
13. int index = istack.top();
    
14. Node *head = G.link[index].head;
    
15. 
    
16. while (head != NULL && flag[head->data] == true)
    
17.   head = head->next;
    
18. 
    
19. if (head != NULL)
    
20. {
    
21.   index = head->data;
    
22.   if (!flag[index])
    
23.   {
    
24.   cout << G.link[index].name << " ";
    
25.   flag[index] = true;
    
26.   istack.push(index);
    
27.   }
    
28. }
    
29. else
    
30.   istack.pop();
    
31. }
    
32. }

复制代码