C語言數(shù)據(jù)結(jié)構(gòu)之圖的遍歷實(shí)例詳解
成都創(chuàng)新互聯(lián)公司服務(wù)項(xiàng)目包括洛浦網(wǎng)站建設(shè)、洛浦網(wǎng)站制作、洛浦網(wǎng)頁制作以及洛浦網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢(shì)、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，洛浦網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到洛浦省份的部分城市，未來相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！
輸入一組頂點(diǎn)，建立無向圖的鄰接矩陣。輸入一組頂點(diǎn)，建立有向圖的鄰接表。分別對(duì)無向圖和有向圖進(jìn)行DFS（深度優(yōu)先遍歷）和BFS（廣度優(yōu)先遍歷）。寫出深度優(yōu)先遍歷的遞歸和非遞歸算法。根據(jù)建立的有向圖，判斷該圖是否是有向無環(huán)圖，若是，則輸出其一種拓?fù)溆行蛐蛄小?/p>
實(shí)現(xiàn)代碼：
#include
#include
#define MAX 20
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct{
char data;
ArcNode *firstarc;
}AdjList[MAX];
typedef struct{
AdjList vertices;
int vexnum;
int arcnum;
}ALGraph;
typedef struct{
int *base;
int front,rear;
}CqQueue;
void InitQueue(CqQueue &Q)
{//初始化一個(gè)隊(duì)列
Q.base=(int*)malloc(MAX*sizeof(int));
Q.front=Q.rear=0;
}
int QueueEmpty(CqQueue Q)
{//判斷隊(duì)列是否為空
if(Q.rear==Q.front)
return 1;
return 0;
}
void EnQueue(CqQueue &Q,int e)
{//入隊(duì)操作
if((Q.rear+1)%MAX==Q.front)
return;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAX;
}
void DeQueue(CqQueue &Q,int &e)
{//出隊(duì)操作
if(Q.rear==Q.front)
return;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAX;
}
int LocateVex(ALGraph G,char v)
{//查找頂點(diǎn)v在圖G中的位置
for(int i=0;iadjvex=j;
s->nextarc=NULL;
if(!G.vertices[i].firstarc)
G.vertices[i].firstarc=s;
else{
p=G.vertices[i].firstarc;
while(p->nextarc)
p=p->nextarc;
p->nextarc=s;
}
s=(ArcNode*)malloc(sizeof(ArcNode));
s->adjvex=i;
s->nextarc=NULL;
if(!G.vertices[j].firstarc)
G.vertices[j].firstarc=s;
else{
p=G.vertices[j].firstarc;
while(p->nextarc)
p=p->nextarc;
p->nextarc=s;
}
}
}
int visited[MAX];
void DFS(ALGraph G,int v)
{//從頂點(diǎn)v開始對(duì)圖G進(jìn)行深度優(yōu)先搜索
ArcNode *p;
printf("%3c",G.vertices[v].data);
visited[v]=1;
for(p=G.vertices[v].firstarc;p;p=p->nextarc)
if(!visited[p->adjvex])
DFS(G,p->adjvex);
}
void DFSTraverse(ALGraph G)
{//對(duì)用鄰接表存儲(chǔ)的無向圖G進(jìn)行深度優(yōu)先遍歷
int v;
for(v=0;vnextarc)
if(!visited[p->adjvex]){
printf("%3c",G.vertices[p->adjvex].data);
visited[p->adjvex]=1;
EnQueue(Q,p->adjvex);
}
}
}
}
int main(){
ALGraph G;
printf("建立無向圖的鄰接表：\n");
CreateAdjList(G);
printf("無向圖的深度優(yōu)先遍歷序列如下：\n");
DFSTraverse(G);
printf("\n\n無向圖的廣度優(yōu)先遍歷序列如下：\n");
BFSTraverse(G);
printf("\n");
return 0;
}
感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
網(wǎng)頁標(biāo)題：C語言數(shù)據(jù)結(jié)構(gòu)之圖的遍歷實(shí)例詳解
分享網(wǎng)址：
http://weahome.cn/article/ihdjig.html
重慶分公司
重慶分公司
