数据结构基础-图

• 图的概念
• 图的表达
• 图的存储结构
• 图的基本操作

更适应于稠密图

#include
using namespace std;

#define maxVertexnum 100
typedef char VertexType;
typedef int EdgeType;
typedef struct{
	VertexType Vex[maxVertexnum];
	EdgeType Edge[maxVertexnum][maxVertexnum];
	int vexnum,arcnum;
}Graph;

//有向图 
void create(Graph &g){
	int vex = 4,arc = 4;
	g.arcnum=arc;
	g.vexnum = vex;
	for(int i = 0;ig.vexnum || y>g.vexnum) return false;
	if(g.Edge[x][y] >= 1) return true;
}
void Neighbors(Graph g,int x){ //print x's neighbors vertex
	for(int i=0;i= 1){
			cout<= 1){
			cout<= 1){
		g.Edge[x][y] = 0;
	}
}
int main(){
	Graph g = new Graph();
	create(g);
}

更适应于稀疏图

#include
using namespace std;
#define maxVertexnum 100
typedef char VertexType

typedef struct ArcNode{
	int adjvex;
	struct ArcNode *next;
}ArcNode;
typedef struct VNode{
	VertexType data;
	ArcNode *first;
}VNode,AdjList[maxVertexnum];
typedef struct{
	AdjList vertices;
	int vexnum,arcnum;
}Graph;

void ADjacent(G,x,y);//is have edge x-y
void Neighbors(G,x); //print x's neighbors vertex
void InsertVertex(G,x);// insert x
void DeleteVertex(G,x);// delete x
void AddEdge(G,x,y); // add edge for x-y
void RemoveEdge(G,x,y);// remove the edge of x-y

有向图的一种链式表示

#include
#define maxVextexTypeNum 100
typedef char VertexType;
typedef int EdgeType;
using namespace std;
typedef struct ArcNode{
	int tailvex,headvex;	//尾域和头域 
	struct ArcNode *hlink,*tlink;	//出单链表和入单链表
	//Infotype info; 
}ArcNode;
typedef struct Vnode{
	VertexType data;
	ArcNode *firstin,*firstout;
}Vnode;
typedef struct{
	Vnode list[maxVertexTypeNum];
	int vexnum,arcnum;
}ALGraph;
int main(){
	
} 

无向图的一种链式表示

#include
#define maxVextexTypeNum 100
typedef char VertexType;
typedef int EdgeType;
using namespace std;
typedef struct ArcNode{
	int mark;
	int ivex,jvex;
	ArcNode *ilink,*jlink;
	//InfoType info;
}ArcNode;
typedef struct Vnode{
	VertexType data;
	ArcNode *firstedge;
}Vnode;
typedef struct{
	Vnode list[maxVertexTypeNum];
	int vexnum,arcnum;
}ALGraph;