（一）图的表示
给定图G=(V,E)，其中V表示图的点、E表示图的边，V[G]表示图G的点集合，E[G]表示图G的边集合。
表示方法：邻接表，邻接矩阵，均可用于有向图和无向图
有向图，两个顶点间有方向，是单向边，而无向图两个顶点之间是双向边。
1）邻接表
当图G中|E|（边）远小于|V|2（点）时，即为稀疏图，适用邻接表表示。
图G=(V,E)的邻接表表示由一个包含|V|个列表的数组Adj所组成，其中每个列表对应于V中的一个顶点。对于每一个u∈V，邻接表Adj[u]包含所有满足(u,v)∈E的顶点v。即Adj[u]中包含图G中所有和顶点u相邻的顶点，邻接表的长度之和为|E|，u指向v为一条边。
如果G是有向图，则是包含u指向的顶点。每个邻接表中的顶点一般以任意顺序存储，邻接表的长度之和为2|E|，u和v双向两条边。
邻接表的存储空间为⊙(V+E)，如果是图边是加权的，可以把权值w(u,v)存储在相应数组中表示。
2）邻接矩阵
当图G中|E|接近|V|2时，即为稠密图，或者需快速判断两个顶点间是否存在连接边时，适用邻接矩阵表示。
图G=(V,E)的邻接矩阵表示，假定各顶点编号从1,2，…，|V|，那么G的邻接矩阵为一个|V|X|V|的矩阵A=(aij)，满足：aij=1，如果(i,j)∈E；aij=0，如果(i,j)∉E；在有向图中属于E[G]边集合是从i到j的指向。
邻接矩阵的存储空间为⊙(V2)，与图中的边数无关。如果是无向图，矩阵A是对称矩阵，可以只存储对角线及对角线以上部分，存储空间节省近一半。如果图边是加权的，可以在相应矩阵行列点上存储权值。如果是非加权图，存储邻接矩阵的每个元素时，可以只用一个二进制位表示，而不必用一个字的空间。
（二）广度优先搜索 （BFS）
定义：首先访问出发点v，接着访问v的所有邻接点w1，w2……wt，然后在依次访问与w1，w2……wt邻接的所有未曾访问过的顶点。以此类推，直至图中所有和起点v有路径想通的顶点都已访问到为止，此时从v开始的搜索过程结束。
#include <stdio.h>
#define N 4
//广度优先搜索算法，邻接矩阵表示
int qh,qe,visited[100];
int sq[100];
int bfsm(){
int g[][N]={{0,1,1,0},{0,0,0,0},{0,0,0,1},{1,0,0,0}};
int i;
qh=0;//队首
qe=1;//队尾
sq[0]=0;//sq[0]=k;从k开始搜索
visited[0]=1;//visited[k]=1;
printf("%d ",sq[0]+1);
while(qh!=qe)
{
for(i=0;i<N;i++)
{
if(g[sq[qh]][i]==1&&visited[i]==0)//核心
{
sq[qe]=i;
visited[i]=1;
printf("%d ",i+1);
qe++;
}
}
qh++;
}
return 0;
}
int main() {
int i;
for(i=0;i<N;i++)
visited[i]=0;
bfsm();
printf("\n");
return 0;
}应用：广度优先搜索类似于树的层次遍历，逐层搜索，适用于最短路径问题
例：已知若干个城市的地图，要求一个城市到另一个城市的路径，要求途中经过的城市最少（A->H）
#include <stdio.h>
#define N 8
int qh,qe,visited[100];
struct {
int city,pre; //pre：前趋城市队列中的下标
}sq[100];
int out() //从起点到终点输出
{
int i,j,a[N];
i=0;
do{
a[i++]=sq[qe].city;
qe=sq[qe].pre;
}while(qe!=0);
a[i]=sq[0].city;
printf("%d(%c)",a[i]+1,a[i]+'A');
for(j=--i;j>=0;j--)
printf("%d(%c)",a[j]+1,a[j]+'A');
printf("\n");
return 0;
}
int search()
{
int jz[][N]={{0,1,1,1,0,1,0,0},{1,0,0,0,0,1,0,0},{1,0,0,1,1,0,0,0},
{1,0,1,0,0,0,1,0},{0,0,1,0,0,0,1,1},{1,1,0,0,0,0,0,1},
{0,0,0,1,1,0,0,1},{0,0,0,0,1,1,1,0}};
int i,flag;
qh=0;
qe=1;
sq[0].city=0;
visited[0]=1;
flag=1;
while(qh!=qe&&flag)
{
for(i=0;i<N&&flag;i++)
{
if(jz[sq[qh].city][i]==1&&visited[i]==0)
{
sq[qe].city=i;
sq[qe].pre=qh;
visited[i]=1;
if(sq[qe].city==N-1)
{
out();
flag=0;
}
qe++;
}
}
qh++;
}
if(flag)
printf("Non solution.\n");
}
int main() {
int i;
for(i=0;i<N;i++)
visited[i]=0;
search();
return 0;
}（三）深度优先搜索（DFS）
定义：首先访问出发点v，并将其标记为一访问过；然后依次从v出发搜索v的每一个邻接点w，若w未曾访问过，则以w为新的厨房点继续进行深度优先搜索，直至图中所有和源点v有路径相通的顶点都已被访问为止。
#include <stdio.h>
#define N 4
//深度优先搜索算法，用邻接矩阵表示
int visited[N];
int g[][N]={{0,1,1,0},{0,0,0,0},{0,0,0,1},{1,0,0,0}};
int dfsm(int g[][N],int k)
{
int j;
printf("%d ",k+1);
visited[k]=1;
for(j=0;j<N;j++)
if(g[k][j]==1&&visited[j]==0) //核心
dfsm(g,j);
}
int main() {
int i;
for(i=0;i<N;i++)
visited[i]=0;
dfsm(g,0);
printf("\n");
return 0;
}应用：七巧板涂色问题，共4种颜色，相邻区域涂不同颜色
涂色过程：（1）对某一区域涂上与其相邻区域不同的颜色
（2）若使用4种颜色进行涂色均不能满足要求，则回溯一步，更改前一区域的颜色
（3）转步骤（1）继续涂色，直到所有区域全部涂色位置，输出结果
#include <stdio.h>
#define N 7
int color[N];
int output()
{
int i;
static int total=1;
printf("serial number:%3d ",total);
for(i=0;i<N;i++)
printf("%d ",color[i]);
printf("\n");
total++;
return 0;
}
int colorsame(int s)
{
int i,flag=0;
int data[][N]={{0,1,0,0,1,0,1},{1,0,0,1,0,1,0},{0,0,0,1,0,0,1},{0,1,1,0,0,1,1},
{1,0,0,0,0,0,1},{0,1,0,1,0,0,0},{1,0,1,1,1,0,0}};
for(i=0;i<s&&!flag;i++)
{
if(data[s][i]==1&&color[i]==color[s])//核心
flag=1;
}
return flag;
}
int try(int s)
{
int i;
if(s==N)
output();
else
for(i=0;i<4;i++)
{
color[s]=i;
if(colorsame(s)==0)
try(s+1);
}
}
int main() {
int i;
for(i=0;i<N;i++)
color[i]=0;
try(1);
return 0;
}