## 【算法与数据结构】图 -- 邻接表 原

cuihao

``/************************************************************************ 边(弧)结点 -------------------------- |adjvex | info | nextarc | -------------------------- adjvex:邻接点域,该点在图中的位置 info :相关信息，比如可以保存从某顶点到该点的权值 nextac:指向下一个与该点有相同邻接点的顶点 顶点结点 ------------------ |data | firstarc | ------------------ data :该顶点的数据 firstarc:第一个与该顶点邻接的顶点 e.g. 顶点1，2，3，4 --------- -------- --------- 0 | 1 | |--->| 2 | |--->| 1 | ^ | --------- 1 | 2 | ^ | --------- --------- 2 | 3 | |--->| 3 | ^ | --------- --------- 3 | 4 | |--->| 0 | ^ | --------- --------- PS:画上面这个图 容易么我 ************************************************************************/``

``````//最大顶点个数
const int MAX_VERTEX = 100; //最大值
const int MAX_VALUE = (1 << 31) - 1; //边(弧)结点
typedef struct _tagArcNode { int                 adjvex;  //该边(弧)所指向的顶点在图中的位置
struct _tagArcNode* nextarc; //下一个与该顶点有相同邻接点的边(弧)结点
char                info;    //相关信息，比如可以保存该边(弧)的权值
}ArcNode; //顶点节点
typedef struct _tagVNode { char data;          //顶点信息
ArcNode* firstArc;  //该顶点的第一条边(弧)所指向的顶点
int vexnum;        //顶点个数
int arcnum;        //边(弧)的条数
}Graph;``````

``int Locate(Graph& graph, char ch) { for (int i = 0; i < graph.vexnum; ++ i) { if (ch == graph.vertices[i].data) return i; } return -1; }``

``````void CreateGraph(Graph& graph) { int num = 0; cout << "请输入图的顶点个数:"; cin >> num; graph.vexnum = num; cout << "请输入图的边(弧)的条数:"; cin >> num; graph.arcnum = num; cout<<endl<<endl; cout<<"开始输入每个顶点"<<endl; for (int i = 0; i < graph.vexnum; ++ i) { cout << "请输入顶点:"; char ch = 0; cin >> ch; graph.vertices[i].data = ch; graph.vertices[i].firstArc = NULL; } cout<<endl<<"结束输入顶点"<<endl<<endl; cout<<"开始构造邻接表"<<endl; for (int i = 0; i < graph.vexnum; ++ i) { int nCount = 1; while(1) { cout << "请输入顶点 "<<graph.vertices[i].data<<" 的第 " << nCount++<<" 个邻接点, 输入#结束:"; char ch = 0; cin >> ch; if (ch == '#') break; ArcNode* pArcNode = new ArcNode(); pArcNode->adjvex = Locate(graph, ch); pArcNode->nextarc = NULL; //如果该顶点还没有设置第一条边(弧)，则将该输入顶点确定的边(弧) //作为该顶点的第一条边(弧)
if (NULL == graph.vertices[i].firstArc) { graph.vertices[i].firstArc = pArcNode; } //否则，遍历该顶点所在链表，找到最后一个节点，将其nextarc指针域 //设置为由当前输入的顶点确定的边(弧)
else { ArcNode* pTemp = graph.vertices[i].firstArc; //直到找到顶点所在链表的最后一个边(弧)结点为止
while(pTemp->nextarc != NULL) pTemp = pTemp->nextarc; //找到最后一个边(弧)结点后，将其nextarc指针域设置为当前输入的顶点所确定的边(弧)
pTemp->nextarc = pArcNode; } } //while(1)
} //for
cout << endl<<"结束构造邻接表"<<endl<<endl; }``````

``int _tmain(int argc, _TCHAR* argv[]) { Graph graph; CreateGraph(graph); return 0; }``

### cuihao

新学期开始了，开始专心于技术上了，上学期的寒假总是那么短暂，飘飘乎就这样逝去，今天补补上学期还没学完的数据结构---图，希望能和大家一起探讨，共同进步~ 定义： 　　图是由顶点集合...

graylee
2015/03/10
0
0

2017/09/11
0
0

RapidBird
2010/03/25
393
0

2018/08/28
3.9K
0
【译】Swift算法俱乐部-图

Andy_Ron
07/24
0
0

Replugin借助“UI进程”来快速释放Dex

public static boolean preload(PluginInfo pi) { if (pi == null) { return false; } // 借助“UI进程”来快速释放Dex（见PluginFastInstallProviderProxy的说明） return PluginFastInsta......

Gemini-Lin

4
0
Hibernate 5 的模块/包（modules/artifacts）

Hibernate 的功能被拆分成一系列的模块/包（modules/artifacts），其目的是为了对依赖进行独立（模块化）。 模块名称 说明 hibernate-core 这个是 Hibernate 的主要（main (core)）模块。定义...

honeymoose

4
0
CSS--属性

wytao1995

4
0

7
0

401恶户

3
0