鄰接表表示的圖的深度優先搜索和廣度優先搜索程序

鄰接表表示的圖的深度優先搜索和廣度優先搜索程序

#include <stdioh>
#define maxvertexnum
#define queuesize
#define null

typedef struct{
　　int frontrearcountdata[queuesize];
　}cirqueue;//循環隊列結構定義

typedef int vertextype;//為了簡單設圖中結點的數據為整型
typedef struct node{
　　int adjvex;//存放鄰接點序號
　　struct node *next;//指向下一個邊結點
　}edgenode;//圖的鄰接表的邊結點定義

typedef struct vnode{
　　vertextype vertex;//頂點數據域
　　edgenode *firstedge;//指向第一個邊結點
　}vertexnode;//圖的鄰接表表示的頂點結點定義

typedef vertexnode adjlist[maxvertexnum];//用向量定義圖的鄰接表表示的頂點表

typedef struct{
　　adjlist adjlist;
　　int n;//圖的頂點數
　　int e;//圖的邊數
　}algraph;//定義圖的鄰接表

typedef enum{FALSETRUE}boolean;
boolean visited[maxvertexnum];//保存訪問信息的布爾向量

main()//主函數
　{//建立圖g並進行深度優先搜索和廣度優先搜索
　　algraph *g;
　　g=(algraph*)malloc(sizeof(algraph));//申請圖g的鄰接表空間
　　createalgraph(g);//建立圖g的鄰接表表示
　　printf(the dfs is:);/
　　dfstraverse(g);//對圖g進行深度優先搜索並打印搜索序列
　　printf(the bfs is:);
　　bfstraverse(g);//對圖g進行廣度優先搜索並打印搜索序列　
　}

createalgraph(algraph *g)
　{//建立圖g的鄰接表表示
　　int ijk;
　　int flag;
　　edgenode *s;
　　printf(\ncreat:\n)//選擇建立有向圖或無向圖
　　printf(digraph\n);
　　printf(undigraph\n);
　　scanf(%d&flag);
　　printf(input ne\n);
　　scanf(%d%d&g>n&g>e);//輸入圖g的頂點數和邊數
　　printf(input nodes:\n);
　　for(i=;i<g>n;i++){//構造一個只含n個頂點邊數為的圖
　　　　scanf(%d&(g>adjlist[i]vertex));
　　　　　//輸入頂點的數據域（為了簡單起見輸入為整數）
　　　　g>adjlist[i]firstedge=null;//將頂點結點的firstedge域置為空
　　　}//end for
　　for(k=;k<g>e;k++){
　　　　printf(input ij(~n):\n);
　　　　scanf(%d%d&i&j);//輸入對應於一條邊的頂點序號序偶對要求頂點序號為~n
　　　　s=(edgenode *)malloc(sizeof(edgenode));//申請一個邊結點*s
　　　　s>adjvex=j;//將序號j放入邊結點*s的adjvex域
　　　　s>next=g>adjlist[i]firstedge;
　　　　　//將邊結點*s作為第一個鄰接點插入到序號為i的頂點的邊表中
　　　　g>adjlist[i]firstedge=s;
　　　　if (flag){//若要建立無向圖
　　　　　　s=(edgenode *)malloc(sizeof(edgenode));申請一個邊結點*s
　　　　　　s>adjvex=i;//將序號i放入邊結點*s的adjvex域
　　　　　　s>next=g>adjlist[j]firstedge;
　　　　　　　//將邊結點*s作為第一個鄰接點插入到序號為j的頂點的邊表中
　　　　　　g>adjlist[j]firstedge=s;
　　　　　}//end of if
　　　}//end of for
　}//end of creatalgraph

dfs(algraph *gint i)
　{//對圖g進行以序號為i的頂點作為出發點深度優先搜索
　　edgenode *p;
　　printf(visit vertex:%dg>adjlist[i]vertex);//打印序號為i的頂點信息
　　visited[i]=TRUE;//將序號為i的頂點設置已訪問過標記
　　p=g>adjlist[i]firstedge;//設置尋找序號為i的第一個未訪問過鄰接點的掃描指針
　　while(p){
　　　　if (!visited[p>adjvex])//若*p邊結點對應頂點（假設序號為j）未訪問過
　　　　　　dfs(gp>adjvex);//對圖g進行以序號為j的頂點作為出發點進行深度優先搜索
　　　　p=p>next;//p順著邊表next指針往後繼續尋找
　　　}//end of while
　}//end of dfs

dfstraverse(algraph *g)
　{//對以鄰接表表示的圖g進行深度優先搜索
　　int i;
　　for(i=;i<g>n;i++)//將圖g的所有頂點設置未訪問過標記
　　　　visited[i]=FALSE;
　　for(i=;i<g>n;i++)//對圖g調用dfs函數進行深度優先搜索
　　　if(!visited[i])
　　　　dfs(gi);
　　printf(\n);
　}//end of dfstraverse

bfs(algraph *gint k)
　{//對圖g進行以序號為k的頂點作為出發點廣度優先搜索
　　int ij;
　　cirqueue *q;//設置循環隊列指針
　　edgenode *p;
　　q=(cirqueue *)malloc(sizeof(cirqueue));//申請循環隊列空間
　　q>rear=q>front=q>count=;//將循環隊列置為空隊
　　printf(visit vertex:%dg>adjlist[k]vertex);
　　visited[k]=TRUE;//將序號為k的頂點設置為已訪問過
　　q>data[q>rear]=k;q>rear=(q>rear+)%queuesize;q>count++;//將頂點序號k入隊
　　while(q>count){//當隊列非空時做以下操作
　　　　i=q>data[q>front];q>front=(q>front+)%queuesize;q>count;//將隊首元素i出隊
　　　　p=g>adjlist[i]firstedge;//設置尋找序號為i頂點的未訪問過鄰接點的掃描指針p
　　　　while (p){//當*p不為空時做以下操作
　　　　　　if(!visited[p>adjvex]){//若*p邊結點對應頂點（假設序號為j）未訪問過
　　　　　　　　printf(visit vertex:%dg>adjlist[p>adjvex]vertex);
　　　　　　　　　　//訪問序號為j的頂點
　　　　　　　　visited[p>adjvex]=TRUE;//設置已訪問過標記
　　　　　　　　q>data[q>rear]=p>adjvex;q>rear=(q>rear+)%queuesize;q>count++;
　　　　　　　　　　//將序號為j的頂點入隊
　　　　　　　}//end of if
　　　　　　p=p>next;//p順著邊表next指針往後繼續尋找
　　　　　}//end of while
　　　}//end of while
　}//end of bfs

bfstraverse(algraph *g)
　{//對以鄰接表表示的圖g進行廣度優先搜索
　　int i;
　　for(i=;i<g>n;i++)//將圖g的所有頂點設置未訪問過標記
　　　visited[i]=FALSE;
　　for(i=;i<g>n;i++)//對圖g調用bfs函數進行廣度優先搜索
　　　if(!visited[i])
　　　　bfs(gi);
　　printf(\n);
　}

From:http://tw.wingwit.com/Article/program/sjjg/201311/23272.html