分享图的邻接表深度和广度优先搜索~
感觉代码写得比较长~不过还是整理出来了~仅供参考~~~
程序代码：#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#define MAX 20 //最大边数
#define HEAD_NUM 8 //顶点实际数量
#define LEN sizeof (Node)
#define LEN_Qnode sizeof (Qnode)
#define LEN_LinkQnode sizeof (LinkQnode)
typedef int ElemType;
typedef struct Node
{
ElemType vertes; //顶点信息
struct Node* next; //下一个顶点坐标信息
}Node,*PNode;
typedef struct Graph //图的顶点数组
{
PNode head; //头顶点信息
ElemType vertrs; //该顶点信息
int visit; //该点是否被遍历
}Graph;
typedef struct Data
{
int n; //顶点数量
int e; //边数
int node[MAX][2]; //邻接表信息
Graph graph[MAX]; //邻接表
}Data;
typedef struct Queue //队列
{
ElemType current; //记录顶点信息
struct Queue* next; //队列指针
}Qnode,*PQnode;
typedef struct LinkQueue
{
PQnode front; //队头指针
PQnode rear; //队尾指针
}LinkQnode,*PLinkQnode;
void Creat_Init(Data* G); //初始化图的信息
void Creat_Node(PNode* p); //建立新顶点
void Creat_Graph(Data* G); //建立邻接表
void Print_Graph(Data* G); //输出邻接表信息
void DFS_Search(Graph graph[],int current); //图的深度搜索
void BFS_Search(Graph graph[],int n); //图的广度搜索
void Empty_Visit(Data* G); //重置遍历状态(用于重新遍历)
void Del_Graph(Data* G); //释放邻接表
void Creat_Queue(PLinkQnode* p); //新建一个队列
void Creat_Node_Queue(PQnode* p); //创建一个队列节点
void Insert_Queue(PLinkQnode p,ElemType n); //入队
void Pop_Queue(PLinkQnode p); //出队
void Del_Queue(PLinkQnode* p); //清空队列
int Empty_Queue(PLinkQnode p); //判断队空
int main()
{
Data G=
{
0,0,
{
{1,2},{2,1},
{1,4},{4,1},
{3,4},{4,3},
{1,8},{8,1},
{2,6},{6,2},
{4,5},{5,4},
{5,6},{6,5},
{6,7},{7,6},
{6,8},{8,6},
},
};
Creat_Init(&G);
Creat_Graph(&G);
Print_Graph(&G);
puts("\n图的深度搜索结果为:\n");
printf("搜索起点:%d\n",1);
DFS_Search(G.graph,1); //深度搜索
Empty_Visit(&G); //重置遍历状态
puts("\n图的广度搜索结果为:\n");
BFS_Search(G.graph,1);
Del_Graph(&G); //释放邻接表
return 0;
}
void Creat_Node(PNode* p) //建立新顶点
{
*p=(PNode)malloc(LEN);
assert(*p!=NULL);
memset(*p,0,LEN);
}
void Creat_Init(Data* G) //初始化图的信息
{
int i=0;
memset(G->graph,0,sizeof(G->graph));
G->n=HEAD_NUM;
G->e=MAX;
for (i=0;i<=G->n;++i)
{
Creat_Node(&G->graph[i].head); //创建头顶点信息
G->graph[i].vertrs=i;
}
}
void Creat_Graph(Data* G)
{
PNode new_node=NULL; //图的遍历指针
PNode ptr=NULL;
int i=0;
int from=0; //边的起点
int to=0; //边的终点
for (i=0;i<G->e;++i)
{
from=G->node[i][0];
to=G->node[i][1];
Creat_Node(&new_node); //创建顶点坐标
new_node->vertes=to; //建立邻接表
ptr=G->graph[from].head;
while (ptr->next!=NULL)
ptr=ptr->next;
ptr->next=new_node; //插入新节点
}
}
void Print_Graph(Data* G) //输出邻接表信息
{
PNode ptr=NULL;
int i=0;
for (i=1;i<=G->n;++i)
{
ptr=G->graph[i].head->next;
printf("vertex[%d]->",G->graph[i].vertrs);
while (ptr)
{
printf("%-3d",ptr->vertes);
ptr=ptr->next;
}
puts("");
}
}
void DFS_Search(Graph graph[],int current) //图的深度搜索
{
PNode ptr=graph[current].head->next; //遍历顶点指针
graph[current].visit=1;
printf("vertex[%d]\n",graph[current].vertrs);
while (ptr!=NULL)
{
if (graph[ptr->vertes].visit==0) //递归遍历呼叫
DFS_Search(graph,ptr->vertes);
ptr=ptr->next;
}
}
void BFS_Search(Graph graph[],int n) //图的广度搜索
{
PNode ptr=NULL; //遍历顶点指针
PLinkQnode queue=NULL;
int count[MAX]={0}; //图的步长标记
int step=1; //图的步长
Creat_Queue(&queue);
printf("搜索起点:%d\n",n);
if (graph[n].head!=NULL)
{
Insert_Queue(queue,graph[n].vertrs); //第一个顶点入队
printf("步长->%-2d vertex[%d]\n",step,graph[n].vertrs);
graph[n].visit=1;
count[n]=step;
}
while (!Empty_Queue(queue))
{
ptr=graph[queue->front->next->current].head->next;
if (count[queue->front->next->current]==step)
++step;
while (ptr!=NULL)
{
if (graph[ptr->vertes].visit==0)
{
Insert_Queue(queue,graph[ptr->vertes].vertrs);
printf("步长->%-2d vertex[%d]\n",step,graph[ptr->vertes].vertrs);
graph[ptr->vertes].visit=1;
count[graph[ptr->vertes].vertrs]=step;
}
ptr=ptr->next;
}
Pop_Queue(queue);
}
Del_Queue(&queue);
}
void Empty_Visit(Data* G) //清空遍历信息
{
int i=0;
for (i=1;i<=G->n;++i)
G->graph[i].visit=0;
}
void Del_Graph(Data* G) //释放邻接表
{
PNode t1=G->graph[0].head;
PNode t2=t1;
int i=0;
for (i=0;i<=G->n;t1=t2=G->graph[++i].head)
{
if (G->graph[i].head==NULL)
continue;
while (t1=t2)
{
t2=t1->next;
free(t1);
}
G->graph[i].head=NULL;
}
}
void Creat_Queue(PLinkQnode* p) //新建一个队列
{
*p=(PLinkQnode)malloc(LEN_LinkQnode);
assert(*p!=NULL);
memset(*p,0,LEN_LinkQnode);
(*p)->front=(*p)->rear=(PQnode)malloc(LEN_Qnode);
assert((*p)->front!=NULL);
memset((*p)->front,0,LEN_Qnode);
}
void Creat_Node_Queue(PQnode* p) //创建一个队列节点
{
*p=(PQnode)malloc(LEN_Qnode);
assert(*p!=NULL);
memset(*p,0,LEN_Qnode);
}
void Insert_Queue(PLinkQnode p,ElemType n) //入队
{
PQnode t=NULL;
Creat_Node_Queue(&t);
t->current=n;
p->rear=p->rear->next=t;
}
void Pop_Queue(PLinkQnode p) //出队
{
PQnode t1=p->front;
if (Empty_Queue(p))
return ;
p->front=p->front->next;
free(t1);
t1=p->front->next;
memset(p->front,0,LEN_Qnode);
p->front->next=t1;
}
void Del_Queue(PLinkQnode* p) //清空队列
{
PQnode t=(*p)->front;
while (!Empty_Queue(*p))
Pop_Queue(*p);
free(*p);
*p=NULL;
}
int Empty_Queue(PLinkQnode p) //判断队空
{
return p->front==p->rear;
}
[此贴子已经被作者于2017-4-23 06:01编辑过]
~大一时要用链表写信息管理系统
大二就要用数据结构写城市规划管理系统了
就是现在感觉插入和删除顶点和边调整比较麻烦~不过感觉写泛型要和图的结构框架要匹配才行~所以和上楼回复这个感觉的确比较难找到现成的通用性较强的代码~~
~~~