图（Graph）在是一种较线性表和树更为复杂的数据结构。
在线性表中，数据元素之间是被串起来的，只有线性关系，每个数据元素只有一个直接前驱和一个直接后继。
在树形结构中，数据元素之间有着很明显的层次关系，并且每一层的数据元素可能和下一层的多个元素相关，但是只能和上一层的一个元素相关。 这就和一对父母可以有多个孩子，但是一个孩子只能有一对亲生父母一样。
但是实际上，在现实生活中，很多事物和人际关系都是十分复杂的，并非简单的一对一、一对多的关系。这个时候就可以用图这种数据结构来表示，在图的数据结构中，结点之间的关系可以是任意的，图中任意两个数据元素都是可能相关的。
在图中的数据元素叫做顶点（Vertex），假定V是顶点的有穷非空集合；VR是两个顶点直接的关系的集合。若<v,w>∈VR，则<v,w>表示从v到w的一条弧（Arc），且称v为弧尾（Tail）或初始点，称w为弧头（Head）或终端点。
如果<v,w>∈VR，必有<w,v>∈VR，即VR是对称的，则以无序对（v,w)来代替这两个有序对，表示v和w之间的一条边（Edge），边是没有方向的，此时的图称为无向图
如果图的弧或边具有与它相关的数字，则称这种与图的边或弧相关的数叫做权值（Weight），这种带权值的图成为网（Net）。带权值的有向图成为有向网
带权值的无向图称为无向网
用一维数组存储图中顶点的信息（顶点表），用二维数组存储图中边或弧的信息（邻接矩阵）。
在无向图和有向图中，若两顶点之间有边或弧，则二维数组中点为1，否则为0。
在无向网和有向网中，若两顶点之间有边或弧，则二维数组中的点为其权值，否则为∞。
当边数相对顶点数较少的图时，邻接矩阵这种结构会极大的浪费存储空间。于是我们使用一种把数组和链表相结合的存储方式——邻接表，用一个一维数组来存放顶点信息（顶点表），在将图中的每个顶点所有邻接点构成一个线性表，用单链表存储。
还有十字链表、邻接多重表和边集数组这三种存储结构，本文不着重说明。 本文重点讲解无向图的邻接矩阵基本操作
首先定义和声明一下之后会用到的宏
无向图的数据元素的声明和队列的数据元素的声明（队列在广度优先遍历中会使用到）
#include<iostream>
using namespace std;
typedef char VertexType;
typedef int EdgeType;
typedef int status;
typedef int QElemType;
#define MAXVEX 20 //最大顶点个数设置为20
#define MAXSIZE 20 //设置队列的最大容量为20
#define ERROR 0
#define OK 1
bool Visited[MAXVEX]; //设置一个布尔变量，用于在两种遍历的时候标志顶点是否被访问过
typedef struct MGraph //无向图的数组表示法存储结构
{
VertexType vexs[MAXVEX]; //顶点表
EdgeType arc[MAXVEX][MAXVEX]; //邻接矩阵
int vertexs_num; //顶点数
}MGraph;
创建无向图所需要的信息是顶点信息和边关系
因为无向图的邻接矩阵是对称的，所以G.arc[i][j]=G.arc[j][i]
void Create(MGraph& G)
{ //创建一个无向图
int i, j;
cout << endl;
cout << "该无向图的顶点个数为：";
cin >> G.vertexs_num;
cout << endl;
cout << "请依次输入顶点" << endl<<endl;
for (i = 0; i < G.vertexs_num; ++i)
{//输入顶点表，构成一维的顶点数组
cout << "第" << i + 1 << "个顶点值为：";
cin >> G.vexs[i];
}
for (i = 0; i < G.vertexs_num; ++i)
G.arc[i][i] = 0; //初始化邻接矩阵,即无向图中主对角线所有元素都为0
for (i = 0; i < G.vertexs_num; i++)
for (j = i + 1; j < G.vertexs_num; j++)
{
cout << "若元素"<< G.vexs[i] <<"和元素"<< G.vexs[j] <<"有边，则输入1，否则输入0：";
cin >> G.arc[i][j];
G.arc[j][i] = G.arc[i][j];
}
}
先输出顶点表，再输出二维的邻接矩阵
void Print(MGraph G)
{
int i, j;
cout << endl;
cout << "该无向图的信息如下：" << endl << endl;;
cout << "顶点元素表：" << endl;
for (i = 0; i < G.vertexs_num; i++)
cout << G.vexs[i] << " ";
cout << endl<<endl;
cout << "邻接矩阵如下：" << endl;
cout << " ";
for (i = 0; i < G.vertexs_num; i++)
cout << " " << G.vexs[i];
cout << endl;
for (i = 0; i < G.vertexs_num; i++)
{
cout << G.vexs[i];
cout << " ";
for (j = 0; j < G.vertexs_num; j++)
cout << " " << G.arc[i][j];
cout << endl;
}
cout << endl;
}
图的遍历是从某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。
通常有两种遍历次序的方法：深度优先遍历和广度优先遍历。
深度优先遍历又叫深度优先搜索，简称为DFS，类似于树的先根遍历，其实是一个递归的过程
从某顶点v出发进行DFS的基本思想为：
void DFS(MGraph G, int i)
{
int j;
Visited[i] = true; //将该顶点设置为已访问过的
cout << G.vexs[i] << " ";
for (j = 0; j < G.vertexs_num; j++)
{
if (G.arc[i][j] == 1 && !Visited[j] ) //如果两点之间有边并且第j+1个顶点没有被访问过
DFS(G, j);
}
}
void DFSTraverse(MGraph G)
{ //深度优先遍历算法
int i;
cout << endl;
cout << "深度优先搜索的序列为： " ;
for (i = 0; i < G.vertexs_num; i++)
Visited[i] = false; //将所有的顶点都设置为未访问
for(i=0;i<G.vertexs_num;i++)
if(!Visited[i])
DFS(G,i);
cout << endl << endl;;
}
广度优先遍历又称为广度优先搜索，简称BFS，类似于树的层次遍历。
从某顶点v出发进行BFS的基本思想为：
如果说深度优先遍历是一次遍历一个，那么广度优先遍历就是一次遍历一层
故这里要运用到队列这种先进先出的输出方法
算法思想为：
typedef struct { //队列的数据结构(队列在广度优先遍历里会使用到）
QElemType* base; //初始化时动态分配空间
int front; //头指针,队列非空时，指向队头元素
int rear; //尾指针，队列非空时，指向队尾元素的下一个位置
}SqQueue;
status InitQueue(SqQueue &Q)
{ //初始化空队列
Q.base= (QElemType *)malloc(MAXSIZE *sizeof(QElemType));
if (Q.base == NULL)
{
cout << "分配内存失败！" << endl;
exit(0);
}
Q.front = 0;
Q.rear = 0;
return OK;
}
status QueueEmpty(SqQueue Q)
{ //判断队列是否为空
if (Q.front == Q.rear) //头尾相等则说明是空队列
return ERROR;
else
return OK;
}
status push(SqQueue &Q, QElemType e)
{ //在队尾插入元素
if ((Q.rear + 1) % MAXSIZE == Q.front)//队列已满
return ERROR;
Q.base[Q.rear] = e;//插入队尾
Q.rear = (Q.rear + 1) % MAXSIZE;//尾部指针后移，如果到最后则转到头部
return OK;
}
status pop(SqQueue &Q, QElemType & e)
{ //元素出队,并用e返回被删除的队头元素
if (Q.front == Q.rear)//队列空
return ERROR;
e = Q.base[Q.front];//返回队头元素
Q.front = (Q.front + 1) % MAXSIZE;//队头指针后移，如到最后转到头部
return OK;
}
void BFSTraverse(MGraph G)
{ //广度优先遍历算法
SqQueue Q;
int i,j;
QElemType k;
int mark; //用于标记
cout << endl;
cout << "广度优先搜索的序列为： ";
InitQueue(Q);
for (i = 0; i < G.vertexs_num; ++i)
Visited[i] = false;
for (i = 0; i < G.vertexs_num; ++i)
{
if (!Visited[i])
{
Visited[i] = true;
push(Q,G.vexs[i]); //该顶点入队
cout << G.vexs[i] << " ";
while (!QueueEmpty(Q))
{
pop(Q, k); //该顶点出队，把出队的元素赋值给k
cout << k << " ";
for (j = 0; j < G.vertexs_num; j++)
{
if (G.vexs[j] == k) mark = k; //将此时的队头元素标记
}
for (j = 0; j < G.vertexs_num; ++j)
{
if (G.arc[mark][j]==1&&!Visited[j]) //将表中标记行中未被访问的结点入队
{
Visited[j] = true;
cout << G.vexs[j] << " ";
push(Q,G.vexs[j]);
}
}
}
}
}
cout << endl << endl;
}
主函数如下
int main()
{
int a;
SqQueue Q;
InitQueue(Q);
MGraph G;
cout << "1.创建无向图 2.输出无向图的信息 3.用深度优先遍历（DFS）无向图 4.用广度优先遍历（BFS）无向图 " <<endl<< endl;
while (1)
{
cout << " 请输入想要执行的操作： ";
cin >> a;
switch (a)
{
case 1: Create(G); break;
case 2: Print(G); break;
case 3: DFSTraverse(G); break;
case 4: BFSTraverse(G); break;
default: cout << "请重新输入正确的操作！" << endl;
}
}
return 0;
}
对下图进行操作
别因为学会说话，尝到了甜头，就忘记了做人