6-1 jmu-ds-邻接矩阵实现图的操作集 ( 30分) 

1. 关键代码

 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         else
32         {
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 <queue>
47 void BFS(MGraph g, int v)
48 {
49     int t;
50     queue<int>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. 关键代码

 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     else
36     {
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<int>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.运行截图