#include <stdio.h>

struct node                       /* 图顶点结构定义     */

{

   int vertex                    /* 顶点数据信息       */

   struct node *nextnode         /* 指下一顶点的指标   */

}

typedef struct node *graph       /* 图形的结构新型态   */

struct node head[9]              /* 图形顶点数组       */

int visited[9]                   /* 遍历标记数组       */

/********************根据已有的信息建立邻接表********************/

void creategraph(int node[20][2],int num)/*num指的是图的边数*/

{

   graph newnode                 /*指向新节点的指针定义*/

   graph ptr

   int from                      /* 边的起点          */

   int to                        /* 边的终点          */

   int i

   for ( i = 0 i < num i++ )    /* 读取边线信息，插入邻接表*/

   {

      from = node[i][0]         /*    边线的起点            */

      to = node[i][1]           /*   边线的终点             */

   /* 建立新顶点 */

      newnode = ( graph ) malloc(sizeof(struct node))

      newnode->vertex = to        /* 建立顶点内容       */

      newnode->nextnode = NULL    /* 设定指标初值       */

      ptr = &(head[from])         /* 顶点位置           */

      while ( ptr->nextnode != NULL ) /* 遍历至链表尾   */

         ptr = ptr->nextnode     /* 下一个顶点         */

      ptr->nextnode = newnode    /* 插入节点        */

   }

}

/**********************  图的深度优先搜寻法********************/

void dfs(int current)

{

   graph ptr

   visited[current] = 1          /* 记录已遍历过       */

   printf("vertex[%d]\n",current)   /* 输出遍历顶点值     */

   ptr = head[current].nextnode  /* 顶点位置           */

   while ( ptr != NULL )          /* 遍历至链表尾       */

   {

      if ( visited[ptr->vertex] == 0 )  /* 如过没遍历过 */

         dfs(ptr->vertex)              /* 递回遍历呼叫 */

      ptr = ptr->nextnode              /* 下一个顶点   */

   }

}

/****************************** 主程序******************************/

int main()

{

   graph ptr

   int node[20][2] = { {1, 2}, {2, 1},  /* 边线数组     */

                       {1, 3}, {3, 1},

                       {1, 4}, {4, 1},

                       {2, 5}, {5, 2},

                       {2, 6}, {6, 2},

                       {3, 7}, {7, 3},

                       {4, 7}, {4, 4},

                       {5, 8}, {8, 5},

                       {6, 7}, {7, 6},

                       {7, 8}, {8, 7} }

   int i

   //clrscr()

   for ( i = 1 i <= 8 i++ )      /*   顶点数组初始化  */

   {

      head[i].vertex = i         /*    设定顶点值      */

      head[i].nextnode = NULL    /*       指针为空     */

      visited[i] = 0             /* 设定遍历初始标志   */

   }

   creategraph(node,20)          /*    建立邻接表      */

   printf("Content of the gragh's ADlist is:\n")

   for ( i = 1 i <= 8 i++ )

   {

      printf("vertex%d ->",head[i].vertex) /* 顶点值    */

      ptr = head[i].nextnode             /* 顶点位置   */

      while ( ptr != NULL )       /* 遍历至链表尾       */

      {

         printf(" %d ",ptr->vertex)  /* 印出顶点内容   */

         ptr = ptr->nextnode         /* 下一个顶点     */

      }

      printf("\n")               /*   换行             */

   }

   printf("\nThe end of the dfs are:\n")

   dfs(1)                        /* 打印输出遍历过程   */

   printf("\n")                  /* 换行               */

   puts(" Press any key to quit...")

  // getch()

}

（2） 从指定顶点出发进行深度优先搜索遍历。

（3） 从指定顶点出发进行广度优先搜索遍历。

#include"stdio.h"

#include"string.h"

#include"stdlib.h"

#include"math.h"

#define MAX_INT 1000

#define MAX_VERTEX_NUM 20

#define MAX_QUEUE_NUMBER 20

typedef struct ArcNode

{

int adjvex

double adj

struct ArcNode *nextarc

}ArcNode

typedef struct VexNode

{

char szName[40]

ArcNode *firstarc

}VexNode,AdjList[MAX_VERTEX_NUM]

typedef struct

{

AdjList vexs

int vexnum,arcnum

}Net

//定义队列

typedef struct{

int *elem

int front, rear

}Queue

void InitQueue(Queue &Q)

{

Q.elem = new int[MAX_QUEUE_NUMBER]

Q.front = Q.rear = 0

}

int EmptyQueue(Queue Q)

{

if(Q.front==Q.rear)

return 0

else

return 1

}

void DestroyQueue(Queue &Q){

delete []Q.elem

Q.front = Q.rear = 0

}

void EnterQueue(Queue &Q, int e)

{

if((Q.rear + 1)%MAX_QUEUE_NUMBER != Q.front)

Q.elem[Q.rear ] = e

else

printf("队列满!\n")

Q.rear = (Q.rear + 1)%MAX_QUEUE_NUMBER

}

void LeaveQueue(Queue &Q, int &e)

{

if(Q.rear != Q.front)

e = Q.elem[Q.front]

else

printf("队列空!\n")

Q.front = (Q.front+1)%MAX_QUEUE_NUMBER

}

int LocateVex(Net ga,char *name)

{

int i

for(i=0i<ga.vexnumi++)

if(strcmp(name,ga.vexs[i].szName)==0)

return i

return -1

}

void crt_net(Net &ga)

{

ArcNode *p

char name1[40],name2[40]

int i,j,k

double w

printf("请输入顶点数和弧数：")

scanf("%d%d",&ga.vexnum,&ga.arcnum)

printf("请依次输入顶点名：\n")

for(i=0i<ga.vexnumi++)

{

scanf("%s",ga.vexs[i].szName)

ga.vexs[i].firstarc=NULL

}

for(k=0k<ga.arcnumk++)

{

printf("请输入相邻的两个定点和权值：")

scanf("%s%s%lf",name1,name2,&w)

i=LocateVex(ga,name1)

j=LocateVex(ga,name2)

p=new ArcNode

p->adjvex=j

p->adj=w

p->nextarc=ga.vexs[i].firstarc

ga.vexs[i].firstarc=p

}

}

void DFS(Net ga,char *name,int *visited)

{

int v,w

ArcNode *p

v=LocateVex(ga,name)

visited[v]=1

printf("%s ",ga.vexs[v].szName)

p=ga.vexs[v].firstarc

while(p!=NULL)

{

w=p->adjvex

if(visited[w]==0)

DFS(ga,ga.vexs[w].szName,visited)

p=p->nextarc

}

}

void DFSTravel(Net ga,char *name)

{

int v,k=0

int visited[20]

for(v=0v<ga.vexnumv++)

visited[v]=0

for(v=LocateVex(ga,name)k!=2v=(v+1)%(ga.vexnum-1))

{

if(v+1==LocateVex(ga,name))

k++

if(visited[v]==0)

DFS(ga,ga.vexs[v].szName,visited)

}

}

void BFSTravel(Net ga,char *name)

{

ArcNode *p

int v,w,u,k=0

Queue Q

int visited[20]

for(v=0v<ga.vexnumv++)

visited[v]=0

InitQueue(Q)

for(v=LocateVex(ga,name)k!=2v=(v+1)%(ga.vexnum-1))

{

if(v+1==LocateVex(ga,name))

k++

if(visited[v]==0)

{

visited[v]=1

printf("%s ",ga.vexs[v].szName)

EnterQueue(Q,v)

while(EmptyQueue(Q)!=0)

{

LeaveQueue(Q,u)

p=ga.vexs[u].firstarc

while(p!=NULL)

{

w=p->adjvex

if(visited[w]==0)

{

printf("%s ",ga.vexs[w].szName)

visited[w]=1

EnterQueue(Q,w)

}

p=p->nextarc

}

}

}

}

}

void main()

{

char name[40]

Net ga

crt_net(ga)

printf("请输入深度优先遍历开始点的名：")

scanf("%s",name)

printf("深度优先遍历：")

DFSTravel(ga,name)

printf("\n")

printf("请输入广度优先遍历开始点的名：")

scanf("%s",name)

printf("广度优先遍历：")

BFSTravel(ga,name)

printf("\n")

}

/*编写无向图的邻接矩阵类AdjMWGraph,实现无向图的广度遍历和深度遍历。

其中，图中顶点数据类型为字符。Input第一行图中顶点的个数n(4<=n<=26)

第二行是图中边的条数m(3<=m<=351) 第三行是顶点信息(全为大写字母)

后面的输入数据是依附于一条边的两个顶点，有多少条边，就输入多少组信息。

注意：根结点都为A；并且所给字符连续，也就是说A B C D ……。

Output广度优先搜索序列。 深度优先搜索序列。

Sample Input

7

6

A B C D E F G

A B

A C

B D

B E

C F

C G

Sample Output

A B C D E F G

A B D E C F G

*/

#include <stdio.h>#include <stdlib.h>

unsigned char arrMap[26][26] = {0}

int nV = 0

void deep_prior_scan(int j)

void spread_prior_scan(int j)

void GetResult()

{

int nL = 0//存储边数

int i

char arrV[26] = {0}

char temp, pairV[2]

//输入过程

printf("\n请输入顶点数：")

scanf("%d", &nV)

printf("\n请输入边数:")

scanf("%d", &nL)

printf("\n请依次输入顶点：\n")

for (i = 0, temp = 'A'i <nV)

{

temp = getchar()

if (temp >= 'A' &&temp <= 'Z')

{

arrV[i++] = temp

}

}

printf("\n请依次输入边:\n")

for (i = 0i <nL*2)

{

temp = getchar()

if (temp >= 'A' &&temp <= 'Z')

{

pairV[i%2] = temp

if (i%2 == 1)

{

arrMap[pairV[0] - 'A'][pairV[1] - 'A'] = 1

}

++i

}

}

//printf("\n广度优先遍历：\n")

//spread_prior_scan(0)

//printf("\n")

printf("\n深度优先遍历：\n")

deep_prior_scan(0)

printf("\n")

}

int main()

{

GetResult()

system("pause")

return 0

}

void deep_prior_scan(int j)

{

int i

printf("%c ", j + 'A')

for (i = 0i <nVi++)

{

if (arrMap[j][i] != 0)

{

arrMap[j][i] = 0

deep_prior_scan(i)

}

}

}

void spread_prior_scan(int j)

{

int i

if (j == 0)

{

printf("\nA ")

}

if (j >= 26)

{

printf("\nj=%d\n", j)

}

for (i = 0i <nVi++)

{

if (arrMap[j][i] != 0)

{

printf("%c ", i + 'A')

}

}

for (i = 0i <nVi++)

{

if (arrMap[j][i] != 0)

{

arrMap[j][i] = 0

spread_prior_scan(i)

}

}

}

因为懒得复制数组，所以两种遍历方法要分开运行，你可以通过打开和关闭对相应函数的注释来得到两次的结果