邻接表的图遍历
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0#define MAXSIZE 9 /* 存儲空間初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITY 65535typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼,如OK等 */
typedef int Boolean; /* Boolean是布爾類型,其值是TRUE或FALSE */typedef char VertexType; /* 頂點類型應由用戶定義 */
typedef int EdgeType; /* 邊上的權(quán)值類型應由用戶定義 *//* 鄰接矩陣結(jié)構(gòu) */
typedef struct
{VertexType vexs[MAXVEX]; /* 頂點表 */EdgeType arc[MAXVEX][MAXVEX];/* 鄰接矩陣,可看作邊表 */int numVertexes, numEdges; /* 圖中當前的頂點數(shù)和邊數(shù) */
}MGraph;/* 鄰接表結(jié)構(gòu)****************** */
typedef struct EdgeNode /* 邊表結(jié)點 */
{int adjvex; /* 鄰接點域,存儲該頂點對應的下標 */int weight; /* 用于存儲權(quán)值,對于非網(wǎng)圖可以不需要 */struct EdgeNode *next; /* 鏈域,指向下一個鄰接點 */
}EdgeNode;typedef struct VertexNode /* 頂點表結(jié)點 */
{int in; /* 頂點入度 */char data; /* 頂點域,存儲頂點信息 */EdgeNode *firstedge;/* 邊表頭指針 */
}VertexNode, AdjList[MAXVEX];typedef struct
{AdjList adjList; int numVertexes,numEdges; /* 圖中當前頂點數(shù)和邊數(shù) */
}graphAdjList,*GraphAdjList;
/* **************************** *//* 用到的隊列結(jié)構(gòu)與函數(shù)********************************** */
/* 循環(huán)隊列的順序存儲結(jié)構(gòu) */
typedef struct
{int data[MAXSIZE];int front; /* 頭指針 */int rear; /* 尾指針,若隊列不空,指向隊列尾元素的下一個位置 */
}Queue;/* 初始化一個空隊列Q */
Status InitQueue(Queue *Q)
{Q->front=0;Q->rear=0;return OK;
}/* 若隊列Q為空隊列,則返回TRUE,否則返回FALSE */
Status QueueEmpty(Queue Q)
{ if(Q.front==Q.rear) /* 隊列空的標志 */return TRUE;elsereturn FALSE;
}/* 若隊列未滿,則插入元素e為Q新的隊尾元素 */
Status EnQueue(Queue *Q,int e)
{if ((Q->rear+1)%MAXSIZE == Q->front) /* 隊列滿的判斷 */return ERROR;Q->data[Q->rear]=e; /* 將元素e賦值給隊尾 */Q->rear=(Q->rear+1)%MAXSIZE;/* rear指針向后移一位置, *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK;
}/* 若隊列不空,則刪除Q中隊頭元素,用e返回其值 */
Status DeQueue(Queue *Q,int *e)
{if (Q->front == Q->rear) /* 隊列空的判斷 */return ERROR;*e=Q->data[Q->front]; /* 將隊頭元素賦值給e */Q->front=(Q->front+1)%MAXSIZE; /* front指針向后移一位置, *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK;
}
/* ****************************************************** */void CreateMGraph(MGraph *G)
{int i, j;G->numEdges=15;G->numVertexes=9;/* 讀入頂點信息,建立頂點表 */ G->vexs[0]='A';G->vexs[1]='B';G->vexs[2]='C';G->vexs[3]='D';G->vexs[4]='E';G->vexs[5]='F';G->vexs[6]='G';G->vexs[7]='H';G->vexs[8]='I';for (i = 0; i < G->numVertexes; i++)/* 初始化圖 */{for ( j = 0; j < G->numVertexes; j++){G->arc[i][j]=0;}}G->arc[0][1]=1;G->arc[0][5]=1;G->arc[1][2]=1; G->arc[1][8]=1; G->arc[1][6]=1; G->arc[2][3]=1; G->arc[2][8]=1; G->arc[3][4]=1;G->arc[3][7]=1;G->arc[3][6]=1;G->arc[3][8]=1;G->arc[4][5]=1;G->arc[4][7]=1;G->arc[5][6]=1; G->arc[6][7]=1; for(i = 0; i < G->numVertexes; i++){for(j = i; j < G->numVertexes; j++){G->arc[j][i] =G->arc[i][j];}}}/* 利用鄰接矩陣構(gòu)建鄰接表 */
void CreateALGraph(MGraph G,GraphAdjList *GL)
{int i,j;EdgeNode *e;*GL = (GraphAdjList)malloc(sizeof(graphAdjList));(*GL)->numVertexes=G.numVertexes;(*GL)->numEdges=G.numEdges;for(i= 0;i <G.numVertexes;i++) /* 讀入頂點信息,建立頂點表 */ {(*GL)->adjList[i].in=0;(*GL)->adjList[i].data=G.vexs[i];(*GL)->adjList[i].firstedge=NULL; /* 將邊表置為空表 */}for(i=0;i<G.numVertexes;i++) /* 建立邊表 */{ for(j=0;j<G.numVertexes;j++){if (G.arc[i][j]==1){e=(EdgeNode *)malloc(sizeof(EdgeNode));e->adjvex=j; /* 鄰接序號為j */ e->next=(*GL)->adjList[i].firstedge; /* 將當前頂點上的指向的結(jié)點指針賦值給e */(*GL)->adjList[i].firstedge=e; /* 將當前頂點的指針指向e */ (*GL)->adjList[j].in++;}}}}Boolean visited[MAXSIZE]; /* 訪問標志的數(shù)組 *//* 鄰接表的深度優(yōu)先遞歸算法 */
void DFS(GraphAdjList GL, int i)
{EdgeNode *p;visited[i] = TRUE;printf("%c ",GL->adjList[i].data);/* 打印頂點,也可以其它操作 */p = GL->adjList[i].firstedge;while(p){if(!visited[p->adjvex])DFS(GL, p->adjvex);/* 對為訪問的鄰接頂點遞歸調(diào)用 */p = p->next;}
}/* 鄰接表的深度遍歷操作 */
void DFSTraverse(GraphAdjList GL)
{int i;for(i = 0; i < GL->numVertexes; i++)visited[i] = FALSE; /* 初始所有頂點狀態(tài)都是未訪問過狀態(tài) */for(i = 0; i < GL->numVertexes; i++)if(!visited[i]) /* 對未訪問過的頂點調(diào)用DFS,若是連通圖,只會執(zhí)行一次 */ DFS(GL, i);
}/* 鄰接表的廣度遍歷算法 */
void BFSTraverse(GraphAdjList GL)
{int i;EdgeNode *p;Queue Q;for(i = 0; i < GL->numVertexes; i++)visited[i] = FALSE;InitQueue(&Q);for(i = 0; i < GL->numVertexes; i++){if (!visited[i]){visited[i]=TRUE;printf("%c ",GL->adjList[i].data);/* 打印頂點,也可以其它操作 */EnQueue(&Q,i);while(!QueueEmpty(Q)){DeQueue(&Q,&i);p = GL->adjList[i].firstedge; /* 找到當前頂點的邊表鏈表頭指針 */while(p){if(!visited[p->adjvex]) /* 若此頂點未被訪問 */{visited[p->adjvex]=TRUE;printf("%c ",GL->adjList[p->adjvex].data);EnQueue(&Q,p->adjvex); /* 將此頂點入隊列 */}p = p->next; /* 指針指向下一個鄰接點 */}}}}
}int main(void)
{ MGraph G; GraphAdjList GL; CreateMGraph(&G);CreateALGraph(G,&GL);printf("\n深度遍歷:");DFSTraverse(GL);printf("\n廣度遍歷:");BFSTraverse(GL);return 0;
}#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0#define MAXSIZE 9 /* 存儲空間初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITY 65535typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼,如OK等 */
typedef int Boolean; /* Boolean是布爾類型,其值是TRUE或FALSE */typedef char VertexType; /* 頂點類型應由用戶定義 */
typedef int EdgeType; /* 邊上的權(quán)值類型應由用戶定義 *//* 鄰接矩陣結(jié)構(gòu) */
typedef struct
{VertexType vexs[MAXVEX]; /* 頂點表 */EdgeType arc[MAXVEX][MAXVEX];/* 鄰接矩陣,可看作邊表 */int numVertexes, numEdges; /* 圖中當前的頂點數(shù)和邊數(shù) */
}MGraph;/* 鄰接表結(jié)構(gòu)****************** */
typedef struct EdgeNode /* 邊表結(jié)點 */
{int adjvex; /* 鄰接點域,存儲該頂點對應的下標 */int weight; /* 用于存儲權(quán)值,對于非網(wǎng)圖可以不需要 */struct EdgeNode *next; /* 鏈域,指向下一個鄰接點 */
}EdgeNode;typedef struct VertexNode /* 頂點表結(jié)點 */
{int in; /* 頂點入度 */char data; /* 頂點域,存儲頂點信息 */EdgeNode *firstedge;/* 邊表頭指針 */
}VertexNode, AdjList[MAXVEX];typedef struct
{AdjList adjList; int numVertexes,numEdges; /* 圖中當前頂點數(shù)和邊數(shù) */
}graphAdjList,*GraphAdjList;
/* **************************** *//* 用到的隊列結(jié)構(gòu)與函數(shù)********************************** */
/* 循環(huán)隊列的順序存儲結(jié)構(gòu) */
typedef struct
{int data[MAXSIZE];int front; /* 頭指針 */int rear; /* 尾指針,若隊列不空,指向隊列尾元素的下一個位置 */
}Queue;/* 初始化一個空隊列Q */
Status InitQueue(Queue *Q)
{Q->front=0;Q->rear=0;return OK;
}/* 若隊列Q為空隊列,則返回TRUE,否則返回FALSE */
Status QueueEmpty(Queue Q)
{ if(Q.front==Q.rear) /* 隊列空的標志 */return TRUE;elsereturn FALSE;
}/* 若隊列未滿,則插入元素e為Q新的隊尾元素 */
Status EnQueue(Queue *Q,int e)
{if ((Q->rear+1)%MAXSIZE == Q->front) /* 隊列滿的判斷 */return ERROR;Q->data[Q->rear]=e; /* 將元素e賦值給隊尾 */Q->rear=(Q->rear+1)%MAXSIZE;/* rear指針向后移一位置, *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK;
}/* 若隊列不空,則刪除Q中隊頭元素,用e返回其值 */
Status DeQueue(Queue *Q,int *e)
{if (Q->front == Q->rear) /* 隊列空的判斷 */return ERROR;*e=Q->data[Q->front]; /* 將隊頭元素賦值給e */Q->front=(Q->front+1)%MAXSIZE; /* front指針向后移一位置, *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK;
}
/* ****************************************************** */void CreateMGraph(MGraph *G)
{int i, j;G->numEdges=15;G->numVertexes=9;/* 讀入頂點信息,建立頂點表 */ G->vexs[0]='A';G->vexs[1]='B';G->vexs[2]='C';G->vexs[3]='D';G->vexs[4]='E';G->vexs[5]='F';G->vexs[6]='G';G->vexs[7]='H';G->vexs[8]='I';for (i = 0; i < G->numVertexes; i++)/* 初始化圖 */{for ( j = 0; j < G->numVertexes; j++){G->arc[i][j]=0;}}G->arc[0][1]=1;G->arc[0][5]=1;G->arc[1][2]=1; G->arc[1][8]=1; G->arc[1][6]=1; G->arc[2][3]=1; G->arc[2][8]=1; G->arc[3][4]=1;G->arc[3][7]=1;G->arc[3][6]=1;G->arc[3][8]=1;G->arc[4][5]=1;G->arc[4][7]=1;G->arc[5][6]=1; G->arc[6][7]=1; for(i = 0; i < G->numVertexes; i++){for(j = i; j < G->numVertexes; j++){G->arc[j][i] =G->arc[i][j];}}}/* 利用鄰接矩陣構(gòu)建鄰接表 */
void CreateALGraph(MGraph G,GraphAdjList *GL)
{int i,j;EdgeNode *e;*GL = (GraphAdjList)malloc(sizeof(graphAdjList));(*GL)->numVertexes=G.numVertexes;(*GL)->numEdges=G.numEdges;for(i= 0;i <G.numVertexes;i++) /* 讀入頂點信息,建立頂點表 */ {(*GL)->adjList[i].in=0;(*GL)->adjList[i].data=G.vexs[i];(*GL)->adjList[i].firstedge=NULL; /* 將邊表置為空表 */}for(i=0;i<G.numVertexes;i++) /* 建立邊表 */{ for(j=0;j<G.numVertexes;j++){if (G.arc[i][j]==1){e=(EdgeNode *)malloc(sizeof(EdgeNode));e->adjvex=j; /* 鄰接序號為j */ e->next=(*GL)->adjList[i].firstedge; /* 將當前頂點上的指向的結(jié)點指針賦值給e */(*GL)->adjList[i].firstedge=e; /* 將當前頂點的指針指向e */ (*GL)->adjList[j].in++;}}}}Boolean visited[MAXSIZE]; /* 訪問標志的數(shù)組 *//* 鄰接表的深度優(yōu)先遞歸算法 */
void DFS(GraphAdjList GL, int i)
{EdgeNode *p;visited[i] = TRUE;printf("%c ",GL->adjList[i].data);/* 打印頂點,也可以其它操作 */p = GL->adjList[i].firstedge;while(p){if(!visited[p->adjvex])DFS(GL, p->adjvex);/* 對為訪問的鄰接頂點遞歸調(diào)用 */p = p->next;}
}/* 鄰接表的深度遍歷操作 */
void DFSTraverse(GraphAdjList GL)
{int i;for(i = 0; i < GL->numVertexes; i++)visited[i] = FALSE; /* 初始所有頂點狀態(tài)都是未訪問過狀態(tài) */for(i = 0; i < GL->numVertexes; i++)if(!visited[i]) /* 對未訪問過的頂點調(diào)用DFS,若是連通圖,只會執(zhí)行一次 */ DFS(GL, i);
}/* 鄰接表的廣度遍歷算法 */
void BFSTraverse(GraphAdjList GL)
{int i;EdgeNode *p;Queue Q;for(i = 0; i < GL->numVertexes; i++)visited[i] = FALSE;InitQueue(&Q);for(i = 0; i < GL->numVertexes; i++){if (!visited[i]){visited[i]=TRUE;printf("%c ",GL->adjList[i].data);/* 打印頂點,也可以其它操作 */EnQueue(&Q,i);while(!QueueEmpty(Q)){DeQueue(&Q,&i);p = GL->adjList[i].firstedge; /* 找到當前頂點的邊表鏈表頭指針 */while(p){if(!visited[p->adjvex]) /* 若此頂點未被訪問 */{visited[p->adjvex]=TRUE;printf("%c ",GL->adjList[p->adjvex].data);EnQueue(&Q,p->adjvex); /* 將此頂點入隊列 */}p = p->next; /* 指針指向下一個鄰接點 */}}}}
}int main(void)
{ MGraph G; GraphAdjList GL; CreateMGraph(&G);CreateALGraph(G,&GL);printf("\n深度遍歷:");DFSTraverse(GL);printf("\n廣度遍歷:");BFSTraverse(GL);return 0;
}#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0#define MAXSIZE 9 /* 存儲空間初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITY 65535typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼,如OK等 */
typedef int Boolean; /* Boolean是布爾類型,其值是TRUE或FALSE */typedef char VertexType; /* 頂點類型應由用戶定義 */
typedef int EdgeType; /* 邊上的權(quán)值類型應由用戶定義 *//* 鄰接矩陣結(jié)構(gòu) */
typedef struct
{VertexType vexs[MAXVEX]; /* 頂點表 */EdgeType arc[MAXVEX][MAXVEX];/* 鄰接矩陣,可看作邊表 */int numVertexes, numEdges; /* 圖中當前的頂點數(shù)和邊數(shù) */
}MGraph;/* 鄰接表結(jié)構(gòu)****************** */
typedef struct EdgeNode /* 邊表結(jié)點 */
{int adjvex; /* 鄰接點域,存儲該頂點對應的下標 */int weight; /* 用于存儲權(quán)值,對于非網(wǎng)圖可以不需要 */struct EdgeNode *next; /* 鏈域,指向下一個鄰接點 */
}EdgeNode;typedef struct VertexNode /* 頂點表結(jié)點 */
{int in; /* 頂點入度 */char data; /* 頂點域,存儲頂點信息 */EdgeNode *firstedge;/* 邊表頭指針 */
}VertexNode, AdjList[MAXVEX];typedef struct
{AdjList adjList; int numVertexes,numEdges; /* 圖中當前頂點數(shù)和邊數(shù) */
}graphAdjList,*GraphAdjList;
/* **************************** *//* 用到的隊列結(jié)構(gòu)與函數(shù)********************************** */
/* 循環(huán)隊列的順序存儲結(jié)構(gòu) */
typedef struct
{int data[MAXSIZE];int front; /* 頭指針 */int rear; /* 尾指針,若隊列不空,指向隊列尾元素的下一個位置 */
}Queue;/* 初始化一個空隊列Q */
Status InitQueue(Queue *Q)
{Q->front=0;Q->rear=0;return OK;
}/* 若隊列Q為空隊列,則返回TRUE,否則返回FALSE */
Status QueueEmpty(Queue Q)
{ if(Q.front==Q.rear) /* 隊列空的標志 */return TRUE;elsereturn FALSE;
}/* 若隊列未滿,則插入元素e為Q新的隊尾元素 */
Status EnQueue(Queue *Q,int e)
{if ((Q->rear+1)%MAXSIZE == Q->front) /* 隊列滿的判斷 */return ERROR;Q->data[Q->rear]=e; /* 將元素e賦值給隊尾 */Q->rear=(Q->rear+1)%MAXSIZE;/* rear指針向后移一位置, *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK;
}/* 若隊列不空,則刪除Q中隊頭元素,用e返回其值 */
Status DeQueue(Queue *Q,int *e)
{if (Q->front == Q->rear) /* 隊列空的判斷 */return ERROR;*e=Q->data[Q->front]; /* 將隊頭元素賦值給e */Q->front=(Q->front+1)%MAXSIZE; /* front指針向后移一位置, *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK;
}
/* ****************************************************** */void CreateMGraph(MGraph *G)
{int i, j;G->numEdges=15;G->numVertexes=9;/* 讀入頂點信息,建立頂點表 */ G->vexs[0]='A';G->vexs[1]='B';G->vexs[2]='C';G->vexs[3]='D';G->vexs[4]='E';G->vexs[5]='F';G->vexs[6]='G';G->vexs[7]='H';G->vexs[8]='I';for (i = 0; i < G->numVertexes; i++)/* 初始化圖 */{for ( j = 0; j < G->numVertexes; j++){G->arc[i][j]=0;}}G->arc[0][1]=1;G->arc[0][5]=1;G->arc[1][2]=1; G->arc[1][8]=1; G->arc[1][6]=1; G->arc[2][3]=1; G->arc[2][8]=1; G->arc[3][4]=1;G->arc[3][7]=1;G->arc[3][6]=1;G->arc[3][8]=1;G->arc[4][5]=1;G->arc[4][7]=1;G->arc[5][6]=1; G->arc[6][7]=1; for(i = 0; i < G->numVertexes; i++){for(j = i; j < G->numVertexes; j++){G->arc[j][i] =G->arc[i][j];}}}/* 利用鄰接矩陣構(gòu)建鄰接表 */
void CreateALGraph(MGraph G,GraphAdjList *GL)
{int i,j;EdgeNode *e;*GL = (GraphAdjList)malloc(sizeof(graphAdjList));(*GL)->numVertexes=G.numVertexes;(*GL)->numEdges=G.numEdges;for(i= 0;i <G.numVertexes;i++) /* 讀入頂點信息,建立頂點表 */ {(*GL)->adjList[i].in=0;(*GL)->adjList[i].data=G.vexs[i];(*GL)->adjList[i].firstedge=NULL; /* 將邊表置為空表 */}for(i=0;i<G.numVertexes;i++) /* 建立邊表 */{ for(j=0;j<G.numVertexes;j++){if (G.arc[i][j]==1){e=(EdgeNode *)malloc(sizeof(EdgeNode));e->adjvex=j; /* 鄰接序號為j */ e->next=(*GL)->adjList[i].firstedge; /* 將當前頂點上的指向的結(jié)點指針賦值給e */(*GL)->adjList[i].firstedge=e; /* 將當前頂點的指針指向e */ (*GL)->adjList[j].in++;}}}}Boolean visited[MAXSIZE]; /* 訪問標志的數(shù)組 *//* 鄰接表的深度優(yōu)先遞歸算法 */
void DFS(GraphAdjList GL, int i)
{EdgeNode *p;visited[i] = TRUE;printf("%c ",GL->adjList[i].data);/* 打印頂點,也可以其它操作 */p = GL->adjList[i].firstedge;while(p){if(!visited[p->adjvex])DFS(GL, p->adjvex);/* 對為訪問的鄰接頂點遞歸調(diào)用 */p = p->next;}
}/* 鄰接表的深度遍歷操作 */
void DFSTraverse(GraphAdjList GL)
{int i;for(i = 0; i < GL->numVertexes; i++)visited[i] = FALSE; /* 初始所有頂點狀態(tài)都是未訪問過狀態(tài) */for(i = 0; i < GL->numVertexes; i++)if(!visited[i]) /* 對未訪問過的頂點調(diào)用DFS,若是連通圖,只會執(zhí)行一次 */ DFS(GL, i);
}/* 鄰接表的廣度遍歷算法 */
void BFSTraverse(GraphAdjList GL)
{int i;EdgeNode *p;Queue Q;for(i = 0; i < GL->numVertexes; i++)visited[i] = FALSE;InitQueue(&Q);for(i = 0; i < GL->numVertexes; i++){if (!visited[i]){visited[i]=TRUE;printf("%c ",GL->adjList[i].data);/* 打印頂點,也可以其它操作 */EnQueue(&Q,i);while(!QueueEmpty(Q)){DeQueue(&Q,&i);p = GL->adjList[i].firstedge; /* 找到當前頂點的邊表鏈表頭指針 */while(p){if(!visited[p->adjvex]) /* 若此頂點未被訪問 */{visited[p->adjvex]=TRUE;printf("%c ",GL->adjList[p->adjvex].data);EnQueue(&Q,p->adjvex); /* 將此頂點入隊列 */}p = p->next; /* 指針指向下一個鄰接點 */}}}}
}int main(void)
{ MGraph G; GraphAdjList GL; CreateMGraph(&G);CreateALGraph(G,&GL);printf("\n深度遍歷:");DFSTraverse(GL);printf("\n廣度遍歷:");BFSTraverse(GL);return 0;
}
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0#define MAXSIZE 9 /* 存儲空間初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITY 65535typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼,如OK等 */
typedef int Boolean; /* Boolean是布爾類型,其值是TRUE或FALSE */typedef char VertexType; /* 頂點類型應由用戶定義 */
typedef int EdgeType; /* 邊上的權(quán)值類型應由用戶定義 *//* 鄰接矩陣結(jié)構(gòu) */
typedef struct
{VertexType vexs[MAXVEX]; /* 頂點表 */EdgeType arc[MAXVEX][MAXVEX];/* 鄰接矩陣,可看作邊表 */int numVertexes, numEdges; /* 圖中當前的頂點數(shù)和邊數(shù) */
}MGraph;/* 鄰接表結(jié)構(gòu)****************** */
typedef struct EdgeNode /* 邊表結(jié)點 */
{int adjvex; /* 鄰接點域,存儲該頂點對應的下標 */int weight; /* 用于存儲權(quán)值,對于非網(wǎng)圖可以不需要 */struct EdgeNode *next; /* 鏈域,指向下一個鄰接點 */
}EdgeNode;typedef struct VertexNode /* 頂點表結(jié)點 */
{int in; /* 頂點入度 */char data; /* 頂點域,存儲頂點信息 */EdgeNode *firstedge;/* 邊表頭指針 */
}VertexNode, AdjList[MAXVEX];typedef struct
{AdjList adjList; int numVertexes,numEdges; /* 圖中當前頂點數(shù)和邊數(shù) */
}graphAdjList,*GraphAdjList;
/* **************************** *//* 用到的隊列結(jié)構(gòu)與函數(shù)********************************** */
/* 循環(huán)隊列的順序存儲結(jié)構(gòu) */
typedef struct
{int data[MAXSIZE];int front; /* 頭指針 */int rear; /* 尾指針,若隊列不空,指向隊列尾元素的下一個位置 */
}Queue;/* 初始化一個空隊列Q */
Status InitQueue(Queue *Q)
{Q->front=0;Q->rear=0;return OK;
}/* 若隊列Q為空隊列,則返回TRUE,否則返回FALSE */
Status QueueEmpty(Queue Q)
{ if(Q.front==Q.rear) /* 隊列空的標志 */return TRUE;elsereturn FALSE;
}/* 若隊列未滿,則插入元素e為Q新的隊尾元素 */
Status EnQueue(Queue *Q,int e)
{if ((Q->rear+1)%MAXSIZE == Q->front) /* 隊列滿的判斷 */return ERROR;Q->data[Q->rear]=e; /* 將元素e賦值給隊尾 */Q->rear=(Q->rear+1)%MAXSIZE;/* rear指針向后移一位置, *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK;
}/* 若隊列不空,則刪除Q中隊頭元素,用e返回其值 */
Status DeQueue(Queue *Q,int *e)
{if (Q->front == Q->rear) /* 隊列空的判斷 */return ERROR;*e=Q->data[Q->front]; /* 將隊頭元素賦值給e */Q->front=(Q->front+1)%MAXSIZE; /* front指針向后移一位置, *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK;
}
/* ****************************************************** */void CreateMGraph(MGraph *G)
{int i, j;G->numEdges=15;G->numVertexes=9;/* 讀入頂點信息,建立頂點表 */ G->vexs[0]='A';G->vexs[1]='B';G->vexs[2]='C';G->vexs[3]='D';G->vexs[4]='E';G->vexs[5]='F';G->vexs[6]='G';G->vexs[7]='H';G->vexs[8]='I';for (i = 0; i < G->numVertexes; i++)/* 初始化圖 */{for ( j = 0; j < G->numVertexes; j++){G->arc[i][j]=0;}}G->arc[0][1]=1;G->arc[0][5]=1;G->arc[1][2]=1; G->arc[1][8]=1; G->arc[1][6]=1; G->arc[2][3]=1; G->arc[2][8]=1; G->arc[3][4]=1;G->arc[3][7]=1;G->arc[3][6]=1;G->arc[3][8]=1;G->arc[4][5]=1;G->arc[4][7]=1;G->arc[5][6]=1; G->arc[6][7]=1; for(i = 0; i < G->numVertexes; i++){for(j = i; j < G->numVertexes; j++){G->arc[j][i] =G->arc[i][j];}}}/* 利用鄰接矩陣構(gòu)建鄰接表 */
void CreateALGraph(MGraph G,GraphAdjList *GL)
{int i,j;EdgeNode *e;*GL = (GraphAdjList)malloc(sizeof(graphAdjList));(*GL)->numVertexes=G.numVertexes;(*GL)->numEdges=G.numEdges;for(i= 0;i <G.numVertexes;i++) /* 讀入頂點信息,建立頂點表 */ {(*GL)->adjList[i].in=0;(*GL)->adjList[i].data=G.vexs[i];(*GL)->adjList[i].firstedge=NULL; /* 將邊表置為空表 */}for(i=0;i<G.numVertexes;i++) /* 建立邊表 */{ for(j=0;j<G.numVertexes;j++){if (G.arc[i][j]==1){e=(EdgeNode *)malloc(sizeof(EdgeNode));e->adjvex=j; /* 鄰接序號為j */ e->next=(*GL)->adjList[i].firstedge; /* 將當前頂點上的指向的結(jié)點指針賦值給e */(*GL)->adjList[i].firstedge=e; /* 將當前頂點的指針指向e */ (*GL)->adjList[j].in++;}}}}Boolean visited[MAXSIZE]; /* 訪問標志的數(shù)組 *//* 鄰接表的深度優(yōu)先遞歸算法 */
void DFS(GraphAdjList GL, int i)
{EdgeNode *p;visited[i] = TRUE;printf("%c ",GL->adjList[i].data);/* 打印頂點,也可以其它操作 */p = GL->adjList[i].firstedge;while(p){if(!visited[p->adjvex])DFS(GL, p->adjvex);/* 對為訪問的鄰接頂點遞歸調(diào)用 */p = p->next;}
}/* 鄰接表的深度遍歷操作 */
void DFSTraverse(GraphAdjList GL)
{int i;for(i = 0; i < GL->numVertexes; i++)visited[i] = FALSE; /* 初始所有頂點狀態(tài)都是未訪問過狀態(tài) */for(i = 0; i < GL->numVertexes; i++)if(!visited[i]) /* 對未訪問過的頂點調(diào)用DFS,若是連通圖,只會執(zhí)行一次 */ DFS(GL, i);
}/* 鄰接表的廣度遍歷算法 */
void BFSTraverse(GraphAdjList GL)
{int i;EdgeNode *p;Queue Q;for(i = 0; i < GL->numVertexes; i++)visited[i] = FALSE;InitQueue(&Q);for(i = 0; i < GL->numVertexes; i++){if (!visited[i]){visited[i]=TRUE;printf("%c ",GL->adjList[i].data);/* 打印頂點,也可以其它操作 */EnQueue(&Q,i);while(!QueueEmpty(Q)){DeQueue(&Q,&i);p = GL->adjList[i].firstedge; /* 找到當前頂點的邊表鏈表頭指針 */while(p){if(!visited[p->adjvex]) /* 若此頂點未被訪問 */{visited[p->adjvex]=TRUE;printf("%c ",GL->adjList[p->adjvex].data);EnQueue(&Q,p->adjvex); /* 將此頂點入隊列 */}p = p->next; /* 指針指向下一個鄰接點 */}}}}
}int main(void)
{ MGraph G; GraphAdjList GL; CreateMGraph(&G);CreateALGraph(G,&GL);printf("\n深度遍歷:");DFSTraverse(GL);printf("\n廣度遍歷:");BFSTraverse(GL);return 0;
}
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0#define MAXSIZE 9 /* 存儲空間初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITY 65535typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼,如OK等 */
typedef int Boolean; /* Boolean是布爾類型,其值是TRUE或FALSE */typedef char VertexType; /* 頂點類型應由用戶定義 */
typedef int EdgeType; /* 邊上的權(quán)值類型應由用戶定義 *//* 鄰接矩陣結(jié)構(gòu) */
typedef struct
{VertexType vexs[MAXVEX]; /* 頂點表 */EdgeType arc[MAXVEX][MAXVEX];/* 鄰接矩陣,可看作邊表 */int numVertexes, numEdges; /* 圖中當前的頂點數(shù)和邊數(shù) */
}MGraph;/* 鄰接表結(jié)構(gòu)****************** */
typedef struct EdgeNode /* 邊表結(jié)點 */
{int adjvex; /* 鄰接點域,存儲該頂點對應的下標 */int weight; /* 用于存儲權(quán)值,對于非網(wǎng)圖可以不需要 */struct EdgeNode *next; /* 鏈域,指向下一個鄰接點 */
}EdgeNode;typedef struct VertexNode /* 頂點表結(jié)點 */
{int in; /* 頂點入度 */char data; /* 頂點域,存儲頂點信息 */EdgeNode *firstedge;/* 邊表頭指針 */
}VertexNode, AdjList[MAXVEX];typedef struct
{AdjList adjList; int numVertexes,numEdges; /* 圖中當前頂點數(shù)和邊數(shù) */
}graphAdjList,*GraphAdjList;
/* **************************** *//* 用到的隊列結(jié)構(gòu)與函數(shù)********************************** */
/* 循環(huán)隊列的順序存儲結(jié)構(gòu) */
typedef struct
{int data[MAXSIZE];int front; /* 頭指針 */int rear; /* 尾指針,若隊列不空,指向隊列尾元素的下一個位置 */
}Queue;/* 初始化一個空隊列Q */
Status InitQueue(Queue *Q)
{Q->front=0;Q->rear=0;return OK;
}/* 若隊列Q為空隊列,則返回TRUE,否則返回FALSE */
Status QueueEmpty(Queue Q)
{ if(Q.front==Q.rear) /* 隊列空的標志 */return TRUE;elsereturn FALSE;
}/* 若隊列未滿,則插入元素e為Q新的隊尾元素 */
Status EnQueue(Queue *Q,int e)
{if ((Q->rear+1)%MAXSIZE == Q->front) /* 隊列滿的判斷 */return ERROR;Q->data[Q->rear]=e; /* 將元素e賦值給隊尾 */Q->rear=(Q->rear+1)%MAXSIZE;/* rear指針向后移一位置, *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK;
}/* 若隊列不空,則刪除Q中隊頭元素,用e返回其值 */
Status DeQueue(Queue *Q,int *e)
{if (Q->front == Q->rear) /* 隊列空的判斷 */return ERROR;*e=Q->data[Q->front]; /* 將隊頭元素賦值給e */Q->front=(Q->front+1)%MAXSIZE; /* front指針向后移一位置, *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK;
}
/* ****************************************************** */void CreateMGraph(MGraph *G)
{int i, j;G->numEdges=15;G->numVertexes=9;/* 讀入頂點信息,建立頂點表 */ G->vexs[0]='A';G->vexs[1]='B';G->vexs[2]='C';G->vexs[3]='D';G->vexs[4]='E';G->vexs[5]='F';G->vexs[6]='G';G->vexs[7]='H';G->vexs[8]='I';for (i = 0; i < G->numVertexes; i++)/* 初始化圖 */{for ( j = 0; j < G->numVertexes; j++){G->arc[i][j]=0;}}G->arc[0][1]=1;G->arc[0][5]=1;G->arc[1][2]=1; G->arc[1][8]=1; G->arc[1][6]=1; G->arc[2][3]=1; G->arc[2][8]=1; G->arc[3][4]=1;G->arc[3][7]=1;G->arc[3][6]=1;G->arc[3][8]=1;G->arc[4][5]=1;G->arc[4][7]=1;G->arc[5][6]=1; G->arc[6][7]=1; for(i = 0; i < G->numVertexes; i++){for(j = i; j < G->numVertexes; j++){G->arc[j][i] =G->arc[i][j];}}}/* 利用鄰接矩陣構(gòu)建鄰接表 */
void CreateALGraph(MGraph G,GraphAdjList *GL)
{int i,j;EdgeNode *e;*GL = (GraphAdjList)malloc(sizeof(graphAdjList));(*GL)->numVertexes=G.numVertexes;(*GL)->numEdges=G.numEdges;for(i= 0;i <G.numVertexes;i++) /* 讀入頂點信息,建立頂點表 */ {(*GL)->adjList[i].in=0;(*GL)->adjList[i].data=G.vexs[i];(*GL)->adjList[i].firstedge=NULL; /* 將邊表置為空表 */}for(i=0;i<G.numVertexes;i++) /* 建立邊表 */{ for(j=0;j<G.numVertexes;j++){if (G.arc[i][j]==1){e=(EdgeNode *)malloc(sizeof(EdgeNode));e->adjvex=j; /* 鄰接序號為j */ e->next=(*GL)->adjList[i].firstedge; /* 將當前頂點上的指向的結(jié)點指針賦值給e */(*GL)->adjList[i].firstedge=e; /* 將當前頂點的指針指向e */ (*GL)->adjList[j].in++;}}}}Boolean visited[MAXSIZE]; /* 訪問標志的數(shù)組 *//* 鄰接表的深度優(yōu)先遞歸算法 */
void DFS(GraphAdjList GL, int i)
{EdgeNode *p;visited[i] = TRUE;printf("%c ",GL->adjList[i].data);/* 打印頂點,也可以其它操作 */p = GL->adjList[i].firstedge;while(p){if(!visited[p->adjvex])DFS(GL, p->adjvex);/* 對為訪問的鄰接頂點遞歸調(diào)用 */p = p->next;}
}/* 鄰接表的深度遍歷操作 */
void DFSTraverse(GraphAdjList GL)
{int i;for(i = 0; i < GL->numVertexes; i++)visited[i] = FALSE; /* 初始所有頂點狀態(tài)都是未訪問過狀態(tài) */for(i = 0; i < GL->numVertexes; i++)if(!visited[i]) /* 對未訪問過的頂點調(diào)用DFS,若是連通圖,只會執(zhí)行一次 */ DFS(GL, i);
}/* 鄰接表的廣度遍歷算法 */
void BFSTraverse(GraphAdjList GL)
{int i;EdgeNode *p;Queue Q;for(i = 0; i < GL->numVertexes; i++)visited[i] = FALSE;InitQueue(&Q);for(i = 0; i < GL->numVertexes; i++){if (!visited[i]){visited[i]=TRUE;printf("%c ",GL->adjList[i].data);/* 打印頂點,也可以其它操作 */EnQueue(&Q,i);while(!QueueEmpty(Q)){DeQueue(&Q,&i);p = GL->adjList[i].firstedge; /* 找到當前頂點的邊表鏈表頭指針 */while(p){if(!visited[p->adjvex]) /* 若此頂點未被訪問 */{visited[p->adjvex]=TRUE;printf("%c ",GL->adjList[p->adjvex].data);EnQueue(&Q,p->adjvex); /* 將此頂點入隊列 */}p = p->next; /* 指針指向下一個鄰接點 */}}}}
}int main(void)
{ MGraph G; GraphAdjList GL; CreateMGraph(&G);CreateALGraph(G,&GL);printf("\n深度遍歷:");DFSTraverse(GL);printf("\n廣度遍歷:");BFSTraverse(GL);return 0;
}
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0#define MAXSIZE 9 /* 存儲空間初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITY 65535typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼,如OK等 */
typedef int Boolean; /* Boolean是布爾類型,其值是TRUE或FALSE */typedef char VertexType; /* 頂點類型應由用戶定義 */
typedef int EdgeType; /* 邊上的權(quán)值類型應由用戶定義 *//* 鄰接矩陣結(jié)構(gòu) */
typedef struct
{VertexType vexs[MAXVEX]; /* 頂點表 */EdgeType arc[MAXVEX][MAXVEX];/* 鄰接矩陣,可看作邊表 */int numVertexes, numEdges; /* 圖中當前的頂點數(shù)和邊數(shù) */
}MGraph;/* 鄰接表結(jié)構(gòu)****************** */
typedef struct EdgeNode /* 邊表結(jié)點 */
{int adjvex; /* 鄰接點域,存儲該頂點對應的下標 */int weight; /* 用于存儲權(quán)值,對于非網(wǎng)圖可以不需要 */struct EdgeNode *next; /* 鏈域,指向下一個鄰接點 */
}EdgeNode;typedef struct VertexNode /* 頂點表結(jié)點 */
{int in; /* 頂點入度 */char data; /* 頂點域,存儲頂點信息 */EdgeNode *firstedge;/* 邊表頭指針 */
}VertexNode, AdjList[MAXVEX];typedef struct
{AdjList adjList; int numVertexes,numEdges; /* 圖中當前頂點數(shù)和邊數(shù) */
}graphAdjList,*GraphAdjList;
/* **************************** *//* 用到的隊列結(jié)構(gòu)與函數(shù)********************************** */
/* 循環(huán)隊列的順序存儲結(jié)構(gòu) */
typedef struct
{int data[MAXSIZE];int front; /* 頭指針 */int rear; /* 尾指針,若隊列不空,指向隊列尾元素的下一個位置 */
}Queue;/* 初始化一個空隊列Q */
Status InitQueue(Queue *Q)
{Q->front=0;Q->rear=0;return OK;
}/* 若隊列Q為空隊列,則返回TRUE,否則返回FALSE */
Status QueueEmpty(Queue Q)
{ if(Q.front==Q.rear) /* 隊列空的標志 */return TRUE;elsereturn FALSE;
}/* 若隊列未滿,則插入元素e為Q新的隊尾元素 */
Status EnQueue(Queue *Q,int e)
{if ((Q->rear+1)%MAXSIZE == Q->front) /* 隊列滿的判斷 */return ERROR;Q->data[Q->rear]=e; /* 將元素e賦值給隊尾 */Q->rear=(Q->rear+1)%MAXSIZE;/* rear指針向后移一位置, *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK;
}/* 若隊列不空,則刪除Q中隊頭元素,用e返回其值 */
Status DeQueue(Queue *Q,int *e)
{if (Q->front == Q->rear) /* 隊列空的判斷 */return ERROR;*e=Q->data[Q->front]; /* 將隊頭元素賦值給e */Q->front=(Q->front+1)%MAXSIZE; /* front指針向后移一位置, *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK;
}
/* ****************************************************** */void CreateMGraph(MGraph *G)
{int i, j;G->numEdges=15;G->numVertexes=9;/* 讀入頂點信息,建立頂點表 */ G->vexs[0]='A';G->vexs[1]='B';G->vexs[2]='C';G->vexs[3]='D';G->vexs[4]='E';G->vexs[5]='F';G->vexs[6]='G';G->vexs[7]='H';G->vexs[8]='I';for (i = 0; i < G->numVertexes; i++)/* 初始化圖 */{for ( j = 0; j < G->numVertexes; j++){G->arc[i][j]=0;}}G->arc[0][1]=1;G->arc[0][5]=1;G->arc[1][2]=1; G->arc[1][8]=1; G->arc[1][6]=1; G->arc[2][3]=1; G->arc[2][8]=1; G->arc[3][4]=1;G->arc[3][7]=1;G->arc[3][6]=1;G->arc[3][8]=1;G->arc[4][5]=1;G->arc[4][7]=1;G->arc[5][6]=1; G->arc[6][7]=1; for(i = 0; i < G->numVertexes; i++){for(j = i; j < G->numVertexes; j++){G->arc[j][i] =G->arc[i][j];}}}/* 利用鄰接矩陣構(gòu)建鄰接表 */
void CreateALGraph(MGraph G,GraphAdjList *GL)
{int i,j;EdgeNode *e;*GL = (GraphAdjList)malloc(sizeof(graphAdjList));(*GL)->numVertexes=G.numVertexes;(*GL)->numEdges=G.numEdges;for(i= 0;i <G.numVertexes;i++) /* 讀入頂點信息,建立頂點表 */ {(*GL)->adjList[i].in=0;(*GL)->adjList[i].data=G.vexs[i];(*GL)->adjList[i].firstedge=NULL; /* 將邊表置為空表 */}for(i=0;i<G.numVertexes;i++) /* 建立邊表 */{ for(j=0;j<G.numVertexes;j++){if (G.arc[i][j]==1){e=(EdgeNode *)malloc(sizeof(EdgeNode));e->adjvex=j; /* 鄰接序號為j */ e->next=(*GL)->adjList[i].firstedge; /* 將當前頂點上的指向的結(jié)點指針賦值給e */(*GL)->adjList[i].firstedge=e; /* 將當前頂點的指針指向e */ (*GL)->adjList[j].in++;}}}}Boolean visited[MAXSIZE]; /* 訪問標志的數(shù)組 *//* 鄰接表的深度優(yōu)先遞歸算法 */
void DFS(GraphAdjList GL, int i)
{EdgeNode *p;visited[i] = TRUE;printf("%c ",GL->adjList[i].data);/* 打印頂點,也可以其它操作 */p = GL->adjList[i].firstedge;while(p){if(!visited[p->adjvex])DFS(GL, p->adjvex);/* 對為訪問的鄰接頂點遞歸調(diào)用 */p = p->next;}
}/* 鄰接表的深度遍歷操作 */
void DFSTraverse(GraphAdjList GL)
{int i;for(i = 0; i < GL->numVertexes; i++)visited[i] = FALSE; /* 初始所有頂點狀態(tài)都是未訪問過狀態(tài) */for(i = 0; i < GL->numVertexes; i++)if(!visited[i]) /* 對未訪問過的頂點調(diào)用DFS,若是連通圖,只會執(zhí)行一次 */ DFS(GL, i);
}/* 鄰接表的廣度遍歷算法 */
void BFSTraverse(GraphAdjList GL)
{int i;EdgeNode *p;Queue Q;for(i = 0; i < GL->numVertexes; i++)visited[i] = FALSE;InitQueue(&Q);for(i = 0; i < GL->numVertexes; i++){if (!visited[i]){visited[i]=TRUE;printf("%c ",GL->adjList[i].data);/* 打印頂點,也可以其它操作 */EnQueue(&Q,i);while(!QueueEmpty(Q)){DeQueue(&Q,&i);p = GL->adjList[i].firstedge; /* 找到當前頂點的邊表鏈表頭指針 */while(p){if(!visited[p->adjvex]) /* 若此頂點未被訪問 */{visited[p->adjvex]=TRUE;printf("%c ",GL->adjList[p->adjvex].data);EnQueue(&Q,p->adjvex); /* 將此頂點入隊列 */}p = p->next; /* 指針指向下一個鄰接點 */}}}}
}int main(void)
{ MGraph G; GraphAdjList GL; CreateMGraph(&G);CreateALGraph(G,&GL);printf("\n深度遍歷:");DFSTraverse(GL);printf("\n廣度遍歷:");BFSTraverse(GL);return 0;
}
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0#define MAXSIZE 9 /* 存儲空間初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITY 65535typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼,如OK等 */
typedef int Boolean; /* Boolean是布爾類型,其值是TRUE或FALSE */typedef char VertexType; /* 頂點類型應由用戶定義 */
typedef int EdgeType; /* 邊上的權(quán)值類型應由用戶定義 *//* 鄰接矩陣結(jié)構(gòu) */
typedef struct
{VertexType vexs[MAXVEX]; /* 頂點表 */EdgeType arc[MAXVEX][MAXVEX];/* 鄰接矩陣,可看作邊表 */int numVertexes, numEdges; /* 圖中當前的頂點數(shù)和邊數(shù) */
}MGraph;/* 鄰接表結(jié)構(gòu)****************** */
typedef struct EdgeNode /* 邊表結(jié)點 */
{int adjvex; /* 鄰接點域,存儲該頂點對應的下標 */int weight; /* 用于存儲權(quán)值,對于非網(wǎng)圖可以不需要 */struct EdgeNode *next; /* 鏈域,指向下一個鄰接點 */
}EdgeNode;typedef struct VertexNode /* 頂點表結(jié)點 */
{int in; /* 頂點入度 */char data; /* 頂點域,存儲頂點信息 */EdgeNode *firstedge;/* 邊表頭指針 */
}VertexNode, AdjList[MAXVEX];typedef struct
{AdjList adjList; int numVertexes,numEdges; /* 圖中當前頂點數(shù)和邊數(shù) */
}graphAdjList,*GraphAdjList;
/* **************************** *//* 用到的隊列結(jié)構(gòu)與函數(shù)********************************** */
/* 循環(huán)隊列的順序存儲結(jié)構(gòu) */
typedef struct
{int data[MAXSIZE];int front; /* 頭指針 */int rear; /* 尾指針,若隊列不空,指向隊列尾元素的下一個位置 */
}Queue;/* 初始化一個空隊列Q */
Status InitQueue(Queue *Q)
{Q->front=0;Q->rear=0;return OK;
}/* 若隊列Q為空隊列,則返回TRUE,否則返回FALSE */
Status QueueEmpty(Queue Q)
{ if(Q.front==Q.rear) /* 隊列空的標志 */return TRUE;elsereturn FALSE;
}/* 若隊列未滿,則插入元素e為Q新的隊尾元素 */
Status EnQueue(Queue *Q,int e)
{if ((Q->rear+1)%MAXSIZE == Q->front) /* 隊列滿的判斷 */return ERROR;Q->data[Q->rear]=e; /* 將元素e賦值給隊尾 */Q->rear=(Q->rear+1)%MAXSIZE;/* rear指針向后移一位置, *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK;
}/* 若隊列不空,則刪除Q中隊頭元素,用e返回其值 */
Status DeQueue(Queue *Q,int *e)
{if (Q->front == Q->rear) /* 隊列空的判斷 */return ERROR;*e=Q->data[Q->front]; /* 將隊頭元素賦值給e */Q->front=(Q->front+1)%MAXSIZE; /* front指針向后移一位置, *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK;
}
/* ****************************************************** */void CreateMGraph(MGraph *G)
{int i, j;G->numEdges=15;G->numVertexes=9;/* 讀入頂點信息,建立頂點表 */ G->vexs[0]='A';G->vexs[1]='B';G->vexs[2]='C';G->vexs[3]='D';G->vexs[4]='E';G->vexs[5]='F';G->vexs[6]='G';G->vexs[7]='H';G->vexs[8]='I';for (i = 0; i < G->numVertexes; i++)/* 初始化圖 */{for ( j = 0; j < G->numVertexes; j++){G->arc[i][j]=0;}}G->arc[0][1]=1;G->arc[0][5]=1;G->arc[1][2]=1; G->arc[1][8]=1; G->arc[1][6]=1; G->arc[2][3]=1; G->arc[2][8]=1; G->arc[3][4]=1;G->arc[3][7]=1;G->arc[3][6]=1;G->arc[3][8]=1;G->arc[4][5]=1;G->arc[4][7]=1;G->arc[5][6]=1; G->arc[6][7]=1; for(i = 0; i < G->numVertexes; i++){for(j = i; j < G->numVertexes; j++){G->arc[j][i] =G->arc[i][j];}}}/* 利用鄰接矩陣構(gòu)建鄰接表 */
void CreateALGraph(MGraph G,GraphAdjList *GL)
{int i,j;EdgeNode *e;*GL = (GraphAdjList)malloc(sizeof(graphAdjList));(*GL)->numVertexes=G.numVertexes;(*GL)->numEdges=G.numEdges;for(i= 0;i <G.numVertexes;i++) /* 讀入頂點信息,建立頂點表 */ {(*GL)->adjList[i].in=0;(*GL)->adjList[i].data=G.vexs[i];(*GL)->adjList[i].firstedge=NULL; /* 將邊表置為空表 */}for(i=0;i<G.numVertexes;i++) /* 建立邊表 */{ for(j=0;j<G.numVertexes;j++){if (G.arc[i][j]==1){e=(EdgeNode *)malloc(sizeof(EdgeNode));e->adjvex=j; /* 鄰接序號為j */ e->next=(*GL)->adjList[i].firstedge; /* 將當前頂點上的指向的結(jié)點指針賦值給e */(*GL)->adjList[i].firstedge=e; /* 將當前頂點的指針指向e */ (*GL)->adjList[j].in++;}}}}Boolean visited[MAXSIZE]; /* 訪問標志的數(shù)組 *//* 鄰接表的深度優(yōu)先遞歸算法 */
void DFS(GraphAdjList GL, int i)
{EdgeNode *p;visited[i] = TRUE;printf("%c ",GL->adjList[i].data);/* 打印頂點,也可以其它操作 */p = GL->adjList[i].firstedge;while(p){if(!visited[p->adjvex])DFS(GL, p->adjvex);/* 對為訪問的鄰接頂點遞歸調(diào)用 */p = p->next;}
}/* 鄰接表的深度遍歷操作 */
void DFSTraverse(GraphAdjList GL)
{int i;for(i = 0; i < GL->numVertexes; i++)visited[i] = FALSE; /* 初始所有頂點狀態(tài)都是未訪問過狀態(tài) */for(i = 0; i < GL->numVertexes; i++)if(!visited[i]) /* 對未訪問過的頂點調(diào)用DFS,若是連通圖,只會執(zhí)行一次 */ DFS(GL, i);
}/* 鄰接表的廣度遍歷算法 */
void BFSTraverse(GraphAdjList GL)
{int i;EdgeNode *p;Queue Q;for(i = 0; i < GL->numVertexes; i++)visited[i] = FALSE;InitQueue(&Q);for(i = 0; i < GL->numVertexes; i++){if (!visited[i]){visited[i]=TRUE;printf("%c ",GL->adjList[i].data);/* 打印頂點,也可以其它操作 */EnQueue(&Q,i);while(!QueueEmpty(Q)){DeQueue(&Q,&i);p = GL->adjList[i].firstedge; /* 找到當前頂點的邊表鏈表頭指針 */while(p){if(!visited[p->adjvex]) /* 若此頂點未被訪問 */{visited[p->adjvex]=TRUE;printf("%c ",GL->adjList[p->adjvex].data);EnQueue(&Q,p->adjvex); /* 將此頂點入隊列 */}p = p->next; /* 指針指向下一個鄰接點 */}}}}
}int main(void)
{ MGraph G; GraphAdjList GL; CreateMGraph(&G);CreateALGraph(G,&GL);printf("\n深度遍歷:");DFSTraverse(GL);printf("\n廣度遍歷:");BFSTraverse(GL);return 0;
}
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0#define MAXSIZE 9 /* 存儲空間初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITY 65535typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼,如OK等 */
typedef int Boolean; /* Boolean是布爾類型,其值是TRUE或FALSE */typedef char VertexType; /* 頂點類型應由用戶定義 */
typedef int EdgeType; /* 邊上的權(quán)值類型應由用戶定義 *//* 鄰接矩陣結(jié)構(gòu) */
typedef struct
{VertexType vexs[MAXVEX]; /* 頂點表 */EdgeType arc[MAXVEX][MAXVEX];/* 鄰接矩陣,可看作邊表 */int numVertexes, numEdges; /* 圖中當前的頂點數(shù)和邊數(shù) */
}MGraph;/* 鄰接表結(jié)構(gòu)****************** */
typedef struct EdgeNode /* 邊表結(jié)點 */
{int adjvex; /* 鄰接點域,存儲該頂點對應的下標 */int weight; /* 用于存儲權(quán)值,對于非網(wǎng)圖可以不需要 */struct EdgeNode *next; /* 鏈域,指向下一個鄰接點 */
}EdgeNode;typedef struct VertexNode /* 頂點表結(jié)點 */
{int in; /* 頂點入度 */char data; /* 頂點域,存儲頂點信息 */EdgeNode *firstedge;/* 邊表頭指針 */
}VertexNode, AdjList[MAXVEX];typedef struct
{AdjList adjList; int numVertexes,numEdges; /* 圖中當前頂點數(shù)和邊數(shù) */
}graphAdjList,*GraphAdjList;
/* **************************** *//* 用到的隊列結(jié)構(gòu)與函數(shù)********************************** */
/* 循環(huán)隊列的順序存儲結(jié)構(gòu) */
typedef struct
{int data[MAXSIZE];int front; /* 頭指針 */int rear; /* 尾指針,若隊列不空,指向隊列尾元素的下一個位置 */
}Queue;/* 初始化一個空隊列Q */
Status InitQueue(Queue *Q)
{Q->front=0;Q->rear=0;return OK;
}/* 若隊列Q為空隊列,則返回TRUE,否則返回FALSE */
Status QueueEmpty(Queue Q)
{ if(Q.front==Q.rear) /* 隊列空的標志 */return TRUE;elsereturn FALSE;
}/* 若隊列未滿,則插入元素e為Q新的隊尾元素 */
Status EnQueue(Queue *Q,int e)
{if ((Q->rear+1)%MAXSIZE == Q->front) /* 隊列滿的判斷 */return ERROR;Q->data[Q->rear]=e; /* 將元素e賦值給隊尾 */Q->rear=(Q->rear+1)%MAXSIZE;/* rear指針向后移一位置, *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK;
}/* 若隊列不空,則刪除Q中隊頭元素,用e返回其值 */
Status DeQueue(Queue *Q,int *e)
{if (Q->front == Q->rear) /* 隊列空的判斷 */return ERROR;*e=Q->data[Q->front]; /* 將隊頭元素賦值給e */Q->front=(Q->front+1)%MAXSIZE; /* front指針向后移一位置, *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK;
}
/* ****************************************************** */void CreateMGraph(MGraph *G)
{int i, j;G->numEdges=15;G->numVertexes=9;/* 讀入頂點信息,建立頂點表 */ G->vexs[0]='A';G->vexs[1]='B';G->vexs[2]='C';G->vexs[3]='D';G->vexs[4]='E';G->vexs[5]='F';G->vexs[6]='G';G->vexs[7]='H';G->vexs[8]='I';for (i = 0; i < G->numVertexes; i++)/* 初始化圖 */{for ( j = 0; j < G->numVertexes; j++){G->arc[i][j]=0;}}G->arc[0][1]=1;G->arc[0][5]=1;G->arc[1][2]=1; G->arc[1][8]=1; G->arc[1][6]=1; G->arc[2][3]=1; G->arc[2][8]=1; G->arc[3][4]=1;G->arc[3][7]=1;G->arc[3][6]=1;G->arc[3][8]=1;G->arc[4][5]=1;G->arc[4][7]=1;G->arc[5][6]=1; G->arc[6][7]=1; for(i = 0; i < G->numVertexes; i++){for(j = i; j < G->numVertexes; j++){G->arc[j][i] =G->arc[i][j];}}}/* 利用鄰接矩陣構(gòu)建鄰接表 */
void CreateALGraph(MGraph G,GraphAdjList *GL)
{int i,j;EdgeNode *e;*GL = (GraphAdjList)malloc(sizeof(graphAdjList));(*GL)->numVertexes=G.numVertexes;(*GL)->numEdges=G.numEdges;for(i= 0;i <G.numVertexes;i++) /* 讀入頂點信息,建立頂點表 */ {(*GL)->adjList[i].in=0;(*GL)->adjList[i].data=G.vexs[i];(*GL)->adjList[i].firstedge=NULL; /* 將邊表置為空表 */}for(i=0;i<G.numVertexes;i++) /* 建立邊表 */{ for(j=0;j<G.numVertexes;j++){if (G.arc[i][j]==1){e=(EdgeNode *)malloc(sizeof(EdgeNode));e->adjvex=j; /* 鄰接序號為j */ e->next=(*GL)->adjList[i].firstedge; /* 將當前頂點上的指向的結(jié)點指針賦值給e */(*GL)->adjList[i].firstedge=e; /* 將當前頂點的指針指向e */ (*GL)->adjList[j].in++;}}}}Boolean visited[MAXSIZE]; /* 訪問標志的數(shù)組 *//* 鄰接表的深度優(yōu)先遞歸算法 */
void DFS(GraphAdjList GL, int i)
{EdgeNode *p;visited[i] = TRUE;printf("%c ",GL->adjList[i].data);/* 打印頂點,也可以其它操作 */p = GL->adjList[i].firstedge;while(p){if(!visited[p->adjvex])DFS(GL, p->adjvex);/* 對為訪問的鄰接頂點遞歸調(diào)用 */p = p->next;}
}/* 鄰接表的深度遍歷操作 */
void DFSTraverse(GraphAdjList GL)
{int i;for(i = 0; i < GL->numVertexes; i++)visited[i] = FALSE; /* 初始所有頂點狀態(tài)都是未訪問過狀態(tài) */for(i = 0; i < GL->numVertexes; i++)if(!visited[i]) /* 對未訪問過的頂點調(diào)用DFS,若是連通圖,只會執(zhí)行一次 */ DFS(GL, i);
}/* 鄰接表的廣度遍歷算法 */
void BFSTraverse(GraphAdjList GL)
{int i;EdgeNode *p;Queue Q;for(i = 0; i < GL->numVertexes; i++)visited[i] = FALSE;InitQueue(&Q);for(i = 0; i < GL->numVertexes; i++){if (!visited[i]){visited[i]=TRUE;printf("%c ",GL->adjList[i].data);/* 打印頂點,也可以其它操作 */EnQueue(&Q,i);while(!QueueEmpty(Q)){DeQueue(&Q,&i);p = GL->adjList[i].firstedge; /* 找到當前頂點的邊表鏈表頭指針 */while(p){if(!visited[p->adjvex]) /* 若此頂點未被訪問 */{visited[p->adjvex]=TRUE;printf("%c ",GL->adjList[p->adjvex].data);EnQueue(&Q,p->adjvex); /* 將此頂點入隊列 */}p = p->next; /* 指針指向下一個鄰接點 */}}}}
}int main(void)
{ MGraph G; GraphAdjList GL; CreateMGraph(&G);CreateALGraph(G,&GL);printf("\n深度遍歷:");DFSTraverse(GL);printf("\n廣度遍歷:");BFSTraverse(GL);return 0;
}
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0#define MAXSIZE 9 /* 存儲空間初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITY 65535typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼,如OK等 */
typedef int Boolean; /* Boolean是布爾類型,其值是TRUE或FALSE */typedef char VertexType; /* 頂點類型應由用戶定義 */
typedef int EdgeType; /* 邊上的權(quán)值類型應由用戶定義 *//* 鄰接矩陣結(jié)構(gòu) */
typedef struct
{VertexType vexs[MAXVEX]; /* 頂點表 */EdgeType arc[MAXVEX][MAXVEX];/* 鄰接矩陣,可看作邊表 */int numVertexes, numEdges; /* 圖中當前的頂點數(shù)和邊數(shù) */
}MGraph;/* 鄰接表結(jié)構(gòu)****************** */
typedef struct EdgeNode /* 邊表結(jié)點 */
{int adjvex; /* 鄰接點域,存儲該頂點對應的下標 */int weight; /* 用于存儲權(quán)值,對于非網(wǎng)圖可以不需要 */struct EdgeNode *next; /* 鏈域,指向下一個鄰接點 */
}EdgeNode;typedef struct VertexNode /* 頂點表結(jié)點 */
{int in; /* 頂點入度 */char data; /* 頂點域,存儲頂點信息 */EdgeNode *firstedge;/* 邊表頭指針 */
}VertexNode, AdjList[MAXVEX];typedef struct
{AdjList adjList; int numVertexes,numEdges; /* 圖中當前頂點數(shù)和邊數(shù) */
}graphAdjList,*GraphAdjList;
/* **************************** *//* 用到的隊列結(jié)構(gòu)與函數(shù)********************************** */
/* 循環(huán)隊列的順序存儲結(jié)構(gòu) */
typedef struct
{int data[MAXSIZE];int front; /* 頭指針 */int rear; /* 尾指針,若隊列不空,指向隊列尾元素的下一個位置 */
}Queue;/* 初始化一個空隊列Q */
Status InitQueue(Queue *Q)
{Q->front=0;Q->rear=0;return OK;
}/* 若隊列Q為空隊列,則返回TRUE,否則返回FALSE */
Status QueueEmpty(Queue Q)
{ if(Q.front==Q.rear) /* 隊列空的標志 */return TRUE;elsereturn FALSE;
}/* 若隊列未滿,則插入元素e為Q新的隊尾元素 */
Status EnQueue(Queue *Q,int e)
{if ((Q->rear+1)%MAXSIZE == Q->front) /* 隊列滿的判斷 */return ERROR;Q->data[Q->rear]=e; /* 將元素e賦值給隊尾 */Q->rear=(Q->rear+1)%MAXSIZE;/* rear指針向后移一位置, *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK;
}/* 若隊列不空,則刪除Q中隊頭元素,用e返回其值 */
Status DeQueue(Queue *Q,int *e)
{if (Q->front == Q->rear) /* 隊列空的判斷 */return ERROR;*e=Q->data[Q->front]; /* 將隊頭元素賦值給e */Q->front=(Q->front+1)%MAXSIZE; /* front指針向后移一位置, *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK;
}
/* ****************************************************** */void CreateMGraph(MGraph *G)
{int i, j;G->numEdges=15;G->numVertexes=9;/* 讀入頂點信息,建立頂點表 */ G->vexs[0]='A';G->vexs[1]='B';G->vexs[2]='C';G->vexs[3]='D';G->vexs[4]='E';G->vexs[5]='F';G->vexs[6]='G';G->vexs[7]='H';G->vexs[8]='I';for (i = 0; i < G->numVertexes; i++)/* 初始化圖 */{for ( j = 0; j < G->numVertexes; j++){G->arc[i][j]=0;}}G->arc[0][1]=1;G->arc[0][5]=1;G->arc[1][2]=1; G->arc[1][8]=1; G->arc[1][6]=1; G->arc[2][3]=1; G->arc[2][8]=1; G->arc[3][4]=1;G->arc[3][7]=1;G->arc[3][6]=1;G->arc[3][8]=1;G->arc[4][5]=1;G->arc[4][7]=1;G->arc[5][6]=1; G->arc[6][7]=1; for(i = 0; i < G->numVertexes; i++){for(j = i; j < G->numVertexes; j++){G->arc[j][i] =G->arc[i][j];}}}/* 利用鄰接矩陣構(gòu)建鄰接表 */
void CreateALGraph(MGraph G,GraphAdjList *GL)
{int i,j;EdgeNode *e;*GL = (GraphAdjList)malloc(sizeof(graphAdjList));(*GL)->numVertexes=G.numVertexes;(*GL)->numEdges=G.numEdges;for(i= 0;i <G.numVertexes;i++) /* 讀入頂點信息,建立頂點表 */ {(*GL)->adjList[i].in=0;(*GL)->adjList[i].data=G.vexs[i];(*GL)->adjList[i].firstedge=NULL; /* 將邊表置為空表 */}for(i=0;i<G.numVertexes;i++) /* 建立邊表 */{ for(j=0;j<G.numVertexes;j++){if (G.arc[i][j]==1){e=(EdgeNode *)malloc(sizeof(EdgeNode));e->adjvex=j; /* 鄰接序號為j */ e->next=(*GL)->adjList[i].firstedge; /* 將當前頂點上的指向的結(jié)點指針賦值給e */(*GL)->adjList[i].firstedge=e; /* 將當前頂點的指針指向e */ (*GL)->adjList[j].in++;}}}}Boolean visited[MAXSIZE]; /* 訪問標志的數(shù)組 *//* 鄰接表的深度優(yōu)先遞歸算法 */
void DFS(GraphAdjList GL, int i)
{EdgeNode *p;visited[i] = TRUE;printf("%c ",GL->adjList[i].data);/* 打印頂點,也可以其它操作 */p = GL->adjList[i].firstedge;while(p){if(!visited[p->adjvex])DFS(GL, p->adjvex);/* 對為訪問的鄰接頂點遞歸調(diào)用 */p = p->next;}
}/* 鄰接表的深度遍歷操作 */
void DFSTraverse(GraphAdjList GL)
{int i;for(i = 0; i < GL->numVertexes; i++)visited[i] = FALSE; /* 初始所有頂點狀態(tài)都是未訪問過狀態(tài) */for(i = 0; i < GL->numVertexes; i++)if(!visited[i]) /* 對未訪問過的頂點調(diào)用DFS,若是連通圖,只會執(zhí)行一次 */ DFS(GL, i);
}/* 鄰接表的廣度遍歷算法 */
void BFSTraverse(GraphAdjList GL)
{int i;EdgeNode *p;Queue Q;for(i = 0; i < GL->numVertexes; i++)visited[i] = FALSE;InitQueue(&Q);for(i = 0; i < GL->numVertexes; i++){if (!visited[i]){visited[i]=TRUE;printf("%c ",GL->adjList[i].data);/* 打印頂點,也可以其它操作 */EnQueue(&Q,i);while(!QueueEmpty(Q)){DeQueue(&Q,&i);p = GL->adjList[i].firstedge; /* 找到當前頂點的邊表鏈表頭指針 */while(p){if(!visited[p->adjvex]) /* 若此頂點未被訪問 */{visited[p->adjvex]=TRUE;printf("%c ",GL->adjList[p->adjvex].data);EnQueue(&Q,p->adjvex); /* 將此頂點入隊列 */}p = p->next; /* 指針指向下一個鄰接點 */}}}}
}int main(void)
{ MGraph G; GraphAdjList GL; CreateMGraph(&G);CreateALGraph(G,&GL);printf("\n深度遍歷:");DFSTraverse(GL);printf("\n廣度遍歷:");BFSTraverse(GL);return 0;
}#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0#define MAXSIZE 9 /* 存儲空間初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITY 65535typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼,如OK等 */
typedef int Boolean; /* Boolean是布爾類型,其值是TRUE或FALSE */typedef char VertexType; /* 頂點類型應由用戶定義 */
typedef int EdgeType; /* 邊上的權(quán)值類型應由用戶定義 *//* 鄰接矩陣結(jié)構(gòu) */
typedef struct
{VertexType vexs[MAXVEX]; /* 頂點表 */EdgeType arc[MAXVEX][MAXVEX];/* 鄰接矩陣,可看作邊表 */int numVertexes, numEdges; /* 圖中當前的頂點數(shù)和邊數(shù) */
}MGraph;/* 鄰接表結(jié)構(gòu)****************** */
typedef struct EdgeNode /* 邊表結(jié)點 */
{int adjvex; /* 鄰接點域,存儲該頂點對應的下標 */int weight; /* 用于存儲權(quán)值,對于非網(wǎng)圖可以不需要 */struct EdgeNode *next; /* 鏈域,指向下一個鄰接點 */
}EdgeNode;typedef struct VertexNode /* 頂點表結(jié)點 */
{int in; /* 頂點入度 */char data; /* 頂點域,存儲頂點信息 */EdgeNode *firstedge;/* 邊表頭指針 */
}VertexNode, AdjList[MAXVEX];typedef struct
{AdjList adjList; int numVertexes,numEdges; /* 圖中當前頂點數(shù)和邊數(shù) */
}graphAdjList,*GraphAdjList;
/* **************************** *//* 用到的隊列結(jié)構(gòu)與函數(shù)********************************** */
/* 循環(huán)隊列的順序存儲結(jié)構(gòu) */
typedef struct
{int data[MAXSIZE];int front; /* 頭指針 */int rear; /* 尾指針,若隊列不空,指向隊列尾元素的下一個位置 */
}Queue;/* 初始化一個空隊列Q */
Status InitQueue(Queue *Q)
{Q->front=0;Q->rear=0;return OK;
}/* 若隊列Q為空隊列,則返回TRUE,否則返回FALSE */
Status QueueEmpty(Queue Q)
{ if(Q.front==Q.rear) /* 隊列空的標志 */return TRUE;elsereturn FALSE;
}/* 若隊列未滿,則插入元素e為Q新的隊尾元素 */
Status EnQueue(Queue *Q,int e)
{if ((Q->rear+1)%MAXSIZE == Q->front) /* 隊列滿的判斷 */return ERROR;Q->data[Q->rear]=e; /* 將元素e賦值給隊尾 */Q->rear=(Q->rear+1)%MAXSIZE;/* rear指針向后移一位置, *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK;
}/* 若隊列不空,則刪除Q中隊頭元素,用e返回其值 */
Status DeQueue(Queue *Q,int *e)
{if (Q->front == Q->rear) /* 隊列空的判斷 */return ERROR;*e=Q->data[Q->front]; /* 將隊頭元素賦值給e */Q->front=(Q->front+1)%MAXSIZE; /* front指針向后移一位置, *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK;
}
/* ****************************************************** */void CreateMGraph(MGraph *G)
{int i, j;G->numEdges=15;G->numVertexes=9;/* 讀入頂點信息,建立頂點表 */ G->vexs[0]='A';G->vexs[1]='B';G->vexs[2]='C';G->vexs[3]='D';G->vexs[4]='E';G->vexs[5]='F';G->vexs[6]='G';G->vexs[7]='H';G->vexs[8]='I';for (i = 0; i < G->numVertexes; i++)/* 初始化圖 */{for ( j = 0; j < G->numVertexes; j++){G->arc[i][j]=0;}}G->arc[0][1]=1;G->arc[0][5]=1;G->arc[1][2]=1; G->arc[1][8]=1; G->arc[1][6]=1; G->arc[2][3]=1; G->arc[2][8]=1; G->arc[3][4]=1;G->arc[3][7]=1;G->arc[3][6]=1;G->arc[3][8]=1;G->arc[4][5]=1;G->arc[4][7]=1;G->arc[5][6]=1; G->arc[6][7]=1; for(i = 0; i < G->numVertexes; i++){for(j = i; j < G->numVertexes; j++){G->arc[j][i] =G->arc[i][j];}}}/* 利用鄰接矩陣構(gòu)建鄰接表 */
void CreateALGraph(MGraph G,GraphAdjList *GL)
{int i,j;EdgeNode *e;*GL = (GraphAdjList)malloc(sizeof(graphAdjList));(*GL)->numVertexes=G.numVertexes;(*GL)->numEdges=G.numEdges;for(i= 0;i <G.numVertexes;i++) /* 讀入頂點信息,建立頂點表 */ {(*GL)->adjList[i].in=0;(*GL)->adjList[i].data=G.vexs[i];(*GL)->adjList[i].firstedge=NULL; /* 將邊表置為空表 */}for(i=0;i<G.numVertexes;i++) /* 建立邊表 */{ for(j=0;j<G.numVertexes;j++){if (G.arc[i][j]==1){e=(EdgeNode *)malloc(sizeof(EdgeNode));e->adjvex=j; /* 鄰接序號為j */ e->next=(*GL)->adjList[i].firstedge; /* 將當前頂點上的指向的結(jié)點指針賦值給e */(*GL)->adjList[i].firstedge=e; /* 將當前頂點的指針指向e */ (*GL)->adjList[j].in++;}}}}Boolean visited[MAXSIZE]; /* 訪問標志的數(shù)組 *//* 鄰接表的深度優(yōu)先遞歸算法 */
void DFS(GraphAdjList GL, int i)
{EdgeNode *p;visited[i] = TRUE;printf("%c ",GL->adjList[i].data);/* 打印頂點,也可以其它操作 */p = GL->adjList[i].firstedge;while(p){if(!visited[p->adjvex])DFS(GL, p->adjvex);/* 對為訪問的鄰接頂點遞歸調(diào)用 */p = p->next;}
}/* 鄰接表的深度遍歷操作 */
void DFSTraverse(GraphAdjList GL)
{int i;for(i = 0; i < GL->numVertexes; i++)visited[i] = FALSE; /* 初始所有頂點狀態(tài)都是未訪問過狀態(tài) */for(i = 0; i < GL->numVertexes; i++)if(!visited[i]) /* 對未訪問過的頂點調(diào)用DFS,若是連通圖,只會執(zhí)行一次 */ DFS(GL, i);
}/* 鄰接表的廣度遍歷算法 */
void BFSTraverse(GraphAdjList GL)
{int i;EdgeNode *p;Queue Q;for(i = 0; i < GL->numVertexes; i++)visited[i] = FALSE;InitQueue(&Q);for(i = 0; i < GL->numVertexes; i++){if (!visited[i]){visited[i]=TRUE;printf("%c ",GL->adjList[i].data);/* 打印頂點,也可以其它操作 */EnQueue(&Q,i);while(!QueueEmpty(Q)){DeQueue(&Q,&i);p = GL->adjList[i].firstedge; /* 找到當前頂點的邊表鏈表頭指針 */while(p){if(!visited[p->adjvex]) /* 若此頂點未被訪問 */{visited[p->adjvex]=TRUE;printf("%c ",GL->adjList[p->adjvex].data);EnQueue(&Q,p->adjvex); /* 將此頂點入隊列 */}p = p->next; /* 指針指向下一個鄰接點 */}}}}
}int main(void)
{ MGraph G; GraphAdjList GL; CreateMGraph(&G);CreateALGraph(G,&GL);printf("\n深度遍歷:");DFSTraverse(GL);printf("\n廣度遍歷:");BFSTraverse(GL);return 0;
}
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0#define MAXSIZE 9 /* 存儲空間初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITY 65535typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼,如OK等 */
typedef int Boolean; /* Boolean是布爾類型,其值是TRUE或FALSE */typedef char VertexType; /* 頂點類型應由用戶定義 */
typedef int EdgeType; /* 邊上的權(quán)值類型應由用戶定義 *//* 鄰接矩陣結(jié)構(gòu) */
typedef struct
{VertexType vexs[MAXVEX]; /* 頂點表 */EdgeType arc[MAXVEX][MAXVEX];/* 鄰接矩陣,可看作邊表 */int numVertexes, numEdges; /* 圖中當前的頂點數(shù)和邊數(shù) */
}MGraph;/* 鄰接表結(jié)構(gòu)****************** */
typedef struct EdgeNode /* 邊表結(jié)點 */
{int adjvex; /* 鄰接點域,存儲該頂點對應的下標 */int weight; /* 用于存儲權(quán)值,對于非網(wǎng)圖可以不需要 */struct EdgeNode *next; /* 鏈域,指向下一個鄰接點 */
}EdgeNode;typedef struct VertexNode /* 頂點表結(jié)點 */
{int in; /* 頂點入度 */char data; /* 頂點域,存儲頂點信息 */EdgeNode *firstedge;/* 邊表頭指針 */
}VertexNode, AdjList[MAXVEX];typedef struct
{AdjList adjList; int numVertexes,numEdges; /* 圖中當前頂點數(shù)和邊數(shù) */
}graphAdjList,*GraphAdjList;
/* **************************** *//* 用到的隊列結(jié)構(gòu)與函數(shù)********************************** */
/* 循環(huán)隊列的順序存儲結(jié)構(gòu) */
typedef struct
{int data[MAXSIZE];int front; /* 頭指針 */int rear; /* 尾指針,若隊列不空,指向隊列尾元素的下一個位置 */
}Queue;/* 初始化一個空隊列Q */
Status InitQueue(Queue *Q)
{Q->front=0;Q->rear=0;return OK;
}/* 若隊列Q為空隊列,則返回TRUE,否則返回FALSE */
Status QueueEmpty(Queue Q)
{ if(Q.front==Q.rear) /* 隊列空的標志 */return TRUE;elsereturn FALSE;
}/* 若隊列未滿,則插入元素e為Q新的隊尾元素 */
Status EnQueue(Queue *Q,int e)
{if ((Q->rear+1)%MAXSIZE == Q->front) /* 隊列滿的判斷 */return ERROR;Q->data[Q->rear]=e; /* 將元素e賦值給隊尾 */Q->rear=(Q->rear+1)%MAXSIZE;/* rear指針向后移一位置, *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK;
}/* 若隊列不空,則刪除Q中隊頭元素,用e返回其值 */
Status DeQueue(Queue *Q,int *e)
{if (Q->front == Q->rear) /* 隊列空的判斷 */return ERROR;*e=Q->data[Q->front]; /* 將隊頭元素賦值給e */Q->front=(Q->front+1)%MAXSIZE; /* front指針向后移一位置, *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK;
}
/* ****************************************************** */void CreateMGraph(MGraph *G)
{int i, j;G->numEdges=15;G->numVertexes=9;/* 讀入頂點信息,建立頂點表 */ G->vexs[0]='A';G->vexs[1]='B';G->vexs[2]='C';G->vexs[3]='D';G->vexs[4]='E';G->vexs[5]='F';G->vexs[6]='G';G->vexs[7]='H';G->vexs[8]='I';for (i = 0; i < G->numVertexes; i++)/* 初始化圖 */{for ( j = 0; j < G->numVertexes; j++){G->arc[i][j]=0;}}G->arc[0][1]=1;G->arc[0][5]=1;G->arc[1][2]=1; G->arc[1][8]=1; G->arc[1][6]=1; G->arc[2][3]=1; G->arc[2][8]=1; G->arc[3][4]=1;G->arc[3][7]=1;G->arc[3][6]=1;G->arc[3][8]=1;G->arc[4][5]=1;G->arc[4][7]=1;G->arc[5][6]=1; G->arc[6][7]=1; for(i = 0; i < G->numVertexes; i++){for(j = i; j < G->numVertexes; j++){G->arc[j][i] =G->arc[i][j];}}}/* 利用鄰接矩陣構(gòu)建鄰接表 */
void CreateALGraph(MGraph G,GraphAdjList *GL)
{int i,j;EdgeNode *e;*GL = (GraphAdjList)malloc(sizeof(graphAdjList));(*GL)->numVertexes=G.numVertexes;(*GL)->numEdges=G.numEdges;for(i= 0;i <G.numVertexes;i++) /* 讀入頂點信息,建立頂點表 */ {(*GL)->adjList[i].in=0;(*GL)->adjList[i].data=G.vexs[i];(*GL)->adjList[i].firstedge=NULL; /* 將邊表置為空表 */}for(i=0;i<G.numVertexes;i++) /* 建立邊表 */{ for(j=0;j<G.numVertexes;j++){if (G.arc[i][j]==1){e=(EdgeNode *)malloc(sizeof(EdgeNode));e->adjvex=j; /* 鄰接序號為j */ e->next=(*GL)->adjList[i].firstedge; /* 將當前頂點上的指向的結(jié)點指針賦值給e */(*GL)->adjList[i].firstedge=e; /* 將當前頂點的指針指向e */ (*GL)->adjList[j].in++;}}}}Boolean visited[MAXSIZE]; /* 訪問標志的數(shù)組 *//* 鄰接表的深度優(yōu)先遞歸算法 */
void DFS(GraphAdjList GL, int i)
{EdgeNode *p;visited[i] = TRUE;printf("%c ",GL->adjList[i].data);/* 打印頂點,也可以其它操作 */p = GL->adjList[i].firstedge;while(p){if(!visited[p->adjvex])DFS(GL, p->adjvex);/* 對為訪問的鄰接頂點遞歸調(diào)用 */p = p->next;}
}/* 鄰接表的深度遍歷操作 */
void DFSTraverse(GraphAdjList GL)
{int i;for(i = 0; i < GL->numVertexes; i++)visited[i] = FALSE; /* 初始所有頂點狀態(tài)都是未訪問過狀態(tài) */for(i = 0; i < GL->numVertexes; i++)if(!visited[i]) /* 對未訪問過的頂點調(diào)用DFS,若是連通圖,只會執(zhí)行一次 */ DFS(GL, i);
}/* 鄰接表的廣度遍歷算法 */
void BFSTraverse(GraphAdjList GL)
{int i;EdgeNode *p;Queue Q;for(i = 0; i < GL->numVertexes; i++)visited[i] = FALSE;InitQueue(&Q);for(i = 0; i < GL->numVertexes; i++){if (!visited[i]){visited[i]=TRUE;printf("%c ",GL->adjList[i].data);/* 打印頂點,也可以其它操作 */EnQueue(&Q,i);while(!QueueEmpty(Q)){DeQueue(&Q,&i);p = GL->adjList[i].firstedge; /* 找到當前頂點的邊表鏈表頭指針 */while(p){if(!visited[p->adjvex]) /* 若此頂點未被訪問 */{visited[p->adjvex]=TRUE;printf("%c ",GL->adjList[p->adjvex].data);EnQueue(&Q,p->adjvex); /* 將此頂點入隊列 */}p = p->next; /* 指針指向下一個鄰接點 */}}}}
}int main(void)
{ MGraph G; GraphAdjList GL; CreateMGraph(&G);CreateALGraph(G,&GL);printf("\n深度遍歷:");DFSTraverse(GL);printf("\n廣度遍歷:");BFSTraverse(GL);return 0;
}
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0#define MAXSIZE 9 /* 存儲空間初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITY 65535typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼,如OK等 */
typedef int Boolean; /* Boolean是布爾類型,其值是TRUE或FALSE */typedef char VertexType; /* 頂點類型應由用戶定義 */
typedef int EdgeType; /* 邊上的權(quán)值類型應由用戶定義 *//* 鄰接矩陣結(jié)構(gòu) */
typedef struct
{VertexType vexs[MAXVEX]; /* 頂點表 */EdgeType arc[MAXVEX][MAXVEX];/* 鄰接矩陣,可看作邊表 */int numVertexes, numEdges; /* 圖中當前的頂點數(shù)和邊數(shù) */
}MGraph;/* 鄰接表結(jié)構(gòu)****************** */
typedef struct EdgeNode /* 邊表結(jié)點 */
{int adjvex; /* 鄰接點域,存儲該頂點對應的下標 */int weight; /* 用于存儲權(quán)值,對于非網(wǎng)圖可以不需要 */struct EdgeNode *next; /* 鏈域,指向下一個鄰接點 */
}EdgeNode;typedef struct VertexNode /* 頂點表結(jié)點 */
{int in; /* 頂點入度 */char data; /* 頂點域,存儲頂點信息 */EdgeNode *firstedge;/* 邊表頭指針 */
}VertexNode, AdjList[MAXVEX];typedef struct
{AdjList adjList; int numVertexes,numEdges; /* 圖中當前頂點數(shù)和邊數(shù) */
}graphAdjList,*GraphAdjList;
/* **************************** *//* 用到的隊列結(jié)構(gòu)與函數(shù)********************************** */
/* 循環(huán)隊列的順序存儲結(jié)構(gòu) */
typedef struct
{int data[MAXSIZE];int front; /* 頭指針 */int rear; /* 尾指針,若隊列不空,指向隊列尾元素的下一個位置 */
}Queue;/* 初始化一個空隊列Q */
Status InitQueue(Queue *Q)
{Q->front=0;Q->rear=0;return OK;
}/* 若隊列Q為空隊列,則返回TRUE,否則返回FALSE */
Status QueueEmpty(Queue Q)
{ if(Q.front==Q.rear) /* 隊列空的標志 */return TRUE;elsereturn FALSE;
}/* 若隊列未滿,則插入元素e為Q新的隊尾元素 */
Status EnQueue(Queue *Q,int e)
{if ((Q->rear+1)%MAXSIZE == Q->front) /* 隊列滿的判斷 */return ERROR;Q->data[Q->rear]=e; /* 將元素e賦值給隊尾 */Q->rear=(Q->rear+1)%MAXSIZE;/* rear指針向后移一位置, *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK;
}/* 若隊列不空,則刪除Q中隊頭元素,用e返回其值 */
Status DeQueue(Queue *Q,int *e)
{if (Q->front == Q->rear) /* 隊列空的判斷 */return ERROR;*e=Q->data[Q->front]; /* 將隊頭元素賦值給e */Q->front=(Q->front+1)%MAXSIZE; /* front指針向后移一位置, *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK;
}
/* ****************************************************** */void CreateMGraph(MGraph *G)
{int i, j;G->numEdges=15;G->numVertexes=9;/* 讀入頂點信息,建立頂點表 */ G->vexs[0]='A';G->vexs[1]='B';G->vexs[2]='C';G->vexs[3]='D';G->vexs[4]='E';G->vexs[5]='F';G->vexs[6]='G';G->vexs[7]='H';G->vexs[8]='I';for (i = 0; i < G->numVertexes; i++)/* 初始化圖 */{for ( j = 0; j < G->numVertexes; j++){G->arc[i][j]=0;}}G->arc[0][1]=1;G->arc[0][5]=1;G->arc[1][2]=1; G->arc[1][8]=1; G->arc[1][6]=1; G->arc[2][3]=1; G->arc[2][8]=1; G->arc[3][4]=1;G->arc[3][7]=1;G->arc[3][6]=1;G->arc[3][8]=1;G->arc[4][5]=1;G->arc[4][7]=1;G->arc[5][6]=1; G->arc[6][7]=1; for(i = 0; i < G->numVertexes; i++){for(j = i; j < G->numVertexes; j++){G->arc[j][i] =G->arc[i][j];}}}/* 利用鄰接矩陣構(gòu)建鄰接表 */
void CreateALGraph(MGraph G,GraphAdjList *GL)
{int i,j;EdgeNode *e;*GL = (GraphAdjList)malloc(sizeof(graphAdjList));(*GL)->numVertexes=G.numVertexes;(*GL)->numEdges=G.numEdges;for(i= 0;i <G.numVertexes;i++) /* 讀入頂點信息,建立頂點表 */ {(*GL)->adjList[i].in=0;(*GL)->adjList[i].data=G.vexs[i];(*GL)->adjList[i].firstedge=NULL; /* 將邊表置為空表 */}for(i=0;i<G.numVertexes;i++) /* 建立邊表 */{ for(j=0;j<G.numVertexes;j++){if (G.arc[i][j]==1){e=(EdgeNode *)malloc(sizeof(EdgeNode));e->adjvex=j; /* 鄰接序號為j */ e->next=(*GL)->adjList[i].firstedge; /* 將當前頂點上的指向的結(jié)點指針賦值給e */(*GL)->adjList[i].firstedge=e; /* 將當前頂點的指針指向e */ (*GL)->adjList[j].in++;}}}}Boolean visited[MAXSIZE]; /* 訪問標志的數(shù)組 *//* 鄰接表的深度優(yōu)先遞歸算法 */
void DFS(GraphAdjList GL, int i)
{EdgeNode *p;visited[i] = TRUE;printf("%c ",GL->adjList[i].data);/* 打印頂點,也可以其它操作 */p = GL->adjList[i].firstedge;while(p){if(!visited[p->adjvex])DFS(GL, p->adjvex);/* 對為訪問的鄰接頂點遞歸調(diào)用 */p = p->next;}
}/* 鄰接表的深度遍歷操作 */
void DFSTraverse(GraphAdjList GL)
{int i;for(i = 0; i < GL->numVertexes; i++)visited[i] = FALSE; /* 初始所有頂點狀態(tài)都是未訪問過狀態(tài) */for(i = 0; i < GL->numVertexes; i++)if(!visited[i]) /* 對未訪問過的頂點調(diào)用DFS,若是連通圖,只會執(zhí)行一次 */ DFS(GL, i);
}/* 鄰接表的廣度遍歷算法 */
void BFSTraverse(GraphAdjList GL)
{int i;EdgeNode *p;Queue Q;for(i = 0; i < GL->numVertexes; i++)visited[i] = FALSE;InitQueue(&Q);for(i = 0; i < GL->numVertexes; i++){if (!visited[i]){visited[i]=TRUE;printf("%c ",GL->adjList[i].data);/* 打印頂點,也可以其它操作 */EnQueue(&Q,i);while(!QueueEmpty(Q)){DeQueue(&Q,&i);p = GL->adjList[i].firstedge; /* 找到當前頂點的邊表鏈表頭指針 */while(p){if(!visited[p->adjvex]) /* 若此頂點未被訪問 */{visited[p->adjvex]=TRUE;printf("%c ",GL->adjList[p->adjvex].data);EnQueue(&Q,p->adjvex); /* 將此頂點入隊列 */}p = p->next; /* 指針指向下一個鄰接點 */}}}}
}int main(void)
{ MGraph G; GraphAdjList GL; CreateMGraph(&G);CreateALGraph(G,&GL);printf("\n深度遍歷:");DFSTraverse(GL);printf("\n廣度遍歷:");BFSTraverse(GL);return 0;
}
《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀
《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀
總結(jié)
- 上一篇： 邻接矩阵的图遍历
- 下一篇： 怎么求人眼图像中的噪声