一. 实验要求
实现利用邻接矩阵构造无向图的算法，在此基础上进行深度优先遍历和广度优先遍历。
二. 实验目的
通过该实验，使学生掌握图的几种存储结构，理解图的深度优先和广度优先遍历算法的思想和实现办法
三、设计思想
1.创建网图。网图是利用邻接矩阵来存储的。先从键盘输入图的顶点树vex和边数arc。创建一个正方形矩阵，边数等于vex。然后输入这vex个顶点的符号。再输入图中i个顶点和j个顶点相连，使矩阵中的第i行第j列和第j行第i列的值为1，表示两个顶点i和j相通，矩阵中其他元素的值为0，表示这两个顶点之间无线。
2.输出邻接矩阵。根据创建网图中创建的邻接矩阵，利用for循环来控制输出邻接矩阵即可。
3.深度优先遍历。从第一个顶点1开始遍历。先输出1。借用辅助数组vis，以便判断顶点是否已经遍历过，已被遍历过的元素为true，没有遍历过的为false。利用for循环，如果矩阵中第vex行的第i个是0或是已被调用过的顶点，则continue一次for循环；否则，继续深度遍历这个未被调用过的第i个顶点。
4.广度优先遍历。构建一个置空的辅助队列que，借助辅助数组vis，以便判断顶点是否已经遍历过。将第一个顶点vex入队，vis[vex]=true。当队列que不为空时，进行while循环：将队列que的队头元素输出，并利用for循环寻找邻接矩阵中第vex行是否有未被访问过的顶点，如果有，则入队，并且辅助数组vis中的值改为true。

三. 主要源代码

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define N 100
using namespace std;bool vis[N];
struct Graph{int vex[N];int graph[N][N];int sum_vex, sum_arc;
};
void print();
void init(Graph &g) {for (int i = 1; i <= g.sum_vex; ++i) {for (int j = 1; j <= g.sum_vex; ++j) {g.graph[i][j] = 0;}}return;
}
void creat(Graph &g) {cout << "请输入顶点数和边数：";cin >> g.sum_vex >> g.sum_arc;cout << endl;init(g);cout << "请输入" << g.sum_vex << "个顶点：";for (int i = 1; i <= g.sum_vex; ++i) {cin >> g.vex[i];}sort(g.vex + 1, g.vex + g.sum_vex + 1);cout << "请输入" << g.sum_arc << "个边: ";for (int i = 0; i < g.sum_arc; ++i) {int s, e;cin >> s >> e;g.graph[s][e] = g.graph[e][s] = 1;}return;
}
void print_graph(Graph g) {for (int i = 1; i <= g.sum_vex; ++i) {for (int j = 1; j <= g.sum_vex; ++j) {cout << g.graph[i][j] << " ";}cout << endl;}}
void DFS(Graph g, int vex) {cout << vex << " ";vis[vex] = true;for (int i = 1; i <= g.sum_vex; ++i) {if (g.graph[vex][g.vex[i]] == 0 ||  vis[g.vex[i]] == true)	continue;DFS(g, g.vex[i]);}
}struct Node{int data;Node *next;
};
struct Queue{Node *front, *rear;
};
void Init(Queue &Q) {Q.front = Q.rear = (Node*)malloc(sizeof(Node));Q.front->next = NULL;Q.front->data = 0;
}
int Empty(Queue Q) {if (Q.front == Q.rear)	return true;return false;
}
int Top(Queue Q, int &e) {if (Empty(Q))	return -1;e = Q.front->next->data;return 1;
}
void Push(Queue &Q, int e) {Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = NULL;Q.rear->next = p;Q.rear = p;Q.front->data++;
}
int Pop(Queue &Q, int &e) {if (Empty(Q))	return -1;Node *p;p = Q.front->next;e = p->data;Q.front->next = p->next;if (p == Q.rear)	Q.rear = Q.front;free(p);Q.front->data--;return 1;
}void BFS(Graph g, int vex) {for (int i = 1; i <= g.sum_vex; ++i)vis[g.vex[i]] = false;Queue que;Init(que);Push(que, vex);vis[vex] = true;while (!Empty(que)) {int top;Pop(que, top);cout << top << " ";for (int i = 1; i <= g.sum_vex; ++i) {if (vis[g.vex[i]] || g.graph[top][g.vex[i]] == 0)	continue;vis[g.vex[i]] = true;Push(que, g.vex[i]);}}
}
int main() {print();Graph g;int t;while (cin >> t) {if (t == 5)	break;switch (t) {case 1:	// 创建creat(g);break;case 2: // 输出print_graph(g);break;case 3: // 深度for (int i = 1; i <= g.sum_vex; ++i)vis[g.vex[i]] = false;DFS(g, g.vex[1]);break;case 4: // 广度BFS(g, g.vex[1]);break;default:printf("输入序号错误! ");break;}printf("\n请输入操作代码：");}return 0;
}void print() {cout << "**************************************************************\n";cout << "******************  1.创建网图              ******************\n";cout << "******************  2.输出邻接矩阵          ******************\n";cout << "******************  3.深度优先遍历          ******************\n";cout << "******************  4.广度优先遍历          ******************\n";cout << "******************  5.退出                  ******************\n";cout << "请输入你的选择：";
} 

五. 调试与测试数据