圖的深度優先搜尋和廣度優先搜尋

此圖是以圖的鄰接表法作為儲存方式，對圖進行深度優先搜尋和廣度優先搜尋（均是非遞歸）

# include <stdio.h>

# include <stdlib.h>

# define True 1

# define False 0

# define Error -1

# define OK 1

# define MAX_VERTEX_NUM 20

int visited[MAX_VERTEX_NUM];

typedef char VertexData;

typedef enum{DG,DN,UDG,UDN} GraphKind;

typedef struct ArcNode{         //弧節點結構

 int adjvex;

 struct ArcNode *nextarc;

// OtherInfo info;

}ArcNode;

typedef struct VertexNode{       //表頭節點結構

 VertexData data;

 ArcNode *firstarc;

}VertexNode;

typedef struct {

 VertexNode vertex[MAX_VERTEX_NUM];

 int vexnum,arcnum;

 GraphKind kind;

}AdjList;

//**********************關于棧的知識*******************************

typedef struct node

{

 int num;

 struct node *next;

}LinkStackNode, *LinkStack;

int InitStack(LinkStack *S)           //初始化棧

{

 (*S) = (LinkStack)malloc(sizeof(LinkStackNode));

 (*S)->next = NULL;

 if ((*S) != NULL)

  return True;

 else

  return False;

}

int Push(LinkStack S, int x)         //進棧

{

 LinkStack temp;

 temp = (LinkStack)malloc(sizeof(LinkStackNode));

 if (temp == NULL)

  return False;

 temp->num = x;

 temp->next  = S->next;

 S->next = temp;

 return True;

}

int Pop(LinkStack S, int *x)        //出棧

{

 LinkStack temp;

 temp = S->next;

 if (temp == NULL)

  return False;

 *x = temp->num;

 S->next = temp->next;

 free(temp);

 return True;

}

int IsEmpty(LinkStack S)        //判斷棧是否為空

{

 if (S->next == NULL)

  return True;

 else

  return False;

}

//*************************************************************************

//****************************關于隊的知識**********************************************

typedef struct Node

{

 int data;

 struct Node *next;

}LinkQueueNode;

typedef struct

{

 LinkQueueNode *front;

 LinkQueueNode *rear;

}LinkQueue;

int InitQueue(LinkQueue *Q)                //   鍊隊列的初始化

{

 Q->front = (LinkQueueNode *)malloc(sizeof(LinkQueueNode));

 if (Q->front != NULL)

 {

  Q->rear = Q->front;

  Q->front->next = NULL;

  return (True);

 }

 else

  return False;

}

int EnterQueue(LinkQueue *Q, int x)             //鍊隊列入隊

{

 LinkQueueNode *NewNode;

 NewNode = (LinkQueueNode *)malloc(sizeof(LinkQueueNode));

 if (NewNode != NULL)

 {

  NewNode->data = x;

  NewNode->next = NULL;

  Q->rear->next = NewNode;

  Q->rear = NewNode;

  return True;

 }

 else

  return False;

}

int DeleteQueue(LinkQueue *Q, int *x)      //  鍊隊列出隊

{

 LinkQueueNode *p;

 if (Q->front == Q->rear)

  return False;

 p = Q->front->next;

 Q->front->next = p->next;

 if (Q->rear == p)

  Q->rear = Q->front;

 *x = p->data;

 free(p);

 return True;

}

int Empty(LinkQueue *Q)             //判斷鍊棧是否為空

{

 if (Q->front == Q->rear)

  return True;

 else

  return  False;

}

//*************************************************************************************

int FirstAdjVertex(AdjList *g, int v)         //求v的第一個鄰接點

{

 int w;

 ArcNode *p;

 p = g->vertex[v].firstarc;

 if (p == NULL)

  return Error;

 w = p->adjvex;

 return w;

}

int NextAdjVertex(AdjList *g, int v, int w)     //求v相對于w的下一個鄰接點

{

 int k;

 ArcNode *p;

 p = g->vertex[v].firstarc;

 while (p->adjvex != w)

 {

  p = p->nextarc;

 }

 p = p->nextarc;

 if (p == NULL)

  return Error;

 else

 {

  k = p->adjvex;

  return k;

 }

}

int LocateVertex(AdjList *g, VertexData v)         //求頂點位置函數

{

 int j = Error,k;

 for (k = 0; k < g->vexnum ; k++)

  if (g->vertex[k].data  == v)

  {

   j = k;break;

  }

 return j;

}

void Crtadjlist(AdjList *g)            //建立鄰接連結清單

{

 int n,e,i,j,k;

 char vt,vh;

 ArcNode *p;

 printf("請輸入圖的頂點個數和弧的個數\n");

 scanf("%d%d", &n, &e);

 g->vexnum  = n;

 g->arcnum  = e;

 printf("請輸入頂點資訊\n");

 getchar();

 for (i = 0; i < n; i++)

 {

  scanf("%c", &(g->vertex[i].data));

  g->vertex[i].firstarc = NULL;

 }

 printf("請輸入弧的兩個頂點\n");

 for (k = 0; k < e; k++)

 {

  getchar(); 

  scanf("%c%c",&vt,&vh);

  i = LocateVertex(g,vt);

  j = LocateVertex(g,vh);

  p = (ArcNode *)malloc(sizeof(ArcNode));

  p->adjvex = j;

  p->nextarc = g->vertex[i].firstarc;

  g->vertex[i].firstarc = p;

 }

}

void DepthFirstSearch(AdjList *g, int v0)  //深度優先搜尋

{

 LinkStackNode *S;

 int v, w;

 InitStack(&S);

 Push(S, v0);

 while ( !IsEmpty(S))

 {

  Pop(S, &v);

  if (!visited[v])

  {

   printf("%c ",g->vertex[v].data );

   visited[v] = True;

   w = FirstAdjVertex(g,v);

   while (w != -1)

   {

    if (!visited[w])

     Push(S, w);

    w = NextAdjVertex(g,v,w);

   }

  }

 }

}

void TraverseGraph(AdjList *g)      //深搜

{

 int vi;

 for (vi = 0; vi < g->vexnum ; vi++)

  visited[vi] = False;               //初始化标志數組

 for (vi = 0; vi < g->vexnum; vi++)

  if (!visited[vi])

   DepthFirstSearch(g,vi);

}

void BreadthFirstSearch(AdjList *g, int v0)       // 廣度優先搜尋

{

 LinkQueue Q;

 int v, w;

 printf("%c ", g->vertex[v0].data);

 visited[v0] = True;

 InitQueue(&Q);

 EnterQueue(&Q,v0);

 while (!Empty(&Q))

 {

  DeleteQueue(&Q, &v);

  w = FirstAdjVertex(g, v);

  while (w != -1)

  {

   if (!visited[w])

   {

    printf("%c ",g->vertex[w].data);

    visited[w] = True;

    EnterQueue(&Q,w);

   }

   w = NextAdjVertex(g,v,w);

  }

 }

}

void BreadthTraverseGraph(AdjList *g)      //廣搜

{

 int vi;

 for (vi = 0; vi < g->vexnum ; vi++)

  visited[vi] = False;               //初始化标志數組

 for (vi = 0; vi < g->vexnum; vi++)

  if (!visited[vi])

   BreadthFirstSearch(g,vi);

}

int main(void)

{

 AdjList g;

 Crtadjlist (&g);

 printf("深度優先搜尋周遊輸出\n");

 TraverseGraph(&g);

 printf("\n廣度優先搜尋周遊輸出\n");

 BreadthTraverseGraph(&g);

 printf("\n");

 return 0;

}