一、邻接矩阵

        图的邻接矩阵存储方式是用两个数组表示图，顶点数组（一维数组）存储顶点信息，边数组（二维数组）存储图中的边或弧的信息。（图片来自于百度百科）

   如果存在边，则数组元素置为1，若无边，则数组元素为0。

   若为无向图，则矩阵对称，若为有向图，则不一定对称。但无论是有向图还是无向图，矩阵主对角线上的值都为0。

 

二、邻接表

        可以看出，若数据量巨大，则邻接矩阵会浪费巨大的空间。改用邻接表可以节约大量存储空间。邻接表是一种数组与链表相结合的存储方式。图中顶点用一个一维数组存储，另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点vi的边表，有向图称为顶点vi作为弧尾的出边表。

 

 

三、深度优先搜索算法

  从图的某个顶点出发访问遍图中所有顶点，且每个顶点仅被访问一次。（连通图与非连通图）

1、访问指定的起始顶点；

2、若当前访问的顶点的邻接顶点有未被访问的，则任选一个访问之；反之，退回到最近访问过的顶点；直到与起始顶点相通的全部顶点都访问完毕；

3、若此时图中尚有顶点未被访问，则再选其中一个顶点作为起始顶点并访问之，转 2； 反之，遍历结束。

连通图的深度优先遍历类似于树的先根遍历

如图

 

四、深度优先搜索算法代码（邻接矩阵）

 

#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXVEX 100
#define MAX 100 
#define INFINITE 65535
#define TRUE 1
#define FALSE 0
using namespace std;

typedef char VertexType;
typedef int EdgeType;
typedef int Boolean;
Boolean visited[MAX]; 

typedef struct {
	VertexType vexs[MAXVEX];
	EdgeType arc[MAXVEX][MAXVEX];
	int numVertexes,numEdges;
}MGraph;

void Create_MGraph(MGraph *G){
	int i,j,k,w;
	cout<<"输入顶点数和边数："<<endl;
	cin>>G->numVertexes>>G->numEdges;
	cout<<"请输入各顶点:"<<endl;
	for(i=0;i<G->numVertexes;i++) 
		cin>>G->vexs[i];//读入顶点信息建立顶点表 
	for(i=0;i<G->numVertexes;i++)
		for(j=0;j<G->numVertexes;j++)
			G->arc[i][j]=INFINITE;
	for(k=0;k<G->numEdges;k++){
		cout<<"输入边的顶点和权："<<endl;
		cin>>i>>j>>w;
		G->arc[i][j]=w;
		G->arc[j][i]=G->arc[i][j];
	}
}

void DFS(MGraph G,int i){
	int j;
	visited[i]=TRUE;
	printf("%c ",G.vexs[i]);
	for(j=0;j<G.numVertexes;j++){
		if(G.arc[i][j]==1&&!visited[j])
			DFS(G,j);
	}
}

void DFSTraverse(MGraph G){
	int i;
	for(i=0;i<G.numVertexes;i++)
		visited[i]=FALSE;
	for(i=0;i<G.numVertexes;i++){
		if(!visited[i])
			DFS(G,i);
	}
}

int main(){
	MGraph G;
	Create_MGraph(&G);
	cout<<"遍历结果为："<<endl; 
	DFSTraverse(G);
	return 0;
} 
 
 /*
 5 6
 0 1 2 3 4 
 0 1 9
 1 2 3 
 0 2 2
 2 3 5
 3 4 1
 4 0 6 
 */ 

五、深度优先搜索算法（邻接表）

 

 

#include<bits/stdc++.h>
using namespace std;
#define MAXVEX 100
#define INFINITE 65535
#define MAX 100
#define TRUE 1
#define FALSE 0
using namespace std;

typedef int Boolean;
Boolean visited[MAX]; 
typedef char VertexType;//顶点类型 
typedef int EdgeType;//权值类型 
//边表节点 
typedef struct EdgeNode{
	int adjvex;//邻接点域，储存顶点下标 
	EdgeType weight;//权值 
	struct EdgeNode *next;//链域 
}EdgeNode;
//顶点表节点 
typedef struct VertexNode{
	VertexType data;//顶点信息 
	EdgeNode *firstedge;//边表头指针 
}VertexNode ,AdjList[MAXVEX]; 
typedef struct {
	AdjList adjList;
	int numVertexes,numEdges;//顶点数和边数 
}GraphAdjList;

void Create_ALGraph(GraphAdjList *G){
	int i,j,k;
	EdgeNode *e;
	cout<<"输入顶点数和边数："<<endl;
	cin>>G->numVertexes>>G->numEdges;//输入顶点和边数 
	for(i=0;i<G->numVertexes;i++){
		cin>>G->adjList[i].data;//输入顶点信息 
		G->adjList[i].firstedge=NULL; //边表置为空表 
	}
	for(k=0;k<G->numEdges;k++){   //建立边表 
		cout<<"输入边（vi,vj）上的顶点序号："<<endl; 
		cin>>i>>j;
		e=(EdgeNode *)malloc(sizeof(EdgeNode));//生成边表节点 
		
		e->adjvex=j;//邻接序号为j 
		e->next=G->adjList[i].firstedge;//将e指针指向当前顶点指向的节点 
		G->adjList[i].firstedge=e;//将当前定点的指针指向e 
	//下面段代码的作用，目的？？ 
		e=(EdgeNode *)malloc(sizeof(EdgeNode));//邻接序号为i
		e->adjvex=i;
		e->next=G->adjList[i].firstedge;
		G->adjList[i].firstedge=e; 
	}
} 

void DFS(GraphAdjList GL,int i){
	EdgeNode *p;
	visited[i]=TRUE;
	cout<<GL.adjList[i].data<<" ";
	p=GL.adjList[i].firstedge;
	while(p){
		if(!visited[p->adjvex])
			DFS(GL,p->adjvex);
		p=p->next;
	}
}


void DFSTraverse(GraphAdjList GL){
	int i;
	for(i=0;i<GL.numVertexes;i++)
		visited[i]=FALSE;
	for(i=0;i<GL.numVertexes;i++)
		if(!visited[i])
			DFS(GL,i);
}
int main(){
	GraphAdjList G;
	Create_ALGraph(&G);
	DFSTraverse(G);
	return 0;
} 

/*
5 6
0 1 2 3 4 
0 1 
1 2  
0 2 
2 3 
3 4 
4 0 
*/