무방 향 무권 도 중의 하나 인 필획 문제
9860 단어 절차 의 길
저 는 대학교 2 학년 때 학교 전공 수업 의 데이터 구조 와 알고리즘 수업 에서 3 급 프로젝트 는 무 방향 무 권 도 를 완성 하 는 것 이 었 습 니 다. 오랫동안 생각 했 는데 한 획 의 그림 이 이 무 방향 무 권 도 에 적합 하 다 고 생각 했 습 니 다.그래서 3 급 프로젝트 의 완성 을 즐겁게 시작 했다.알고리즘 은 프로 그래 밍 사상 에 대해 그렇게 엄격 한 요구 가 없 기 때문에 우 리 는 자신의 능력 을 다 해 보완 하고 대상 을 대상 으로 하면 이렇게 될 수 있 습 니 다. 능력 에 한계 가 있 습 니 다. 하하.
첫 번 째 단계: 유형의 디자인, 내 가 생각 하 는 것 은 세 가지 유형 을 구축 하 는 것 이다. 정점 류, 변 류, 그리고 그림 류 이다.
① 정점 류: 정점 의 값 (즉 정점 의 이름) 이 있 고 정점 의 두 가지 구조 방법, 정점 이 방문 되 었 는 지, 그리고 각 정점 과 인접 한 정점 은 vector 배열 에 놓 여 있다.그런데 이 vector 배열 은 정말 좋 은 물건 입 니 다. 스스로 집합 을 정의 하지 않 아 도 됩 니 다. 저 같은 반찬 새 에 게 는 많은 번 거 로 움 을 덜 었 습 니 다.
#pragma once
#include
using namespace std;
class Vertex {
public :
Vertex(int value);
Vertex();
int getValue();
void setValue(int value);
vector & getNearVertexs();
bool isVisted;
private:
vector nearVertexs;
int value;
};
vector & Vertex::getNearVertexs() {
return nearVertexs;
}
int Vertex::getValue() {
return value;
}
void Vertex::setValue(int value) {
this->value = value;
}
Vertex::Vertex(int value) {
isVisted = false;
this->value = value;
}
Vertex::Vertex() {
isVisted = false;
}
② 변 류: 두 가지 구조 방법 으로 변 이 방문 되 었 는 지 여부 (한 획 의 문 제 는 상대 적 으로 변 하기 때문에 모든 변 이 한 번 방문 되 어야 하고 점 의 방문 횟수 는 제한 되 지 않 음) 이 변 의 두 정점 으로 돌아 가 야 합 니 다.
#pragma once
#include"Vertex.h"
class Edge {
public:
Edge();
Edge(Vertex v1, Vertex v2);
bool isVisited;
Vertex& getVertex1();
Vertex& getVertex2();
private:
Vertex v1, v2;
};
Edge::Edge(Vertex v1, Vertex v2){
this->v1 = v1;
this->v2 = v2;
isVisited = false;
}
Vertex& Edge::getVertex1() {
return v1;
}
Vertex& Edge::getVertex2() {
return v2;
}
Edge::Edge() {
isVisited = false;
}
③ 그림 류: 이 안에 물건 이 좀 많 으 니 구체 적 으로 코드 를 보 세 요. 함수 에 대응 하 는 기능 도 영어 의 뜻 에 따라 대충 알 수 있 고 일부 주석 도 적 었 습 니 다.
#pragma once
#include
#include"Vertex.h"
#include"Edge.h"
using namespace std;
class arrayGraph
{
public:
arrayGraph(int e, int v);
int numberOfVertices();//
int numberOfEdges();//
vector getEdges();//
vector getVertexs();//
bool existsEdge(Edge edge);// ，
void insertEdge(Edge edge);//
void initialize();// ， vector
void DFS(Vertex & v);// dfs
void dfs(Vertex & v);
void override_dfs(Vertex & v);// ： dfs， dfs
void override_DFS(Vertex& v);
Vertex& findVertexByValue(int value);//
Edge& findEdgeByVertexValues(int value1, int value2);//
bool isOk();//
bool isCircled();
private:
int edge_count;
int vertex_count;
int insert_index = 0;
vector edges;
vector reach;
vector vertexs;
vector temp;
bool existVertex(int value);
};
arrayGraph::arrayGraph(int e, int v) {
this->edge_count = e;
this->vertex_count = v;
for (int i = 0; i < e; i++)
{
cout << " " << i + 1 << " " << endl;
Vertex v1, v2;
int a,b;
cin >> a >> b;
v1.setValue(a);
v2.setValue(b);
insertEdge(Edge(v1, v2));
if (!existVertex(v1.getValue())) {
vertexs.push_back(v1);
}
if (!existVertex(v2.getValue())) {
vertexs.push_back(v2);
}
}
initialize();
}
int arrayGraph::numberOfVertices() {
return vertex_count;
}
int arrayGraph::numberOfEdges() {
return edge_count;
}
vector arrayGraph::getEdges() {
return edges;
}
bool arrayGraph::existsEdge(Edge edge) {
for each (Edge t_edge in edges)
{
if ((t_edge.getVertex1().getValue() == edge.getVertex1().getValue() && t_edge.getVertex2().getValue() == edge.getVertex2().getValue())
|| (t_edge.getVertex1().getValue() == edge.getVertex2().getValue() && t_edge.getVertex2().getValue() == edge.getVertex1().getValue())
) {
return true;
}
}
return false;
}
void arrayGraph::insertEdge(Edge edge) {
this->edges.push_back(edge);
insert_index++;
}
void arrayGraph::DFS(Vertex & v) {
reach.push_back(findVertexByValue(v.getValue()));
findVertexByValue(v.getValue()).isVisted = true;
dfs(findVertexByValue(v.getValue()));
for (vector::iterator i = reach.end();
i != reach.begin(); cout << (*(--i)).getValue() << " ");
cout << endl;
}
void arrayGraph::dfs(Vertex & v) {
for (vector ::iterator it = findVertexByValue(v.getValue()).getNearVertexs().begin();
it != findVertexByValue(v.getValue()).getNearVertexs().end(); ++it) {
if (!(*it).isVisted && !findVertexByValue((*it).getValue()).isVisted) {
(*it).isVisted = true;
findVertexByValue((*it).getValue()).isVisted = true;
reach.push_back((*it));
dfs((*it));
}
}
}
void arrayGraph::initialize() {
// vector
for each (Edge t_edge in edges)
{
Vertex v1 = t_edge.getVertex1();
Vertex v2 = t_edge.getVertex2();
cout << t_edge.getVertex1().getValue() << " " << t_edge.getVertex2().getValue() << endl;
for (vector ::iterator it = vertexs.begin(); it != vertexs.end(); ++it) {
if ((*it).getValue() == v1.getValue()) {
(*it).getNearVertexs().push_back(v2);
}
if ((*it).getValue() == v2.getValue()) {
(*it).getNearVertexs().push_back(v1);
}
}
}
system("cls");
cout << "=======================================================" << endl;
cout << "=======================================================" << endl;
cout << "======================= =======================" << endl;
cout << endl;
//
for (vector ::iterator it = vertexs.begin(); it != vertexs.end(); ++it) {
cout << " " << (*it).getValue() << " ： ";
for (vector ::iterator ix = (*it).getNearVertexs().begin(); ix != (*it).getNearVertexs().end(); ++ix) {
cout << " ：" << (*ix).getValue() << " ";
}
cout << endl;
cout << endl;
}
}
vector arrayGraph::getVertexs() {
return vertexs;
}
bool arrayGraph::existVertex(int value) {
for each (Vertex t_v in vertexs)
{
if (t_v.getValue() == value) {
return true;
}
}
return false;
}
Vertex& arrayGraph::findVertexByValue(int value) {
for (vector ::iterator it = vertexs.begin(); it != vertexs.end(); ++it) {
if ((*it).getValue() == value) {
return (*it);
}
}
return Vertex();
}
void arrayGraph::override_dfs(Vertex& v) {
for (vector ::iterator it = vertexs.begin(); it != vertexs.end(); ++it) {
if (existsEdge(Edge(findVertexByValue(v.getValue()), (*it))) && !findEdgeByVertexValues(findVertexByValue(v.getValue()).getValue(),(*it).getValue()).isVisited) {
findEdgeByVertexValues(v.getValue(), (*it).getValue()).isVisited = true;
override_dfs((*it));
}
}
reach.push_back(findVertexByValue(v.getValue()));
}
void arrayGraph::override_DFS(Vertex& v) {
override_dfs(findVertexByValue(v.getValue()));
if (isCircled()) {
cout << " , ：" << endl;
}
else
cout << " ， ：" << endl;
for (vector::iterator i = reach.end();
i != reach.begin(); cout << (*(--i)).getValue() << " ");
cout << endl;
}
Edge& arrayGraph::findEdgeByVertexValues(int value1, int value2) {
for (vector ::iterator it = edges.begin(); it != edges.end(); ++it) {
if (((*it).getVertex1().getValue() == value1 && (*it).getVertex2().getValue() == value2) ||
((*it).getVertex1().getValue() == value2 && (*it).getVertex2().getValue() == value1)) {
return (*it);
}
}
return Edge();
}
bool arrayGraph::isOk() {
int key = 0;
for (vector::iterator it = vertexs.begin();it != vertexs.end();++it) {
if ((*it).getNearVertexs().size() % 2 != 0) {
temp.push_back((*it));
key++;
}
}
if (key != 0 && key != 2) {
return false;
}
else {
cout << " ， ！ " << endl;
for (vector::iterator it = temp.begin();it != temp.end();++it) {
cout << (*it).getValue() << " ";
}
cout << endl;
return true;
}
}
bool arrayGraph::isCircled() {
return reach.size()>=vertexs.size();
}
마지막 으로 테스트 의 main 함수 입 니 다.
#include
#include
#include"Graph.h"
using namespace std;
int main() {
while (1) {
system("cls");
cout << "=======================================================" << endl;
cout << "=======================================================" << endl;
cout << "======================= =======================" << endl;
cout << endl;
int edge_count, vertex_count;
cout << " " << endl;
cin >> edge_count >> vertex_count;
arrayGraph a(edge_count, vertex_count);
cout << " ！ ！" << endl;
getch();
if (!a.isOk()) {
cout << " ！" << endl;
}
else {
cout << " " << endl;
int value;cin >> value;
a.override_DFS(a.findVertexByValue(value));
}
getch();
getch();
}
system("pause");
return 0;
}
도움 이 됐 으 면 좋 겠 어 요!!
좋은 웹페이지 즐겨찾기
