一、定义：图是比线性结构和树更复杂的一种数据结构，用来表示多对多的关系。
例如：某选修课一共报了n名学生，而这n名学生不仅报了这门课，还选修了其他课程，且彼此不一定相同。这就是一种图的结构。
图（Graph）G由两个集合顶点V（Vertex）和边E（Edge）组成，记作G=（V,E）。其中顶点V是有穷非空集合，E是V中任意两个顶点关系的有穷集合，关系通过边实现。
二、图的分类：有向图、无向图
图又分为有向图和无向图，有向图是指图中任意边都具有方向性，只能表示v1指向v2或者v2指向v1其中一种情况，E为有向边的集合；无向图是指图中任意边均无方向性，可表示v1指向v2，也可表示v2指向v1，这类图叫做无向图，E为无向边的集合。
三、图的基本术语：
1、子图：图G1完全属于图G2，那么G1就称为G2的子图；任意单个顶点V，是其所在图的子图。
2、无向完全图和有向完全图：无向图G中任意两个顶点均存在对应边，则这个图称作无向完全图，边的条数为n（n-1）/2;有向图G中任意一个顶点均存在指向其余的所有顶点的边，则这个图称作有向完全图，边或弧的条数为n（n-1）。
3、稀疏图和稠密图：有很少条边或弧（边的条数E远小于V²）的图称为稀疏图（sparse graph），反之边的条数|E|接近V²，称为稠密图（dense graph）。
4、权和网：在实际应用中，在图中的边上标记上具有某种含义的数值，该数值称为该边上的权，这些权可以表示两个顶点的距离和耗费等信息。这种带权的图称为网。
5、邻接点：无向图中任意两个顶点V和W中间存在边，那么这两个顶点互为邻接点；有向图中任意顶点V，若存在边E指向另一任意顶点W，则顶点W是顶点V的邻接点。
6、度以及入度和出度：图中和顶点V相关联的边的数量，称为顶点V的度；有向图中，从顶点V发出的边的数量称为顶点V的出度，指向顶点V的边的数量称为顶点V的入度。
7、路径和路径长度：图G中，从顶点V到顶点W，所经过的顶点形成序列（V、V1、V2……W），且序列中任意相邻顶点均为邻接点，这个序列称作顶点V到顶点W的路径；若G为有向图，则路径也是有向的；路径中经过的边（或弧）的数目叫做路径长度。
8、回路或环：第一个顶点和最后一个顶点相同的路径，称作回路或环；单个顶点不允许回路。
9、简单路径、简单回路或简单环：路径中无重复经过的顶点，则这条路径叫做简单路径；同理，除了回路或环中第一个和最后一个顶点外，无其他重复经过的顶点，则这条回路或者环叫做简单回路或简单环。
10、连通、连通图和连通分量：无向图G中，顶点V和顶点W之间存在路径，则称顶点V和顶点W连通；若图G中任意两个顶点连通，则G为连通图；图G中的每个极大连通子图叫做连通分量。
11、强连通图和强连通分量：如有向图G中，任意两个不相同顶点V和W，均存在双向路径（注意路径不是边），则称图G为强连通图；有向图G中的每个极大连通子图，称作有向图G的强连通分量；有向图可以不是强连通图，但可以有连通分量。
12、连通图的生成树：对连通图进行遍历过程，经过的顶点和边的组合可以看做树，这棵树叫作该连通图的生成树；因对树的遍历可能存在多种路径，那么一个连通图也可能存在多棵生成树。
13、生成森林：非连通图可分解为若干连通分量，将每个连通分量生成树就是该图的生成森林。
四、图的邻接矩阵表示法和邻接表表示法：
1、邻接矩阵表示法（适用于稠密图）：用二维数组存放边的权值，二维数组的行和列表示图的顶点。储存无向图时等于是将一条边存了两次，例如：G[3][5]=5，表示顶点3到顶点5的边上权值为5；那么G[5][3]表示顶点5到顶点3，因为是无向图，则G[3][5]和G[5][3]表示同一条边。
为了减少空间浪费可以用一个n*(n+1)/2的一维数组存放。
邻接矩阵 —— 方便检查任意一对顶点间是否存在边 ，方便找任一顶点的所有“邻接点”，方便计算任一顶点的“度”（有向图：从该点发出的边数为“出 度”，指向该点的边数为“入度”）；无向图：对应行（或列）非 0元素的个数为该顶点的度。 有向图：对应行非0元素的个数为出度，对应列非0元素的个数为入度。
2、邻接表表示法（适用于稀疏图）：用一个结构体表示顶点，用一个顶点的指针数组表示图中顶点的集合。对应顶点的邻接点插入至链表。
邻接表方便找任一顶点的所有“邻接点” ，节约稀疏图的空间，需要 N个头指针 + 2E个结点（每个结点至少 2个域，若带权重，结构体需添加权重域）。对无向图：方便计算每个顶点的度；对有向图：只能计算“出度”；需要构造“逆邻接表”（存指向自己 的边）来方便计算“入度” 。
不方便检查任意两个顶点是否存在边。
五、图的基本操作：
1、Graph *init_graph(VertexNum n);初始化有n个顶点，无边的图；
2、Edge *init_edge(Vertex v1,Vertex v2,WeightType weight);初始化一条从v1到v2的边，带权。
3、void insert_graph(Graph *pGraph,Edge *pEdge);将边pEdge插入到图pGraph中。
4、void DFS(Graph *pGraph);深度优先遍历
5、void BFS(Graph *pGraph);广度优先遍历
六、上代码：
（一）邻接矩阵实现
graph.h
#ifndef GRAPH_H
#define GRAPH_H
#include <stdio.h>
#include <stdlib.h>
#define MaxVertex 100
#define INFINITY 65535
typedef int WeightType; //定义权重类型为整形
typedef char DataType; //定义顶点内储存的数据为字符型
/*图的定义*/
typedef struct Gnode Graph;
struct Gnode{
int nV;
int nE;
WeightType G[MaxVertex][MaxVertex];
DataType data[MaxVertex];
};
/*顶点定义*/
typedef int Vertex;
/*边的定义*/
typedef struct Enode Edge;
struct Enode{
Vertex V1,V2;
WeightType weigh;
};
typedef Vertex Element;
int visited[MaxVertex];
typedef struct queue_node Que;
struct queue_node{
Element data[MaxVertex];
int front,rear;
};
#endif
Graph *init_graph(int VertexNum); //初始一个有VertexNum个顶点，没有边的图
Edge *init_edge(Vertex v1,Vertex v2,WeightType weigh); //若为有向图，此边只表示v1-v2，不表示v2-v1
void insert_graph(Graph *pGraph,Edge *pEdge); //将图中某两个顶点链接起来，也就是向图中插入一条边
Graph *build_graph();
void init_visited();
void DFS(Graph *pGraph,Vertex v);
void BFS(Graph *pGraph,Vertex v);
Que *init_Queue(Que *pQ,int n);
int isempty_Queue(Que *pQ);
void in_Queue(Que *pQ,Vertex v);
Vertex out_Queue(Que *pQ);
graph.c
#include "graph.h"
Graph *init_graph(int VertexNum){ //初始一个有VertexNum个顶点，没有边的图
Graph *pGraph=(Graph*)malloc(sizeof(Graph));
pGraph->nV=VertexNum;
pGraph->nE=0;
for(int r=0;r<VertexNum;r++){
for(int l=0;l<VertexNum;l++){
pGraph->G[r][l]=-1;
}
}
return pGraph;
}
Edge *init_edge(Vertex v1,Vertex v2,WeightType weigh){ //若为有向图，此边只表示v1-v2，不表示v2-v1
Edge *pEdge=(Edge*)malloc(sizeof(Edge));
pEdge->V1=v1;pEdge->V2=v2;pEdge->weigh=weigh;
return pEdge;
}
void insert_graph(Graph *pGraph,Edge *pEdge){//将图中某两个顶点链接起来，也就是向图中插入一条边
pGraph->G[pEdge->V1][pEdge->V2]=pEdge->weigh; //有向图v1-v2
pGraph->nE++;
/*若为无向图需进行反向操作： */
pGraph->G[pEdge->V2][pEdge->V1]=pEdge->weigh;
pGraph->nE++;
free(pEdge);
}
Graph *build_graph(){
int Vn=0;
Vertex v1=0,v2=0;
Edge *pEdge=NULL;
WeightType weight=-1;
printf("图中需要多少个顶点？\n");
scanf("%d",&Vn);
Graph *pGraph=init_graph(Vn);
printf("请输入需要连接的顶点和权值：\n");
scanf("%d%d%d",&v1,&v2,&weight);
do{
pEdge=init_edge(v1,v2,weight);
insert_graph(pGraph,pEdge);
printf("请输入需要连接的顶点和权值：\n");
scanf("%d%d%d",&v1,&v2,&weight);
}while(v1!=-1);
return pGraph;
}
void init_visited(int nV){
for(int i=0;i<nV;i++){
visited[i]=0;
}
}
void DFS(Graph *pGraph,Vertex v){ //递归n次，递归中又循环n次，时间复杂度O(n2)；
if(!visited[v]){
visited[v]=1;
printf("%d ",v);
}
for(Vertex w=0;w<pGraph->nV;w++){
if(pGraph->G[v][w]>=0&&!visited[w]){
DFS(pGraph,w);
}
}
}
void BFS(Graph *pGraph,Vertex v){
if(!visited[v]){
visited[v]=1;
printf("%d ",v);
}
Que *pQ=init_Queue(pQ,pGraph->nV);
in_Queue(pQ,v);
while(!isempty_Queue(pQ)){
v=out_Queue(pQ);
for(Vertex w=0;w<pGraph->nV;w++){
if(pGraph->G[v][w]>=0&&!visited[w]){
visited[w]=1;printf("%d ",w);
in_Queue(pQ,w);
}
}
}
}
Que *init_Queue(Que *pQ,int n){
pQ=(Que*)malloc(sizeof(Que));
pQ->front=pQ->rear=0;
for(int i=0;i<n;i++){
pQ->data[i]=-1;
}
return pQ;
}
int isempty_Queue(Que *pQ){
return pQ->front==pQ->rear;
}
void in_Queue(Que *pQ,Vertex v){
pQ->data[++pQ->rear]=v;
}
Vertex out_Queue(Que *pQ){
return pQ->data[++pQ->front];
}main.c
#include <stdio.h>
#include <stdlib.h>
#include "graph.h"
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int main(int argc, char *argv[]) {
Graph *pGraph=build_graph();
init_visited(pGraph->nV);
DFS(pGraph,0);printf("\n");
init_visited(pGraph->nV);
BFS(pGraph,0);printf("\n");
return 0;
}（二）邻接表实现
graph_list.h
#ifndef GRAPH_LIST_H
#define GRAPH_LIST_H
#include <stdio.h>
#include <stdlib.h>
#define MaxVertexNum 100
/*邻接表表示图，用数组的下标来表示图的顶点，顶点结构体包含指向边的指针，
用链表将一个顶点出发的所有边串起来*/
typedef int Vertex; //定义顶点类型，下标表示顶点序号
typedef int WeightType; //定义边的权重类型
typedef char VertexData; //定义顶点包含的数据信息类型
/*声明边结构体，包含邻接点序号和权重,*/
typedef struct edge_node Edge; //声明边结构体
struct edge_node{
Vertex v; //邻接点序号
WeightType weight; //边的权重
Edge *next; //指向下一条边
};
/*声明顶点结构体,也是邻接表的表头数组类型,包含数据信息和指向边的指针*/
typedef struct head_node{
VertexData data;
Edge *next;
}EdgeList[MaxVertexNum];
/*声明图结构体，包含顶点和边的数量和邻接表*/
typedef struct _gnode Graph;
struct _gnode{
int nV,nE;
EdgeList edge;
};
/*声明队列结构体*/
typedef struct _queue Que;
typedef Vertex Element;
struct _queue{
int head,rear;
Element data[MaxVertexNum];
};
int visited[MaxVertexNum];
#endif
Graph *init_graph(int VertexNum); //初始化一个包含VertexNum个顶点，0条边的图
Edge *init_edge(Vertex v,WeightType weight); //若为有向图，此边只表示指向v，不表示从v出发
void insert_graph(Graph *pGraph,Vertex v,Edge *pEdge); //从v出发，连一条边
Graph *build_graph();
void init_visited();
void DFS(Graph *pGraph,Vertex v);
void BFS(Graph *pGraph,Vertex v);
Que *init_Queue(Que *pQ,int n);
int isempty_Queue(Que *pQ);
void in_Queue(Que *pQ,Vertex v);
Vertex out_Queue(Que *pQ);
graph_list.c
#include "graph_list.h"
Graph *init_graph(int VertexNum){ //初始化一个包含VertexNum个顶点，0条边的图
Graph *pGraph=(Graph*)malloc(sizeof(Graph));
pGraph->nV=VertexNum;
pGraph->nE=0;
for(Vertex v=0;v<VertexNum;v++){
pGraph->edge[v].next=NULL;
}
return pGraph;
}
Edge *init_edge(Vertex v,WeightType weight){ //初始化指向v的边，并赋值权重weight
Edge *pEdge=(Edge*)malloc(sizeof(Edge));
pEdge->v=v;
pEdge->weight=weight;
pEdge->next=NULL;
return pEdge;
}
void insert_graph(Graph *pGraph,Vertex v,Edge *pEdge){ //从v出发，连一条边
pEdge->next=pGraph->edge[v].next;
pGraph->edge[v].next=pEdge;
pGraph->nE++;
}
Graph *build_graph(){
int Vn=0;
Vertex v1=0,v2=0;
Edge *pEdge=NULL;
WeightType weight=-1;
printf("图中需要多少个顶点？\n");
scanf("%d",&Vn);
Graph *pGraph=init_graph(Vn);
printf("请输入需要连接的顶点和权值：\n");
scanf("%d%d%d",&v1,&v2,&weight);
do{
pEdge=init_edge(v2,weight);
insert_graph(pGraph,v1,pEdge);
/*如果是无向图，需要反向再连接一次
pEdge=init_edge(v1,weight);
insert_graph(pGraph,v2,pEdge);*/
printf("请输入需要连接的顶点和权值：\n");
scanf("%d%d%d",&v1,&v2,&weight);
}while(v1!=-1);
return pGraph;
}
void init_visited(){
for(Vertex v=0;v<MaxVertexNum;v++){
visited[v]=0;
}
}
void DFS(Graph *pGraph,Vertex v){
if(!visited[v]){
visited[v]=1;
printf("%d ",v);
}
for(Edge *p=pGraph->edge[v].next;p;p=p->next){
if(!visited[p->v]){
DFS(pGraph,p->v);
}
}
}
void BFS(Graph *pGraph,Vertex v){
Que *pQ=init_Queue(pQ,pGraph->nV);
printf("%d ",v);
visited[v]=1;
in_Queue(pQ,v);
while(!isempty_Queue){
v=out_Queue(pQ);
for(Edge *w=pGraph->edge[v].next;w;w=w->next){
if(!visited[w->v]){
printf("%d ",w->v);
visited[w->v]=1;
in_Queue(pQ,w->v);
}
}
}
}
Que *init_Queue(Que *pQ,int n){
pQ=(Que*)malloc(sizeof(Que));
pQ->head=pQ->rear=0;
for(int i=0;i<n;i++){
pQ->data[i]=-1;
}
return pQ;
}
int isempty_Queue(Que *pQ){
return pQ->head==pQ->rear;
}
void in_Queue(Que *pQ,Vertex v){
pQ->data[++pQ->rear]=v;
}
Vertex out_Queue(Que *pQ){
return pQ->data[++pQ->head];
}
文章出处登录后可见！
