目录
一.知识概况：
（1）基本概况：
图(graph)是一种非线性的结构 形式化的语言描述为?Graph=(V,R)，其中 V={Vi|vi属于某种数据类型,i=0,1,2,3 ***,n}是图中元素，vi 称为顶点 。V就是顶点的集合 当n=0 时 V为空集R{<vi,vj>|vi,vj 属于V ，且p(vi,vj存在)}是图中顶点之间的关系的集合 ，p(vi,vj)为顶点vi和vj之间是否存在路径的判断?条件即若 vi/vj 之间的路径存在则关系 <vi,vj>属于R。
分类有：有向图，无向图。
（2）图的存储方式：
????????数组表示法，邻接表，十字链表，邻接多重表。
二.打印邻接矩阵：
首先得创建图，代码如下：
其中先定义一个结构体：
typedef char Vtype ;//图中顶点元素的类型
typedef int Wtype;//边上权的类型
#define MAXN 100
#define VERY_BIG 10000
typedef struct Graph
{
Vtype V[MAXN]; //一维数组来存储顶点的集合
Wtype A[MAXN][MAXN];//存储边上的权值 “邻接矩阵"
int vexnum;//图中有效顶点的个数
}Graph;
接下利用这个结构体创建图：
Graph * create_graph()
{
Vtype v;
int i,j;
Graph * g =malloc(sizeof(*g));
g->vexnum=0;
while(1)
{
scanf("%c",&v);
if(v == '#')
{
break;
}
g->V[g->vexnum++]=v;
}
getchar();
for(i=0;i<g->vexnum;i++)
{
for(j=0;j<g->vexnum;j++)
{
g->A[i][j]=VERY_BIG;
}
}
//输入边
//##0 -->输入结束
while(1)
{
Vtype start ,stop;//起点字符 终点字符
Wtype w;//权值 W
scanf("%c%c%d",&start,&stop,&w);
int start_index ,stop_index;//起点字符和终点字符在顶点数组v[]中的下标
getchar();
if(start == '#')
{
break;
}
start_index=find_index(g->V,g->vexnum,start);
stop_index =find_index(g->V,g->vexnum,stop);
if(start_index == -1 || stop_index == -1)
{
continue;
}
//把输入的边存储到“邻接矩阵”
g->A[start_index][stop_index]=w;
}
return g;
}
然后再建立一个函数来打印出邻接矩阵：
void printf__graph(Graph * g)
{
int i,j;
int start_index ,stop_index;
char start,stop;
for(i=0;i<g->vexnum;i++)
printf(" %3c",g->V[i]);
printf("\n");
for(i=0;i<g->vexnum;i++)
{
start=g->V[i];
printf("%c",start);
for(j=0;j<g->vexnum;j++)
{
stop=g->V[j];
start_index=find_index(g->V,g->vexnum,start);
stop_index =find_index(g->V,g->vexnum,stop);
if(g->A[start_index][stop_index]==10000)
{
printf(" %3c",'#');
}
else
printf(" %3d",g->A[start_index][stop_index]);
}
printf("\n");
}
}结构体中的数组V是用来存储节点的名字，而二维数组A是用来存储两点之间的距离，也就是边上的权。
效果如下：
注意的是我在代码中打印权的数组给初始化了。代码如下：
#define VERY_BIG 10000
for(i=0;i<g->vexnum;i++)
{
for(j=0;j<g->vexnum;j++)
{
g->A[i][j]=VERY_BIG;
}
}?方便后面给它修改成'#'。
三.遍历图：
遍历图的方法有两种，一种为深度优先搜索，另一种是广度优先搜索。
我用的是广度优先搜索。如果你们对深度优先搜索感兴趣的话，可以去了解下。
广度优先搜索的代码如下：
void BFStrevl(Graph *g)
{
int i,v0;
for(i=0;i<g->vexnum;i++)
visit[i]=0;
//创建一个队列
SqQueue *p=InitQueue(MAXN);
for(v0=0;v0<g->vexnum;v0++)
{
if(visit[v0]==1)
continue;
printf("%c",g->V[v0]);
visit[v0]=1;
Enqueue(p,v0);//让第一个被标识的节点入队
while(!QueueisEmpty(p))
{
int n,m;
DeQueue(p,&n);
for(m=find_next_vex(g, n,0);m>=0;m=find_next_vex(g, n, m+1))
{
if(visit[m]==1)//如果标记为1,则说明它已被访问,则继续找它的邻接点。
continue;
printf("%c",g->V[m]);
visit[m]=1;
Enqueue(p,m);
}
}
printf("\n");
}
}思路：从图中的某顶点(称为v0)出发 访问v0 并依次访问 v0的各邻接点（广度） 然后分别从这些被访问过得顶点出发 任然按照广度优先搜索的策略搜索其他节点 ?直到所有的节点被访问完。
该方法与树的遍历层次遍历有些相似。需要调用到队列。
队列代码如下：
#include <stdio.h>
#include <stdlib.h>
#include "SqQueue.h"
//创建一个队列
SqQueue * InitQueue(int maxl)
{
SqQueue * q =malloc(sizeof(*q));
q->data = malloc(maxl * sizeof(QElemType));
q->avail_len = 0;
q->front = 0;
q->rear= 0;
q->max_len = maxl;
}
void DestoryQueue(SqQueue *q)
{
if(q==NULL)
{
return ;
}
free(q->data);
free(q);
}
void ClearQueue(SqQueue *q)
{
if(q==NULL)
{
return ;
}
q->avail_len =0;
q->front =0;
q->rear =0;
}
//队为空 返回1
//队非空 返回0
int QueueisEmpty(SqQueue *q)
{
if(q->avail_len ==0 || q==NULL)
{
return 1;
}
return 0;
}
//返回队列的长度
int QueueLength(SqQueue *q)
{
if(q==NULL)
{
return 0;
}
return q->avail_len;
}
//入队一个元素 把一个元素加入到队列中
//返回值为 1 表示成功
//返回值为 0 表示失败
int Enqueue(SqQueue *q,QElemType x)
{
if(q==NULL || q->avail_len == q->max_len)
{
return 0;
}
q->data[q->rear++]=x;
q->rear=q->rear%q->max_len;
q->avail_len++;
return 1;
}
int DeQueue(SqQueue *q,QElemType *e)
{
if(q==NULL || q->avail_len == 0)
{
return 0;
}
*e = q->data[q->front++];
q->front = q->front % q->max_len;
q->avail_len --;
return 1;
}
int GetHead(SqQueue *q,QElemType *e)
{
if(q==NULL || q->avail_len == 0)
{
return 0;
}
*e = q->data[q->front];
return 1;
}
程序结构如下图：
注意调用队列程序是，需要一个.h文件：
#ifndef __SQQUEUE_H__
#define __SQQUEUE_H__
//#include "Graph.h"
typedef int QElemType;
typedef struct SqQueue
{
QElemType *data;// data = malloc() 动态数组
int max_len;// 队列中最多允许多少个元素
int front;// 队头
int rear ;// 队尾
int avail_len;// 队列中目前有多少个元素
//avail_len =0 ==> empty
//avail_len = max_len ==》满
//入队一个元素 avail_len ++
//出队一个元素 avail_len --
}SqQueue;
SqQueue * InitQueue(int maxl);
void DestoryQueue(SqQueue *q);
void ClearQueue(SqQueue *q);
int QueueisEmpty(SqQueue *q);
int QueueLength(SqQueue *q);
int Enqueue(SqQueue *q,QElemType x);
int DeQueue(SqQueue *q,QElemType *e);
int GetHead(SqQueue *q,QElemType *e);
#endif
?OK，以上就是本次博客的内容。可能有些地方不懂，我在接下来的代码里写些注释：
void BFSTraver(Graph *g)
{
int i,v0;
for(i=0;i<g->vexnum;i++)//标记所有顶点都没有被访问
{
visited[i]=0;
}
//初始化一个队列
SqQueue *q= InitQueue(MAXN);
//每一个节点都要广搜
for(v0=0;v0 < g->vexnum;v0++)
{
if(visited[v0]==1)
continue;
//访问v0 标记它
printf("%c",g->V[v0]);
visited[v0]=1;
//让v0入队
Enqueue(q,v0);//让顶点元素的小标入队
while(!QueueisEmpty(q))//队是否为空,为空说明已将v0的邻接点访问完
{
//出队 w
int w;
DeQueue(q,&w);//将出队元素的下标赋给w
//让出队元素的所有未被访问的邻接点入队（入队之间访问它）
int u;
for(u=find_next_vex(g, w,0);u>=0;u=find_next_vex(g, w, u+1))//通过出队元素的下
标找到附近的邻接
点
{
if(visited[u]==1)//如果标记为1,则说明它已被访问,则继续找它的邻接点。
continue;
printf("%c",g->V[u]);
visited[u]=1;
Enqueue(q,u);
}
printf("\n");
}
}
DestoryQueue(q);
}