데이터 구조 - 깊이 우선 검색 지점 에서 지점 까지 의 일반 경로
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
;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
