데이터 구조 - 깊이 우선 검색 지점 에서 지점 까지 의 일반 경로
35991 단어 데이터 구조
#include
<
iostream
>
using
namespace
std;
#include
<
stdio.h
>
#include
<
stdlib.h
>
#define
OK 1
#define
NULL 0
#define
MAX_VERTEX_NUM 20
//
typedef
char
VertexType;
typedef
int
VRType;
typedef
int
InforType;
typedef
struct
ArcNode
{
int
adjvex;
//
struct
ArcNode
*
nextarc;
//
//
int weight;
//
}ArcNode;
//
typedef
struct
VNode
{
VertexType data;
//
（ ）
ArcNode
*
firstarc;
//
}VNode, AdjList[MAX_VERTEX_NUM];
//
typedef
struct
ALGraph
{
AdjList vertices;
int
visited[MAX_VERTEX_NUM];
//
int
vexnum, arcnum;
//
}ALGraph;
//
void
init_ALGraph(ALGraph
&
g)
{
for
(
int
i
=
0
;i
<
MAX_VERTEX_NUM;i
++
)
g.visited[i]
=
0
;
//
0，
g.vexnum
=
0
;
g.arcnum
=
0
;
}
//
v
int
LocateVex(ALGraph
&
G,
char
v)
{
int
i;
for
(i
=
0
; v
!=
G.vertices[i].data
&&
i
<
G.vexnum; i
++
)
;
return
i;
}
//
void
add_vex(ALGraph
&
G)
{
cout
<<
"
:
"
<<
endl;
cin
>>
G.vexnum;
//
getchar();
//
cout
<<
"
:
"
<<
endl;
for
(
int
i
=
0
; i
<
G.vexnum; i
++
)
{
cin
>>
G.vertices[i].data;
//
G.vertices[i].firstarc
=
NULL;
//
getchar();
}
}
//
void
add_arc(ALGraph
&
G)
{
ArcNode
*
s,
*
t;
ArcNode
*
p;
cout
<<
"
:
"
<<
endl;
cin
>>
G.arcnum;
char
v1, v2;
cout
<<
"
:
"
<<
endl;
for
(
int
k
=
0
; k
<
G.arcnum; k
++
)
{
cin
>>
v1
>>
v2;
int
i
=
LocateVex(G, v1);
int
j
=
LocateVex(G, v2);
//
v1 , v2 G
s
=
(ArcNode
*
) malloc (
sizeof
(ArcNode));
t
=
(ArcNode
*
) malloc (
sizeof
(ArcNode));
s
->
adjvex
=
j;
//
j
s
->
nextarc
=
NULL;
if
(
!
G.vertices[i].firstarc)
{
G.vertices[i].firstarc
=
s;
}
else
{
for
(p
=
G.vertices[i].firstarc; p
->
nextarc; p
=
p
->
nextarc)
;
p
->
nextarc
=
s;
}
t
->
adjvex
=
i;
//
j
t
->
nextarc
=
NULL;
if
(
!
G.vertices[j].firstarc)
{
G.vertices[j].firstarc
=
t;
}
else
{
for
(p
=
G.vertices[j].firstarc; p
->
nextarc; p
=
p
->
nextarc)
;
p
->
nextarc
=
t;
}
}
}
//
void
CreateUDN(ALGraph
&
G)
{
add_vex(G);
//
add_arc(G);
//
}
void
PrintAdjList(ALGraph
&
G)
{
int
i;
ArcNode
*
p;
cout
<<
"
"
<<
endl;
for
(i
=
0
; i
<
G.vexnum; i
++
)
{
cout
<<
"
"
<<
i
<<
"
"
<<
G.vertices[i].data
<<
"
"
;
for
(p
=
G.vertices[i].firstarc; p; p
=
p
->
nextarc)
cout
<<
p
->
adjvex
<<
"
"
;
cout
<<
endl;
}
}
void
Visit(ALGraph
&
g,
int
i)
{
cout
<<
g.vertices[i].data
<<
"
"
;
g.visited[i]
=
1
;
}
//
void
DFSTraverse(ALGraph
&
g,
int
i)
//
i
{
Visit(g,i);
ArcNode
*
p;
for
(p
=
g.vertices[i].firstarc; p; p
=
p
->
nextarc)
if
(
!
g.visited[p
->
adjvex] )
DFSTraverse(g,p
->
adjvex);
}
void
DFSearch(ALGraph
&
g,
int
i,
int
s,
char
path[])
{
ArcNode
*
p;
g.visited[i]
=
1
;
static
int
found
=
0
;
static
int
rear
=
0
;
//
path[rear
++
]
=
g.vertices[i].data;
path[rear]
=
'
\0
'
;
//
'\0'
for
(p
=
g.vertices[i].firstarc; p
&&
!
found; p
=
p
->
nextarc)
if
(s
==
p
->
adjvex)
//
{
found
=
1
;
//
found 1，
path[rear
++
]
=
g.vertices[p
->
adjvex].data;
path[rear]
=
'
\0
'
;
}
else
if
(
!
g.visited[p
->
adjvex])
{
DFSearch(g,p
->
adjvex,s,path);
}
if
(
!
found)
//
， ， 。
path[
--
rear]
=
'
\0
'
;
}
//
void
Path(ALGraph
&
g,
char
ch1,
char
ch2,
char
path[])
{
int
i
=
LocateVex(g, ch1);
int
s
=
LocateVex(g, ch2);
DFSearch(g,i,s,path);
}
int
main()
{
ALGraph G;
init_ALGraph(G);
//
CreateUDN(G);
//
PrintAdjList(G);
//
//
DFSTraverse(G,0);
//
//
char
ch1,ch2;
char
*
path;
//
path
=
(
char
*
)malloc(MAX_VERTEX_NUM
*
sizeof
(
char
));
cout
<<
"
please input two points:
"
<<
endl;
cin
>>
ch1
>>
ch2;
Path(G,ch1,ch2,path);
int
i
=
0
;
while
(path[i])
cout
<<
path[i
++
];
//
return
0
;
}
좋은 웹페이지 즐겨찾기
