1.图的存储方式
图的存储方式有邻接矩阵，邻接链表，十字链表等，邻接矩阵表示法通常将图G中的结点编为1,2,3…V,然后构造一个V*V的矩阵a[V][V],邻接矩阵的空间需求是O（V^2）.对于无向图,邻接矩阵是一个对称矩阵，有时为了减少空间需求，可以存储半个矩阵。邻接矩阵也可以存储权重图，矩阵中的元素代表权重值，如果两个结点之间没有边，可以将对应的权重值设置为-1或者一个不可能的值。
对于这个无向图，邻接矩阵的存储方式为：
邻接矩阵的代码为：
# include <iostream>
using namespace std;
# include <stdlib.h>
# define NUM 10
# define ARG 10
struct graph{
int num; //结点的数目
int arc; //边的数目
int a[NUM][NUM]; //邻接矩阵
char name[NUM]; //节点的名称
};
int main()
{
void create(graph &g);
void print(graph &g);
graph g;
create(g);
print(g);
system("pause");
return 0;
}
int locate(graph &g,char a)
{
int i=0;
for(i=0;i<g.num;i++)
if (g.name[i]==a)
return i;
return -1;
}
void create(graph &g)
{
int i,j;
cout<<"input num of nodes and num of edges"<<endl;
cin>>g.num>>g.arc;
for(i=0;i<g.num;i++)
cin>>g.name[i];
for(i=0;i<NUM;i++) //初始矩阵初始化
for(j=0;j<NUM;j++)
g.a[i][j]=0;
for(i=0;i<g.arc;i++)
{
char a,b;
int i,j,w;
cout<<"input name of nodes"<<endl;
cin>>a>>b>>w;
i=locate(g,a);
j=locate(g,b);
g.a[i][j]=w;
g.a[j][i]=w;
}
}
void print(graph &g) //打印图，即为打印矩阵的元素
{
int i,j;
for(i=0;i<g.num;i++){
for(j=0;j<g.num;j++)
cout<<g.a[i][j]<<"\t";
cout<<endl;
}
}
2.邻接链表
邻接链表时链式的存储结构，对图中每个节点建立一个单链表，链表的头结点是图中的各个节点，头结点和其余结点由两个域组成，分别为data和next指针。头结点的data存放的是节点的名称，普通的结点data存放的是结点序号。
上面的有向图可以用邻接链表表示，示意图为：
程序为：
# include <iostream>
using namespace std;
# include <stdlib.h>
# define NUM 10
struct anode{ //普通结点
int data;
anode *next;
};
struct bnode{ //头节点
char name;
anode *next;
};
struct graph{
int num;
int arc;
bnode arr[NUM];
};
int main()
{
void print(graph &g);
void create(graph &g);
graph g;
create(g);
print(g);
system("pause");
return 0;
}
int locate(graph &g,char a) //找到节点的位置
{
int i=0;
for(;i<g.num;i++)
{
if (g.arr[i].name==a)
return i;
}
return -1;
}
void create(graph &g)
{
cout<<"input the num of nodes and num of edges"<<endl;
cin>>g.num>>g.arc;
int i=0;
for(;i<g.num;i++)
{
cout<<"input the names of nodes"<<endl;
cin>>g.arr[i].name;
g.arr[i].next=NULL;
}
for(i=0;i<g.arc;i++)
{
char a,b;
cout<<"input node a and node b"<<endl;
cin>>a>>b;
int i=locate(g,a);
int j=locate(g,b);
anode *p=new anode;
p->data=j;
p->next=g.arr[i].next;
g.arr[i].next=p;
}
}
void print(graph &g) //打印图
{
int i=0;
while(g.arr[i].next!=NULL&&i<NUM)
{
cout<<g.arr[i].name<<":";
anode *e=g.arr[i].next;
while(e)
{
cout<<e->data;
e=e->next;
}
i++;
cout<<endl;
}
}
3十字链表
十字链表时有向图的另外一种链式存储方式，它是把邻接链表和逆邻接链表结合起来得到的一种链表，十字链表的普通节点有四个域，tail,head,hlink,tlink，头节点有三个域，data,firstin和firstout.
十字链表的程序为：
# include <iostream>
using namespace std;
# include <stdlib.h>
# define NUM 10
struct anode //普通结点
{
int tail,head;
anode *hlink,*tlink;
};
struct bnode{ //头结点
char name;
anode *firstin,*firstout;
};
struct graph{
bnode arr[NUM];
int num;
int arc;
};
int main()
{
void create(graph &g);
graph g;
create(g);
system("pause");
return 0;
}
int locate (graph &g,char a)
{
int i=0;
for(;i<g.num;i++)
{
if(g.arr[i].name==a)
return i;
}
return -1;
}
void create(graph &g)
{
cout<<"input the num of nodes and edges"<<endl;
cin>>g.num>>g.arc;
int i,j;
for(i=0;i<g.num;i++){
cout<<"input the names of nodes"<<endl;
cin>>g.arr[i].name;
g.arr[i].firstin=g.arr[i].firstout=NULL;
}
for (j=0;j<g.num;j++)
{
char a,b;
cout<<"input the node a and node b"<<endl;
cin>>a>>b;
int i=locate(g,a);
int j=locate(g,b);
anode *p=new anode;
//*p= {i,j,g.arr[j].firstin,g.arr[i].firstout};
p->tail=i; //插入新的结点
p->head=j;
p->hlink=g.arr[j].firstin;
p->tlink=g.arr[i].firstout;
g.arr[i].firstout=g.arr[j].firstin=p;
}
}
原文：http://blog.csdn.net/u011608357/article/details/20860209