熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

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

2013-11-15 15:20:42  來源: 數據結構 

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


#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
  • 上一篇文章:

  • 下一篇文章:
  • 推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.