你都如何回憶我、2011.12.12 回答

資料結構這個東西，你的定義不同寫出來的東西也就不同了，好吧，這是我寫的一個東西，寫的有點倉促有點醜哈····

#define MAXSIZE 100

typedef char elemtype；

typedef struct arc

{

int index；

arc *nextarc；

}ARCNODE，*ARC；

typedef struct VER

{

elemtype data；

ARC firstarc；

}VERNODE；

typedef struct

{

VERNODE vertex［MAXSIZE］；

int numVer；

int numArc；

}ADJGRAPH；

//遞迴實現深度優先

void dfs（ADJGRAPH *g，int pos，int *visit，void （*pf）（elemtype））

{

ARCNODE *p = g->vertex［pos］。firstarc；

visit［pos］ = 1；

pf（g->vertex［pos］。data）；

while（p）

{

if （！visit［p->index］）

{

dfs（g，p->index，visit）；

}

p = p->nextarc；

}

}

void dfs_traverse（ADJGRAPH *g，int pos）

{

int *visit = （int *）malloc（sizeof（int）*（g->numVer））；

for （int i = 0；inumVer；i++） { visit［i］ = 0； } dfs（g，pos，visit）； for （int i = 0；inumVer；i++） { if （！visit［i］） { dfs（g，i，visit）； } } } //棧實現深度優先 void dfs_traverse_inrecursion（ADJGRAPH *g，void （*pf）（elemtype）） { ARCNODE *p； ARCNODE *stack［MAXSIZE］；//鏈棧更好 int visit［MAXSIZE］ = {0}； int top = 0； for （int pos = 0；pos < g->numVer；pos++） { if （！visit［pos］） { p = g->vertex［pos］。firstarc； pf（g->vertex［pos］。data）； visit［pos］ = 1； while （p||top） { while （p&&！visit［p->index］） { pf（g->vertex［p->index］。data）； visit［p->index］ = 1； stack［top++］ = p； p = g->vertex［p->index］。firstarc； } if（top） p = stack［——top］->nextarc； else p = p->nextarc； } } } } //廣度優先 void bfs_traverse（ADJGRAPH *g，void （*pf）（elemtype）） { ARCNODE *queue［MAXSIZE］；//鏈佇列更好 ARCNODE *p； int rear = 0，front = 0； int visit［MAXSIZE］ = {0}； for（int pos = 0；posnumVer；pos++） { p = g->vertex［pos］。firstarc； if（！visit［pos］） { pf（g->vertex［pos］。data）； visit［pos］ = 1； } while（p||rear ！= front） { while（p） { queue［front++］ = p； p = p->nextarc； } if（rear ！= front） { p = queue［rear++］； if（！visit［p->index］） { pf（g->vertex［p->index］。data）； visit［p->index］ = 1； } p = g->vertex［p->index］。firstarc； } else p = g->vertex［p->index］。firstarc； } } }

花落魚眠2011.12.12 回答

（1） 圖的建立，按採用鄰接表作為儲存結構。

（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=0；iif（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=0；i { scanf（“%s”，ga。vexs［i］。szname）； ga。vexs［i］。firstarc=null； } for（k=0；k { 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=0；v visited［v］=0； for（v=locatevex（ga，name）；k！=2；v=（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=0；v visited［v］=0； initqueue（q）； for（v=locatevex（ga，name）；k！=2；v=（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”）； }