相邻矩阵表示法:
(1) 也也称邻接矩阵或二维数组表示发
(2) 图的顶点元素是一个 | V | 的顺序表
(3) 如果从 vi 到 vj 存在一条边, 则第 i 行的第 j 个元素做标记, 否则不做标记
(4) 如果矩阵中的元素要存储边的权值, 则矩阵中每个元素必须足够大 (存储权值), 或者存储一个指向权值存储位置的指针
相邻矩阵特点分析:
(1) 可以用于存储无向图或者有向图
(2) 相邻矩阵需要存储所有可能的边, 不管这条边是否实际存在
(3) 没有结构性开销, 但是存在空间浪费
(4) 相邻矩阵的空间代价只与顶点的个数有关, 为 O(|V|^2), 图越密集, 其空间效率就越高
(5) 基于相邻矩阵的图算法, 必须查看它的所有可能的边, 导致总的时间代价为 O(|V|^2), 所以相邻矩阵适合密集图的存储
图的 ADT:
图的基本操作:
(1) 结构操作 / 销毁型操作
(2) 引用型操作:
获取图顶点或边, 查找
(3) 加工型操作:
插入, 删除图顶点或边
图 ADT 代码: Graph.hpp
- #ifndef _GRAPH_HPP_
- #define _GRAPH_HPP_
- #define VertexType int
- class Graph{
- public:
- virtual int n()=0;
- virtual int e()=0;
- virtual int first(int )=0;
- virtual int next(int,int)=0;
- virtual void putVex(int v,VertexType value)=0;
- virtual int locateVex(VertexType u)=0;
- virtual VertexType getVex(int v)=0;
- virtual void setEdge(int v1,int v2,int value)=0;
- virtual void deleteEdge(int,int)=0;
- virtual void setMark(int v,int value)=0;
- virtual int getMark(int v)=0;
- virtual int getEdge(int,int )=0;
- };
- #endif
图 ADT 的物理实现 - 相邻矩阵
声明: Graphm.hpp
- #ifndef _GRAPHM_HPP_
- #define _GRAPHM_HPP_
- #define VertexType int
- #define MAX_VERTEX_NUM 10000
- #include "Graph.hpp"
- class Graphm:public Graph{
- private:
- int numVertex,numEdge;
- int **matrix;
- int *mark;
- VertexType vexs[MAX_VERTEX_NUM];
- public:
- Graphm();
- Graphm(int n);
- int n();
- int e();
- int first(int );
- int next(int,int);
- void putVex(int v,VertexType value);
- int locateVex(VertexType u);
- VertexType getVex(int v);
- void setEdge(int v1,int v2,int value);
- void deleteEdge(int ,int );
- void setMark(int v,int value);
- int getMark(int v);
- int getEdge(int ,int);
- };
- #endif
实现: Graphm.cpp
- #define VertexType int
- #include "Graphm.hpp"
- #include <iostream>
- Graphm::Graphm(){}
- Graphm::Graphm(int n){
- numVertex=n;
- numEdge=0;
- matrix=new int*[numVertex];
- for(int i=0;i<numVertex;i++){
- matrix[i]=new int[numVertex];
- }
- for(int i=0;i<numVertex;i++)
- for(int j=0;j<numVertex;j++)
- matrix[i][j]=0;
- mark=new int[numVertex];
- for(int i=0;i<numVertex;i++)mark[i]=0;
- }
- int Graphm::n(){
- return numVertex;
- }
- int Graphm::e(){
- return numEdge;
- }
- int Graphm::first(int v1){
- int i;
- for( i=0;i<numVertex;i++){
- if(matrix[v1][i]!=0)
- return i;
- }
- return i;
- }
- int Graphm::next(int v1,int v2){
- int i;
- for(i=v2+1;i<numVertex;i++){
- if(matrix[v1][i]!=0)return i;
- }
- return i;
- }
- void Graphm::putVex(int v,VertexType value){
- vexs[v]=value;
- }
- int Graphm::locateVex(VertexType u){
- for(int i=0;i<numVertex;i++){
- if(u==vexs[i])return i;
- }
- return -1;
- }
- VertexType Graphm::getVex(int v){
- return vexs[v];
- }
- void Graphm::setEdge(int v1,int v2,int value){
- if(matrix[v1][v2]==0)numEdge++;
- matrix[v1][v2]=value;
- }
- void Graphm::deleteEdge(int v1,int v2){
- if(matrix[v1][v2]==0)numEdge--;
- matrix[v1][v2]=0;
- }
- void Graphm::setMark(int v,int value){
- mark[v]=value;
- }
- int Graphm::getMark(int v){
- if(v>=numVertex)return -1;
- return mark[v];
- }
- int Graphm::getEdge(int v1,int v2){
- return matrix[v1][v2];
- }
demo 程序: main.cpp
- #include"Graphm.cpp"
- #include"Graphm.hpp"
- #include <iostream>
- #include <stdio.h>
- #include <stdlib.h>
- #include <stack>
- #include <queue>
- using namespace std;
- int V,E;
- // 深度优先搜索递归版
- void DFS1(Graphm *g,int v1){
- printf("%d",v1+1);
- g->setMark(v1,1);
- for(int w=g->first(v1);w<g->n();w=g->next(v1,w)){
- if(g->getMark(w)==0)DFS1(g,w);
- }
- }
- // 深度优先搜索非递归版
- void DFS2(Graphm *g,int v1){
- stack<int> s;
- s.push(v1);
- g->setMark(v1,1);
- while(s.empty()!=1){
- int temp=s.top();
- cout<<temp+1<<" ";
- s.pop();
- for(int i=g->n()-1;i>=0;i--){
- if(g->getMark(i)==0&&g->getEdge(temp,i)!=0){
- s.push(i);
- g->setMark(i,1);
- }
- }
- }
- }
- // 广度优先搜索
- void BFS(Graphm *g,int v1){
- queue<int>q;
- q.push(v1);
- g->setMark(v1,1);
- cout<<v1+1<<" ";
- while(q.empty()!=1){
- int temp=q.front();
- q.pop();
- for(int i=0;i<g->n();i++){
- if(g->getMark(i)==0&&g->getEdge(temp,i)!=0){
- q.push(i);
- g->setMark(i,1);
- cout<<i+1<<" ";
- }
- }
- }
- }
- void print(Graphm &g){
- for(int i=0;i<g.n();i++){
- for(int j=0;j<g.n();j++){
- cout<<g.getEdge(i,j)<<" ";
- }
- cout<<endl;
- }
- cout<<endl;
- }
- int main(){
- scanf("%d%d",&V,&E);
- Graphm G(V);
- // cout<<G.n()<<" "<<G.e()<<endl;
- while(E--){
- int v1,v2;
- scanf("%d%d",&v1,&v2);
- G.setEdge(v1-1,v2-1,1);
- // cout<<G.e()<<endl;
- }
- print(G);
- for(int i=0;i<G.n();i++){
- if(G.getMark(i)==0)
- DFS1(&G,i);
- cout<<endl;
- DFS2(&G,i);
- cout<<endl;
- BFS(&G,i);
- cout<<endl;
- }
- return 0;
- }
来源: https://www.cnblogs.com/bo2000/p/10119665.html