声明：本代码仅供参考，根本就不是正确代码（至少在我看来，有很多BUG和不完美的地方）
图的存储方式选择为邻接表，并且headNode只是来存储一个链表的Node首地址额
总之这个代码写的很垃圾呀很垃圾···水平太低 o(╥﹏╥)o
Graph.h
#include<iostream>
using namespace std;
struct Node { //结点，用来存储图上结点的信息
char data; //结点名称
Node *next;
int loc;//数组下标 };
struct headNode {
Node *address;
bool flag;//标志，默认为false代表没有被访问(访问过就是true防止重复访问 耶我真机智)
};
class Graph {
private:
headNode *root;
const int MAX_SIZE = ;
int true_size;
void initGraph(char data[], int num);
void contact();
int search(char goal);
void dfs_print(int loc);
public:
Graph() { root = NULL; true_size = ; }
Graph(char data[], int num);
void add();
void print_all();
void DFSprint(char item);
};
Graph.cpp
#include"Graph.h"
Graph::Graph(char data[], int num)
{
initGraph(data, num);
cout << "图初始化完毕！" << endl;
contact();
}
void Graph::contact()
{
cout << "请分别输入这" << true_size << "个元素的连接结点：" << endl;
int contact_number;
for (int i = ; i < true_size; i++)
{
cout << "请输入连接" << root[i].address->data << "结点的个数：";
cin >> contact_number;
cout << "请分别输入连接的结点的名称:" << endl;
for (int j = ; j < contact_number;j++)
{
char data;
Node *end = root[i].address;
while (end->next)
{
end = end->next;
}
Node *add = new Node();
cin >> data;
add->data = data;
add->loc = search(data);
if (add->loc == -)
{
//错误
}
add->next = NULL;
end->next = add; }
}
}
int Graph::search(char goal)//-1为查找失败
{
int result = -;
for (int i = ; i < true_size; i++)
{
if (root[i].address->data == goal)
{
result = i;
break;
}
}
return result;
}
void Graph::initGraph(char data[],int num)
{
true_size = num;
root = new headNode[MAX_SIZE];
for (int i = ; i < true_size; i++)
{
root[i].address = new Node();
root[i].address->data = data[i];
root[i].address->loc = i;
root[i].address->next = NULL;
root[i].flag = false;
}
}
void Graph::add()
{ cout << "请输入要添加的元素:" << endl;
char data;
cin >> data;
int loc = search(data);
if (loc!= -)
{
cout << "元素已经存在在图中，请输入添加连接的个数：" << endl;
int number;
cin >> number;
for (int j = ; j < number; j++)
{
char data;
Node *end = root[loc].address;
while (end->next)
{
end = end->next;
}
Node *add = new Node();
cin >> data;
add->data = data;
add->loc = search(data);
if (add->loc == -)
{
cout << "未找到指定元素" << endl;
}
add->next = NULL;
end->next = add;
} }
else
{
if (true_size > MAX_SIZE)
{
cout << "图已经超出最大连接长度，添加失败！" << endl;
return ;
}
true_size++;
root[true_size].address = new Node();
root[true_size].address->data = data;
root[true_size].address->loc = true_size;
root[true_size].address->next = NULL;
}
cout << data << "已经成功添加！" << endl;
}
void Graph::print_all()
{
for (int i = ; i < true_size; i++)
{
cout << "结点:" << root[i].address->data << "连接的结点为：" << endl;
Node *p = root[i].address->next;
while (p)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
}
void Graph::dfs_print(int loc)
{
Node *p = root[loc].address;
root[loc].flag = true;
while (p!= NULL)
{
Node *w = p->next;
if ((w!=NULL)&&(root[w->loc].flag == false))
{
cout << w->data << " ";
dfs_print(w->loc);
}
p = p->next;
}
}
void Graph::DFSprint(char item)
{
int loc = search(item);
if (loc == -)
{
cout << "错误，未找到结点！" << endl;
}
else
{
cout << root[loc].address->data << " ";
dfs_print(loc);
}
}
main.cpp
#include"Graph.h"
int main()
{
char *graphNode,select;
int number;
cout << "请输入图中结点个数:";
cin >> number;
graphNode = new char[number];
cout << "请输入结点名称并继续:" << endl;
for (int i = ; i < number; i++)
{
cin >> graphNode[i];
}
Graph test(graphNode, number);
test.add();
test.print_all();
cout << "请输入开始访问的结点:" << endl;
cin >> select;
test.DFSprint(select);
system("pause");
return ; }
请输入图中结点个数:
请输入结点名称并继续:
A B C D
图初始化完毕！
请分别输入这4个元素的连接结点：
请输入连接A结点的个数：
请分别输入连接的结点的名称:
C
请输入连接B结点的个数：
请分别输入连接的结点的名称:
D
请输入连接C结点的个数：
请分别输入连接的结点的名称:
A
请输入连接D结点的个数：
请分别输入连接的结点的名称:
B
请输入要添加的元素:
A
元素已经存在在图中，请输入添加连接的个数： B
A已经成功添加！
结点:A连接的结点为：
C B
结点:B连接的结点为：
D
结点:C连接的结点为：
A
结点:D连接的结点为：
B
请输入开始访问的结点:
A
A C B D 请按任意键继续. . .
测试结果
注意：已知BUG，如果在输入元素连接结点的时候，请注意输入顺序，尽量从下往上输入，否则会造成DFS遍历失败···