实验（训）项目名称

图的应用

实验（训）地点

明远楼C110

实验（训）日期

2026.6.2

小组成员

无

小组成员

分工情况

个人

实验（训）所用设备、材料、软件等：

Win10操作系统计算机

VC++ 2010学习版软件

实验（训）目的：

掌握图的邻接矩阵和邻接表的存储结构；掌握深度优先遍历、广度优先遍历的基本思想及对图的遍历操作；了解图在人工智能、工程等领域的应用。

实验（训）内容、步骤、结果、心得体会：

一、实验内容

1.输入一组顶点，建立无向图的邻接矩阵。

2.输入一组顶点，建立有向图的邻接表。

3.以邻接矩阵为存储结构，对无向图分别进行DFS（深度优先遍历）和BFS（广度优先遍历）。

二、实验步骤

1.无向图邻接矩阵：

代码：

#include <iostream>

using namespace std;

const int N = 50;

int main() {

    int n, e;

    int a[N][N] = {0};

    cout << "请输入顶点数: ";

    cin >> n;

    cout << "请输入边数: ";

    cin >> e;

    cout << "请输入" << e << "条边:\n";

    for (int i = 0; i < e; i++) {

        int u, v;

        cin >> u >> v;

        a[u][v] = 1;

        a[v][u] = 1;//对称

    }

    cout << "\n邻接矩阵:\n";

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < n; j++) {

            cout << a[i][j] << " ";

        }

        cout << endl;

    }

    return 0;

}

运行结果：

2.有向图连接表

代码：

#include <iostream>

using namespace std;

const int N = 50;

// 边节点

struct Node {

  int v;

  Node *next;

};

// 顶点

struct Vex {

  char name;

  Node *first;

};

int main() {

  int n, e;

  Vex g[N]; // 顶点表

  cout << "请输入顶点数: ";

  cin >> n;

  cout << "请输入" << n << "个顶点名字:\n";

  for (int i = 0; i < n; i++) {

    cin >> g[i].name;

    g[i].first = NULL;

  }

  cout << "请输入边数: ";

  cin >> e;

  cout << "请输入" << e << "条有向边:\n";

  for (int i = 0; i < e; i++) {

    int u, v;

    cin >> u >> v;

    Node *p = new Node;

    p->v = v;

    p->next = g[u].first;

    g[u].first = p;

  }

  cout << "\n邻接表:\n";

  for (int i = 0; i < n; i++) {

    cout << g[i].name << ": ";

    Node *p = g[i].first;

    while (p != NULL) {

      cout << "->" << g[p->v].name;

      p = p->next;

    }

    cout << "->NULL" << endl;

  }

  // 释放内存

  for (int i = 0; i < n; i++) {

    Node *p = g[i].first;

    while (p != NULL) {

      Node *t = p;

      p = p->next;

      delete t;

    }

  }

  return 0;

}

结果：

3.DFS和BFS遍历：

代码：

#include <iostream>

using namespace std;

const int N = 50;

int a[N][N];

int vis[N];

int n, e;

void dfs(int v) {

  cout << v << " ";

  vis[v] = 1;

  for (int w = 0; w < n; w++) {

    if (a[v][w] == 1 && vis[w] == 0) {

      dfs(w);

    }

  }

}

void bfs(int start) {

  int q[N];

  int f = 0, r = 0;

  q[r++] = start;

  vis[start] = 1;

  while (f != r) {

    int v = q[f++];

    cout << v << " ";

    for (int w = 0; w < n; w++) {

      if (a[v][w] == 1 && vis[w] == 0) {

        q[r++] = w;

        vis[w] = 1;

      }

    }

  }

}

int main() {

  cout << "请输入顶点数: ";

  cin >> n;

  cout << "请输入边数: ";

  cin >> e;

  // 初始化

  for (int i = 0; i < n; i++)

    for (int j = 0; j < n; j++)

      a[i][j] = 0;

  cout << "请输入" << e << "条无向边:\n";

  for (int i = 0; i < e; i++) {

    int u, v;

    cin >> u >> v;

    a[u][v] = 1;

    a[v][u] = 1;

  }

  // DFS

  cout << "\nDFS结果: ";

  for (int i = 0; i < n; i++)

    vis[i] = 0;

  for (int i = 0; i < n; i++) {

    if (vis[i] == 0)

      dfs(i); // 处理非连通图

  }

  // BFS

  cout << "\nBFS结果: ";

  for (int i = 0; i < n; i++)

    vis[i] = 0;

  for (int i = 0; i < n; i++) {

    if (vis[i] == 0)

      bfs(i);

  }

  cout << endl;

  return 0;

}

结果：

教师评语：

成绩评定

教师签名