图是一种相对较为复杂的数据结构，由结点及各结点之间的相互关系组成。图中结点之间的关系可以是任意的，也就是说图中任何两个结点之间都可能是有关系的。图中的各个结点称为顶点（vertex）。图分为有向图和无向图。图一中左边是有向图，右边是无向图。
图一
2.图的存储结构
2.1数组表示法
数组表示法又称为邻接矩阵表示法，是用两个数组分别存储顶点信息和顶点之间的关系即边的信息。
[cpp]
view plaincopy#define VERTEXNUM 100 //存储顶点数目
typedef int VertexType;
typedef int EdgeType;
typedef struct
{
VertexType vertexs[VERTEXNUM]; //顶点表
EdgeType edges[VERTEXNUM][VERTEXNUM]; //邻接矩阵存储顶点间关系
int vernum, edgenum; //图中当前的顶点和边数
}Graph;
邻接矩阵表示中建立邻接矩阵及输出程序如下：
[cpp]
view plaincopy#include <cstdio>
#include <cstdlib>
#define VERTEXNUM 100 //存储顶点数目
typedef int VertexType;
typedef int EdgeType;
typedef struct
{
VertexType vertexs[VERTEXNUM]; //顶点表
EdgeType edges[VERTEXNUM][VERTEXNUM]; //邻接矩阵存储顶点间关系
int vernum, edgenum; //图中当前的顶点和边数
}Graph;
void MakeGraph(Graph *&graph)
{
int v1, v2;
int i, j, k;
printf("请输入图的顶点数n和边数e:\n");
scanf("%d%d", &graph->vernum, &graph->edgenum);
printf("顶点编号设置为1~n.\n");
for(i = 0; i < graph->vernum; i++)
{
graph->vertexs[i] = i + 1;
}
for(i = 0; i < graph->vernum; i++) //边信息初始化
{
for(j = 0; j < graph->vernum; j++)
{
graph->edges[i][j] = 0;
}
}
printf("请输入每条边对应的两个顶点的序号(格式为i,j):\n");
for(k = 0; k < graph->edgenum; k++)
{
scanf("%d,%d", &v1, &v2);
graph->edges[v1 - 1][v2 - 1] = 1;
}
}
int main()
{
Graph *graph = (Graph *)malloc(sizeof(Graph));
MakeGraph(graph);
//输出邻接矩阵
for(int i = 0; i < graph->vernum; i++)
{
for(int j = 0; j < graph->vernum; j++)
{
printf("%d ", graph->edges[i][j]);
}
printf("\n");
}
return 0;
}
2.2邻接表表示法
邻接表中，对图中每个顶点建立一个单链表，单链表i中的结点表示依附于顶点vi的边。将这些单个的单链表连接组成的链式存储结构就是图的邻接表（Adjacency List）。结构如下：
[cpp]
view plaincopy#define VERTEXNUM 100 //顶点个数
typedef int VertexType;
typedef int EdgeType;
typedef struct node
{
int adjvex; //顶点位置
struct node *next; //指向下一条边的指针
}EdgeNode;
typedef struct vnode
{
VertexType vertex; //顶点信息
EdgeNode *firstedge; //指向第一条依附该顶点的边的指针
}AdjList[VERTEXNUM];
typedef struct
{
AdjList vertexs; //邻接表
int vernum, edgenum; //图中当前的顶点和边数
}Graph;
建立邻接表及其输出程序如下：
[cpp]
view plaincopy#define VERTEXNUM 100 //顶点个数
typedef int VertexType;
typedef int EdgeType;
typedef struct node
{
int adjvex; //顶点位置
struct node *next; //指向下一条边的指针
}EdgeNode;
typedef struct vnode
{
VertexType vertex; //顶点信息
EdgeNode *firstedge; //指向第一条依附该顶点的边的指针
}AdjList[VERTEXNUM];
typedef struct
{
AdjList vertexs; //邻接表
int vernum, edgenum; //图中当前的顶点和边数
}Graph;
void MakeGraph(Graph *graph)
{
int i, j, k;
printf("请输入图的顶点数n和边数e:\n");
scanf("%d%d", &graph->vernum, &graph->edgenum);
printf("顶点编号设置为1~n.\n");
for(i = 0; i < graph->vernum; i++)
{
graph->vertexs[i].vertex = i + 1; //顶点编号为1~n
graph->vertexs[i].firstedge = NULL; //初始第一条边为空
}
printf("请输入每条边对应的两个顶点的序号(格式为i,j):\n");
EdgeNode *p;
for(k = 0; k < graph->edgenum; k++)
{
scanf("%d,%d", &i, &j); //读入边<vi,vj>的序号
p = (node *)malloc(sizeof(node)); //生成新的结点
p->adjvex = j;
p->next = graph->vertexs[i - 1].firstedge;
graph->vertexs[i - 1].firstedge = p;
}
}
int main()
{
Graph *graph = (Graph *)malloc(sizeof(Graph));
MakeGraph(graph);
EdgeNode *p;
//输出邻接表
for(int i = 0; i < graph->vernum; i++)
{
p = graph->vertexs[i].firstedge;
while(p != NULL)
{
printf("%d ", p->adjvex);
p = p->next;
}
printf("\n");
}
return 0;
}
2.3十字链表
十字链表可以看成是将有向图的邻接表和逆邻接表结合得到的一种链表。在十字链表中，因为容易找到以某顶点为尾的边，也容易找到以其为头的边，因而比较容易求得顶点的出度和入度。
3、深度优先搜索(Depth First Search)
深度优先搜索假设初始状态下图中所有顶点都未被访问，尝试优先搜索从图中某个顶点v出去，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直到图中所有和v相连连的顶点都被访问到。如果此时图中还有没有访问到的顶点，则另选图中未被访问的某顶点作为起始点，重复上述过程，直到图中所有顶点都被访问到。具体实现如下：
[cpp]
view plaincopy#include <cstdio>
#include <cstdlib>
#define VERTEXNUM 100 //顶点个数
typedef char VertexType; //顶点类型
typedef int EdgeType;
typedef enum{FALSE, TRUE} Boolean;
Boolean visited[VERTEXNUM];
/**********************************************
*
* 邻接矩阵存储结构
*
**********************************************/
typedef struct
{
VertexType vertexs[VERTEXNUM]; //顶点
EdgeType edges[VERTEXNUM][VERTEXNUM]; //邻接矩阵
int vernum, edgenum; //图中顶点和边数
}Graph;
/**********************************************
*
* 建立邻接矩阵
*
**********************************************/
void MakeGraph(Graph *graph)
{
int i, j, k;
printf("请输入顶点数和边数:\n");
scanf("%d%d", &graph->vernum, &graph->edgenum);
printf("请输入顶点信息(顶点号<CR>)每个顶点以回车作为结束:\n");
for(i = 0; i < graph->vernum; i++)
{
getchar();
scanf("%c", &graph->vertexs[i]);
}
for(i = 0; i < graph->vernum; i++) //初始化邻接矩阵
{
for(j = 0; j < graph->vernum; j++)
{
graph->edges[i][j] = 0;
}
}
printf("请输入每条边对应的两个顶点的序号(输入格式为:i,j):\n");
for(k = 0; k < graph->edgenum; k++)
{
scanf("%d,%d", &i, &j);
graph->edges[i - 1][j - 1] = 1; //(vi->vj)将edges[i][j]设置为1表示i,j间存在边
}
}
/**********************************************
*
* 深度优先搜索
*
**********************************************/
void DFSTraverse(Graph *graph, int i)
{
printf("深度优先遍历:顶点%c\n", graph->vertexs[i]);
visited[i] = TRUE;
for(int j = 0; j < graph->vernum; j++)
{
if(graph->edges[i][j] == 1 && !visited[j])
DFSTraverse(graph, j);
}
}
void DFS(Graph *graph)
{
int i;
for(i = 0; i < graph->vernum; i++)
visited[i] = FALSE;
for(i = 0; i < graph->vernum; i++)
if(!visited[i])
DFSTraverse(graph, i);
}
int main()
{
Graph *graph = (Graph *)malloc(sizeof(Graph));
MakeGraph(graph); // 建立图
DFS(graph); //深度优先搜索
return 0;
}
对于图一中的图，上述程序运行结果如图二。
图一
图二
深度优先搜索遍历图的时间复杂度为O(n^2)，其中n为图中顶点个数。
4、广度优先搜索(Breadth First Search)
广度优先搜索假设从图中某个顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后再分别从这些邻接点出发依次访问它们的邻接点，并使先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问（因此需要用队列来存储顶点），直到图中所有已被访问的顶点的邻接点都被访问为止。如果此时图中还有未被访问的顶点，则另选图中未被访问的顶点作为起点，重复上述过程，直到图中所有顶点都被访问为止。具体实现如下：
[cpp]
view plaincopy#include <iostream>
#include <queue>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define VERTEXNUM 100 //顶点个数
typedef char VertexType; //顶点类型
typedef int EdgeType;
typedef enum{FALSE, TRUE} Boolean;
Boolean visited[VERTEXNUM];
/**********************************************
*
* 邻接矩阵存储结构
*
**********************************************/
typedef struct
{
VertexType vertexs[VERTEXNUM]; //顶点
EdgeType edges[VERTEXNUM][VERTEXNUM]; //邻接矩阵
int vernum, edgenum; //图中顶点和边数
}Graph;
/**********************************************
*
* 建立邻接矩阵
*
**********************************************/
void MakeGraph(Graph *graph)
{
int i, j, k;
printf("请输入顶点数和边数:\n");
scanf("%d%d", &graph->vernum, &graph->edgenum);
printf("请输入顶点信息(顶点号<CR>)每个顶点以回车作为结束:\n");
for(i = 0; i < graph->vernum; i++)
{
getchar();
scanf("%c", &graph->vertexs[i]);
}
for(i = 0; i < graph->vernum; i++) //初始化邻接矩阵
{
for(j = 0; j < graph->vernum; j++)
{
graph->edges[i][j] = 0;
}
}
printf("请输入每条边对应的两个顶点的序号(输入格式为:i,j):\n");
for(k = 0; k < graph->edgenum; k++)
{
scanf("%d,%d", &i, &j);
graph->edges[i - 1][j - 1] = 1; //(vi->vj)将edges[i][j]设置为1表示i,j间存在边
}
}
/**********************************************
*
* 广度优先搜索
*
**********************************************/
void BFS(Graph *graph)
{
int i, j, k;
queue<int> q;
for(i = 0; i < graph->vernum; i++) //初始化访问标识数组
visited[i] = FALSE;
for(i = 0; i < graph->vernum; i++)
{
if(!visited[i])
{
visited[i] = TRUE;
printf("广度优先遍历:结点%c\n", graph->vertexs[i]);
q.push(i); //入栈
while(!q.empty())
{
j = q.front();
q.pop(); //出栈
for(k = 0; k < graph->vernum; k++)
{
if(graph->edges[j][k] == 1 && !visited[k])
{
printf("广度优先遍历:结点%c\n", graph->vertexs[k]);
visited[k] = TRUE;
q.push(k);
}
}
}
}
}
}
int main()
{
Graph *graph = (Graph *)malloc(sizeof(Graph));
MakeGraph(graph); // 建立图
BFS(graph); //广度优先搜索
return 0;
}
图一中的图，运行上述程序得到的结果如图二。
图一
图二
5、深度优先搜索(Depth First Search)
深度优先搜索假设初始状态下图中所有顶点都未被访问，尝试优先搜索从图中某个顶点v出去，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直到图中所有和v相连连的顶点都被访问到。如果此时图中还有没有访问到的顶点，则另选图中未被访问的某顶点作为起始点，重复上述过程，直到图中所有顶点都被访问到。
采用邻接表存储图的具体实现如下：
[cpp]
view plaincopy#include <cstdio>
#include <cstdlib>
#define VERTEXNUM 100 //顶点个数
typedef char VertexType;
typedef int EdgeType;
typedef enum{FALSE, TRUE} Boolean;
Boolean visited[VERTEXNUM];
/***************************************
*
* 邻接表存储结构
*
* *************************************/
typedef struct node
{
int adjvex; //顶点位置
struct node *next; //指向下一条边的指针
}EdgeNode;
typedef struct vnode
{
VertexType vertex; //顶点信息
EdgeNode *firstedge; //指向第一条依附该顶点的边的指针
}AdjList[VERTEXNUM];
typedef struct
{
AdjList vertexs; //邻接表
int vernum, edgenum; //图中当前的顶点和边数
}Graph;
/***************************************
*
* 建立图的邻接表
*
* *************************************/
void MakeGraph(Graph *graph)
{
int v1, v2;
int i, j, k;
printf("请输入图的顶点数n和边数e:\n");
scanf("%d%d", &graph->vernum, &graph->edgenum);
printf("请输入顶点信息(顶点号<CR>)每个顶点以回车作为结束:\n");
for(i = 0; i < graph->vernum; i++)
{
getchar();
scanf("%c", &graph->vertexs[i].vertex);
graph->vertexs[i].firstedge = NULL; //初始第一条边为空
}
printf("请输入每条边对应的两个顶点的序号(格式为i,j):\n");
EdgeNode *p;
for(k = 0; k < graph->edgenum; k++)
{
scanf("%d,%d", &i, &j); //读入边<vi,vj>的序号
p = (node *)malloc(sizeof(node)); //生成新的结点
p->adjvex = j - 1;
p->next = graph->vertexs[i - 1].firstedge;
graph->vertexs[i - 1].firstedge = p;
}
}
/***************************************
*
* 深度优先遍历
*
* *************************************/
void DFSTraverse(Graph *graph, int v)
{
visited[v] = TRUE;
printf("深度遍历:结点%c\n", graph->vertexs[v].vertex);
EdgeNode *p = graph->vertexs[v].firstedge;
while(p != NULL)
{
if(!visited[p->adjvex])
DFSTraverse(graph, p->adjvex);
p = p->next;
}
}
void DFS(Graph *graph)
{
int i;
for(i = 0; i < graph->vernum; i++)
visited[i] = FALSE;
for(i = 0; i < graph->vernum; i++)
if(!visited[i])
DFSTraverse(graph, i);
}
int main()
{
Graph *graph = (Graph *)malloc(sizeof(Graph));
MakeGraph(graph); //建立图的邻接表
DFS(graph); //深度优先遍历
return 0;
}
对于图一中的图，上述程序运行结果如图二。
图一
6、广度优先搜索(Breadth First Search)
广度优先搜索假设从图中某个顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后再分别从这些邻接点出发依次访问它们的邻接点，并使先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问（因此需要用队列来存储顶点），直到图中所有已被访问的顶点的邻接点都被访问为止。如果此时图中还有未被访问的顶点，则另选图中未被访问的顶点作为起点，重复上述过程，直到图中所有顶点都被访问为止。
采用邻接表存储图的具体实现如下：
[cpp]
view plaincopy#include <iostream>
#include <queue>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define VERTEXNUM 100 //顶点个数
typedef char VertexType;
typedef int EdgeType;
typedef enum{FALSE, TRUE} Boolean;
Boolean visited[VERTEXNUM];
/***************************************
*
* 邻接表存储结构
*
* *************************************/
typedef struct node
{
int adjvex; //顶点位置
struct node *next; //指向下一条边的指针
}EdgeNode;
typedef struct vnode
{
VertexType vertex; //顶点信息
EdgeNode *firstedge; //指向第一条依附该顶点的边的指针
}AdjList[VERTEXNUM];
typedef struct
{
AdjList vertexs; //邻接表
int vernum, edgenum; //图中当前的顶点和边数
}Graph;
/***************************************
*
* 建立图的邻接表
*
* *************************************/
void MakeGraph(Graph *graph)
{
int v1, v2;
int i, j, k;
printf("请输入图的顶点数n和边数e:\n");
scanf("%d%d", &graph->vernum, &graph->edgenum);
printf("请输入顶点信息(顶点号<CR>)每个顶点以回车作为结束:\n");
for(i = 0; i < graph->vernum; i++)
{
getchar();
scanf("%c", &graph->vertexs[i].vertex);
graph->vertexs[i].firstedge = NULL; //初始第一条边为空
}
printf("请输入每条边对应的两个顶点的序号(格式为i,j):\n");
EdgeNode *p;
for(k = 0; k < graph->edgenum; k++)
{
scanf("%d,%d", &i, &j); //读入边<vi,vj>的序号
p = (node *)malloc(sizeof(node)); //生成新的结点
p->adjvex = j - 1;
p->next = graph->vertexs[i - 1].firstedge;
graph->vertexs[i - 1].firstedge = p;
}
}
/***************************************
*
* 广度优先遍历
*
* *************************************/
void BFS(Graph *graph)
{
int i, j, k;
queue<int> q;
EdgeNode *p;
for(i = 0; i < graph->vernum; i++) //初始化访问标识数组
visited[i] = FALSE;
for(i = 0; i < graph->vernum; i++)
{
if(!visited[i])
{
visited[i] = TRUE;
printf("广度优先遍历:结点%c\n", graph->vertexs[i].vertex);
q.push(i); //入栈
while(!q.empty())
{
j = q.front();
q.pop(); //出栈
p = graph->vertexs[j].firstedge;
while(p)
{
if(!visited[p->adjvex])
{
printf("广度优先遍历:结点%c\n", graph->vertexs[p->adjvex].vertex);
visited[p->adjvex] = TRUE;
q.push(p->adjvex);
}
p = p->next;
}
}
}
}
}
int main()
{
Graph *graph = (Graph *)malloc(sizeof(Graph));
MakeGraph(graph); //建立图的邻接表
BFS(graph); //广度优先遍历
return 0;
}
图一中的图，运行上述程序得到的结果如图二。
图一
