Four problems with traversal of the map

Graph establishment, input example: Input the number for vexnum and arcnum: 8 9

Input8Char for vexs (use -Enter- to change): abcdefgh

Input9arc (Char -Enter- Char -Enter): 0: AB11

1: AC11

2: BD11

3: BE11

4: DH23

5: EH11

6: CF11

7: CG11

8: fg11

Matrix of traverses: 88 11 11 88 88 88 88 888 88 88 11 11 88 88 88 88 88 88 88 11 11 8888 11 88 88 88 88 88 2388 11 88 88 88 88 88 1188 88 11 88 88 88 11 8888 88 11 88 88 11 88 8888 88 88 23 11 88 88 Sales: Abdhecfg (adjacent matrix depth traversal results) actual graphics example: A b C D e f ------ g h (other is up and down) Code:

Brand class traversal of adjacent map

#include #include #include

#define infinity INT_MAX #define max_vertex_num 20

#define maxqsize 10 // Maximum queue length #define false 0 # Define true 1

Typedf int vrtype; typedef int status; typedef int rt QEleMType;

Typedef struct qlemtype * base; int around; @} sqqueue;

Typedef struct arcnode {int adjVex; struct arcnode * nextarc; arcNode;

Typedef struct vNode {vertextype data; arcNode * firstarc;} vNode, Adjlist [MAX_VERTEX_NUM];

Typedef struct {adjlist vertices; int usxun; arcnum;} algraph;

BOOL Visited [MAX_VERTEX_NUM]; Status (* VisitFunc) (INT V); int W;

void CreateGraph (ALGraph & G); void BFSTraverse (ALGraph G, Status (* Visit) (int v)); Status printGraph (int v); int FirstAdjVex (ALGraph G, int v); int NextAdjVex (ALGraph G, int v, INT W);

Status initQueue (SQQQueue &); SQQueue &, QelemType; Status Dequeue (Sqqueue &, QeleMType &); STATUS Queueempty (Sqqueue);

Void main (void) {

INT I; Algraph G; ArcNode * P; CreateGraph (g); for (i = 0; i "; cout << (g.vertices [p-> adjvex] .data); P = P-> NEXTARC;} cout << Endl;} bfstraverse (g, printgraph);} void creategraph (algraph & g) {INT i, j = 0, k = 0; char HAND, TIDE; ArcNode * p; cout << "Input the Number for vexnum and arcnum: "; cin >> g.Vexnum >> g.arcnum; cout << endl; cout <<" infut "<< g.vexnum <<" "" char for vexs: "; for (i = 0 i > G.Vertices [i] .data; cout << endl; for (i = 0; i > ;; cin >> Tide; while (hand! = g.vertices [j] .data) J ; while (Tide! = G.Vertices [K ] .data) k ; p = new arcNode; p-> adjgEx = j; p-> nextarc = g.vertices [j] .firstarc; g.vertices [k] .firstarc = p; p = new arcnode; p- > adjvex = k; p-> Nextarc = g.vertices [j] .firstarc; G.vertices [j] .firstarc = p; j = 0; k = 0; cout << endl;}}

Void Bfstraverse (Algraph G, Status (* V)) {sqqueue q; QELEMTYPE U;

INITQUEUE (Q);

For (int V = 0; V Adjvex]! = 1) Return P-> Adjvex; P = P-> Nextarc;} Return }

INT NEXTADJVEX (Algraph G, INT V, INT W) {ArcNode * p; p = g.vertices [v] .firstarc; while (p! = null) {if (Visited [P-> Adjvex]! = 1 && P -> Adjvex! = W) Return P-> Adjvex; P = P-> NEXTARC;} return 0;

Status PrintGraph (int V) {Printf ("% C", V 'A'); cout << endl; return 1;}

STATUS INTQUE (SQQueue & queue) {queue.base = (QELEMTYPE *) Malloc (MaxQsize * sizeof (QELEMTYPE)); if (! Queue.base) Return False; queue.front = queue.rear = 0;

Return True;}

////// Function Name: Enqueue // Function Description: Insert Element to Queue // Parameters: Sqqueue & Queue // Parameters: QEleMType Element // Return Value: Status //// Status Enqueue (Sqqueue & Queue, QELEMTYPE Element) {// Judgment is a queue IF ((Queue.rear 1)% maxqsize == queue.front) Return False; queue.base [queue.rear] = ELEMENT

Queue.rear = (queue.rear 1)% Maxqsize;

Return True;}

////// Function Name: DEQUEUE // Function Description: Delete Queue's Headjet // Parameters: Sqqueue & Queue // Parameters: QELEMTYPE & ELEMENT / / Return Value: status //// status Dequeue (Sqqueue & Queue , QELEMTYPE & ELEMENT) {// Judgment queue is empty if (Queue.Front == Queue.rear) Return False; element = queue.base [queue.front]; queue.front = (queue.front 1)% MaxQsize;} status queueempty (sqqueue queeue) {if (queue.front == queue.rear) Return False; else return

}

Depth traversal of adjacent map

#include #include #include

#define infinity INT_MAX #define max_vertex_num 20

Typedef int vrtype; typef char vertexType; typef int stat;

Typedef struct arcnode {int adjVex; struct arcnode * nextarc; arcNode;

Typedef struct vNode {vertextype data; arcNode * firstarc;} vNode, Adjlist [MAX_VERTEX_NUM];

Typedef struct {adjlist vertices; int usxun; arcnum;} algraph;

BOOL Visited [MAX_VERTEX_NUM]; Status (* VisitFunc) (INT V); int W;

void CreateGraph (ALGraph & G); void DFSTraverse (ALGraph G, Status (* Visit) (int v)); Status printGraph (int v); int FirstAdjVex (ALGraph G, int v); int NextAdjVex (ALGraph G, int v, INT W); Void DFS (Algraph G, INT V);

Void main (void) {

INT I; Algraph G; ArcNode * p; CreateGraph (g);

For (i = 0; i ; cout << (g.vertices [p-> adjvex] .data); p = p-> nextarc;} cout << Endl;} DFSTRAVERSE (G, Printgraph) } void creategraph (algraph & g) {INT I, J = 0, K = 0; char hand, TIDE; ArcNode * p; cout << "Input the number for vexnum and arcnum:"; cin >> g.Vexnum> > G.arcnum; cout << endl; cout << "input" << g.vexnum << "char for vexs:"; for (i = 0; i > G.Vertices [i] .data; cout << endl; for (i = 0; i > HAND; CIN >> TIDE; while (hand! = g.vertices [j] .data) j ; while (Tide! = g.vertices [k] .data) K ; p = new arcnode; p-> adjvex = J; p-> nextarc = g.vertices [j] .firstarc; g.vertices [k] .firstarc = p; p = new arcnode; p-> adjvex = k; p-> nextarc = g.vertices [j ] .firstarc; g.vertices [j] .firstarc = p; j = 0; k = 0; c OUT << Endl;}} void DFSTraverse (Algraph G, Status (* VISIT) (INT V) {Int J; VisitFunc = Visit; For (j = 0; j

Void DFS (Algraph G, INT V) {Visited [V] = 1; VisitFunc (V); for (w = firstadjvex (g, v); w; w = nextadjvex (g, v, w)) IF (! " [w]) DFS (g, w);} int firstadjvex (algraph g, int v) {arcNode * p; p = g.vertices [v] .firstarc; while (p! = null) {if (Visited [P -> adjgEx]! = 1) Return P-> Adjvex; P = P-> NEXTARC;} return 0;}

INT NEXTADJVEX (Algraph G, INT V, INT W) {ArcNode * p; p = g.vertices [v] .firstarc; while (p! = null) {if (Visited [P-> Adjvex]! = 1 && P -> Adjvex! = W) Return P-> Adjvex; P = P-> NEXTARC;} return 0;

Status PrintGraph (int V) {Printf ("% C", V 'A'); cout << endl; return 1;}

Brass traversal of adjacent matrices

#include #include #include

#define infinity INT_MAX #define max_vertex_num 20

#define maxqsize 10 // Maximum queue length #define false 0 # Define true 1

Typedef Int vrtype; typedef in vertextype; typef int status; typedef int te;

Typedef struct qlemtype * base; int around; @} sqqueue;

Typedef struct arccell {vrtype adj; infotype * info;} arccell, adjmaMatrix [max_vertex_num] [max_vertex_num];

TypedEf struct {vertextype vexs [max_vertex_num]; Adjmatrix Arcs; int VexNum, ArcNum;} mgraph;

BOOL Visited [MAX_VERTEX_NUM]; Status (* VisitFunc) (INT V); int W;

Void CreateGraph (MGraph & g); Void Bfstraverse (Mgraph G, Status (* V)); Status PrintGraph (int V); int firstadjvex (mgraph g, intv); int nextadjvex (Mgraph G, int V, INT W);

Status initQueue (SQQQueue &); SQQueue &, QelemType; Status Dequeue (Sqqueue &, QeleMType &); STATUS Queueempty (Sqqueue);

Void main (void) {INT I, J; MGRAPH G; CreateGraph (g); for (i = 0; i > g.vexnum >> g.arcnum; for (i = 0; i

COUT << Endl; cout << "INPUT" << g.vexnum << "CHAR for VEXS (Use -Enter- to change):"; for (i = 0; i > G.vexs [i]; cout << endl; cout << "INPUT" << g.arcnum << "arc (char -enter- char -enter- weigh):" << Endl; j = 0; k = 0; for (i = 0; i > hand; cin >> Tide; cin >> weigh; while (hand! = G.vexs [j]) J ; while (Tide! = g.vexs [k]) k ; g.Arcs [j] [k] .adj = weigh; g.ARCS [K] [J] .adj = weigh; j = 0; k = 0; cout << end1;}}

Void Bfstraverse (Mgraph G, STATUS (* VISIT) (INT V)) {

Sqqueue q; QELEMTYPE U;

INITQUEUE (Q);

For (int V = 0; V

INT firstadjvex (mgraph g, int v) {int J; for (j = 0; j

Status PrintGraph (int V) {Printf ("% C", V 'A'); cout << endl; return 1;}

STATUS INTQUE (SQQueue & queue) {queue.base = (QELEMTYPE *) Malloc (MaxQsize * sizeof (QELEMTYPE)); if (! Queue.base) Return False; queue.front = queue.rear = 0;

Return True;}

////// Function Name: Enqueue // Function Description: Insert Element to Queue // Parameters: Sqqueue & Queue // Parameters: QEleMType Element // Return Value: Status //// Status Enqueue (Sqqueue & Queue, QELEMTYPE Element) {// Judgment is a queue IF ((Queue.rear 1)% maxqsize == queue.front) Return False; queue.base [queue.rear] = ELEMENT

Queue.rear = (queue.rear 1)% Maxqsize;

Return True;}

////// Function Name: DEQUEUE // Function Description: Delete Queue's Headjet // Parameters: Sqqueue & Queue // Parameters: QELEMTYPE & ELEMENT / / Return Value: status //// status Dequeue (Sqqueue & Queue , QELEMTYPE & ELEMENT) {// Judgment queue is empty if (Queue.Front == Queue.rear) Return False; element = queue.base [queue.front]; queue.front = (queue.front 1)% Maxqsize; Return True;}

Status Queueempty (Sqqueue Queue) {if (Queue.Front == Queue.rear) Return False; Else Return True;

}

Depth traversal of adjacent matrices

#include #include #include

#define infinity INT_MAX #define max_vertex_num 20

typedef int VRType; typedef int InfoType; typedef char VertexType; typedef int Status; typedef struct ArcCell {VRType adj; InfoType * info;} ArcCell, AdjMatrix [MAX_VERTEX_NUM] [MAX_VERTEX_NUM];

TypedEf struct {vertextype vexs [max_vertex_num]; Adjmatrix Arcs; int VexNum, ArcNum;} mgraph;

BOOL Visited [MAX_VERTEX_NUM]; Status (* VisitFunc) (INT V); int W;

Void CreateGraph (Mgraph & g); Void Dfstraverse (Mgraph G, Status (* VISIT); Status Printgraph (Int V); Int Firstadjvex (Mgraph G, INT V); Int NextAdjvex (Mgraph G, INT V, INT W); Void DFS (MGRAPH G, INT V);

Void main (void) {INT I, J; MGRAPH G; CreateGraph (g); for (i = 0; i > g.Vexnum >> G.arcnum

For (i = 0; i

COUT << Endl; cout << "INPUT" << g.vexnum << "CHAR for VEXS (Use -Enter- to change):"; for (i = 0; i > G.vexs [i]; cout << endl; cout << "INPUT" << g.arcnum << "arc (char -enter- char -enter- weigh):" << Endl; j = 0; k = 0; for (i = 0; i > hand; cin >> Tide; cin >> weigh; while (hand! = G.vexs [j]) J ; while (Tide! = g.vexs [k]) k ; g.Arcs [j] [k] .adj = weigh; g.ARCS [K] [J] .adj = weigh; j = 0; k = 0; cout << Endl;}} void Dfstraverse (mgraph g, status (* visit) (int V)) {Int j; Visitfunc = Visit; for (j = 0; j

Void DFS (Mgraph G, INT V) {

Visited [V] = 1; VisitFunc (V); for (w = firstadjvex (g, v); w; w = nextadjvex (g, v, w)) IF (! Visited [W]) DFS (g, w) }

INT firstadjvex (mgraph g, int v) {int J; for (j = 0; j

INT NEXTADJVEX (Mgraph G, INT V, INT W) {INT J; for (j = 0; j

Status PrintGraph (int V) {Printf ("% C", V 'A'); cout << endl; return 1;}