《数据结构与算法》——图
本帖最后由 luciferzf 于 2017-8-15 14:03 编辑图：
1）图是由点的集合和边的集合组成的一个多对多的关系，通常可以表示为G（V，E），其中V是点的集合，E是边的集合，点的集合要求有穷非空
2）简单图：图中不存在顶点到自身的边，并且两个点之间只有一条边
3）无向完全图：任意2个顶点间都存在无向边
4）有向完全图：任意2个顶点间都存在两条方向相反的有向边
5）连通图：图中任意两个点都连通；强连通图则要求任意两个点都存在路径
图的存储结构：
1）我们定义一个一维数组存放顶点，一个二维数组存放边，对于二维数组元素T表示点a和b的关系，若T值为1，表示a和b之间有边，若为0，则无边
2）对于无向图，边的储存数组相当于一个对称矩阵，一个顶点的度等于该顶点在矩阵中对应行的1的个数
3）对于网，储存边的数组中的值不再只是0和1，而是每条边的权，若两个点间不存在边，则定义数组对应元素的值为无穷大（即一个比其他元素值都大的静态值）
邻接表：
首先定义一个顺序表用来存储各个节点，然后利用链表的形式，将各个相邻点在顺序表中的下标依次连接在顺序表里各个点上。对于有向表来说，这样就易于得到点的出度。
十字链表：相比于邻接表，十字链表将出度和入度分开，十字链表的顺序表中的各个点不仅储存了出度的点的下标，还有入度的点的下标，对于有向图，更易于得到入度和出度。
邻接多重表：在边表结构中，我们储存了一条边的两个点的下标，以及分别指向与两个点相邻的另外两条边的指针
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
#define N 100
class edgenode
{
public:
int index;
edgenode *np=NULL;
};
class node
{
public:
char data;
int flag = 0;
edgenode *np=NULL;
}vertex;
void Input()
{
int T;
cout << "Input vertex:";
cin >> T;
vertex.data = T;
for (int i = 1; i < T+1; i++)
{
cin >> vertex.data;
}
cout << "Input edges:";
cin >> T;
for (int i = 1; i < T+1; i++)
{
int a, b;
edgenode *cp = NULL;
cin >> a >> b;
if (vertex.np == NULL)
{
cp = new edgenode;
vertex.np = cp;
}
else
{
cp = vertex.np;
while (cp->np != NULL)
{
cp = cp->np;
}
edgenode *p = cp;
cp = new edgenode;
p->np = cp;
}
cp->index = b;
}
}
void research()
{
int n = vertex.data;
for (int i = 1; i <= n; i++)
{
edgenode *p=vertex.np;
cout << vertex.data << "——>" << vertex.data;
while (p->np != NULL)
{
p = p->np;
cout << "——>" << vertex.data;
}
cout << endl;
}
}
int main()
{
Input();
research();
system("PAUSE");
}
页:
[1]