6-1 jmu-ds-邻接矩阵实现图的操作集 ( 30分)
- 关键代码
1 void CreateMGraph(MGraph& g, int n, int e) 2 { 3 int i, j; 4 g.n = n; 5 g.e = e; 6 for (i = 1;i < MAXV;i++) 7 { 8 for (j =1;j < MAXV;j++) 9 {10 g.edges[i][j] = 0;11 }12 }13 int a, b;14 for (i = 0;i < e;i++)15 {16 cin >> a >> b;17 g.edges[a][b] = 1;18 g.edges[b][a] = 1;19 }20 }21 void DFS(MGraph g, int v)22 {23 static int n = 0;24 if (visited[v] == 0)25 {26 if (n == 0)27 {28 cout << v;29 n++;30 }31 else32 {33 cout << " " << v;34 n++;35 }36 visited[v] = 1;37 }38 for (int j = 1;j <= g.n;j++)39 {40 if (g.edges[v][j] && visited[j] == 0)41 {42 DFS(g, j);43 }44 }45 }46 #include 47 void BFS(MGraph g, int v)48 {49 int t;50 queue q;51 if (visited[v] == 0)52 {53 cout << v;54 visited[v] = 1;55 q.push(v);56 }57 while (!q.empty())58 {59 t = q.front();60 q.pop();61 for (int j = 1;j <= g.n;j++)62 {63 if (g.edges[t][j] == 1 && visited[j] == 0)64 {65 cout << " " << j;66 visited[j] = 1;67 q.push(j);68 }69 }70 }71 }
2.运行截图
6-2 jmu-ds-图邻接表操作 (20 分)
- 关键代码
1 void CreateAdj(AdjGraph*& G, int n, int e) 2 { 3 int i; 4 G = new AdjGraph; 5 G->e = e; 6 G->n = n; 7 for (i = 1;i <= n;i++) { 8 G->adjlist[i].firstarc = NULL; 9 }10 for (i = 1;i <= e;i++)11 {12 int a, b;13 cin >> a >> b;14 ArcNode* p, * q;15 p = new ArcNode;16 q = new ArcNode;17 p->adjvex = b;18 q->adjvex = a;19 p->nextarc = G->adjlist[a].firstarc;20 G->adjlist[a].firstarc= p;21 q->nextarc = G->adjlist[b].firstarc;22 G->adjlist[b].firstarc= q;23 }24 }25 void DFS(AdjGraph* G, int v)26 {27 static int n = 0;28 ArcNode* p;29 visited[v] = 1;30 if (!n) 31 {32 cout << v;33 n++;34 }35 else36 {37 cout << " " << v;38 n++;39 }40 p = G->adjlist[v].firstarc;41 while (p != NULL)42 {43 if (visited[p->adjvex] == 0)44 DFS(G, p->adjvex);45 p = p->nextarc;46 }47 48 }49 void BFS(AdjGraph* G, int v)50 {51 int w, i;ArcNode* p;52 queue q;53 cout << v;54 visited[v] = 1;55 q.push(v);56 while (!q.empty())57 {58 w = q.front();59 q.pop();60 p = G->adjlist[w].firstarc;61 while (p != NULL)62 {63 if (visited[p->adjvex] == 0)64 {65 cout << " " << p->adjvex;66 visited[p->adjvex] = 1;67 q.push(p->adjvex);68 }69 p = p->nextarc;70 }71 }72 73 }
2.运行截图
