// Adjacency Lists + DFS.
#ifndef _IOSTREAM_H
#include <iostream.h>
#include <conio.h>
#define _IOSTREAM_H
#endif
enum Boolean { FALSE, TRUE};
template <class Type> class List;
template <class Type> class ListIterator;
template <class Type>
class ListNode {
friend class List<Type>;
friend class ListIterator<Type>;
private:
Type data;
ListNode *link;
ListNode(Type);
};
template <class Type>
ListNode<Type>::ListNode(Type Default)
{
data = Default;
link = 0;
}
template <class Type>
class List {
friend class ListIterator<Type>;
public:
List() {first = 0;};
void Insert(Type);
void Delete(Type);
private:
ListNode<Type> *first;
};
template <class Type>
void List<Type>::Insert(Type k)
{
ListNode<Type> *newnode = new ListNode<Type>(k);
newnode->link = first;
first = newnode;
}
template <class Type>
void List<Type>::Delete(Type k)
{
ListNode<Type> *previous = 0;
ListNode<Type> *current;
for (current = first; current && current->data != k;previous = current, current = current->link);
if (current)
{
if (previous)
previous->link = current->link;
else
first = first->link;
delete current;
}
}
template <class Type>
class ListIterator
{
public:
ListIterator(const List<Type>& l): list(l) {current = l.first;}
Type* First();
Type* Next();
Boolean NotNull();
Boolean NextNotNull();
private:
const List<Type> &list;
ListNode<Type>* current;
};
template <class Type>
Type* ListIterator<Type>::First() {
if (current) return ¤t->data;
else return 0;
}
template <class Type>
Type* ListIterator<Type>::Next() {
current = current->link;
return ¤t->data;
}
template <class Type>
Boolean ListIterator<Type>::NotNull()
{
if (current) return TRUE;
else return FALSE;
}
template <class Type>
Boolean ListIterator<Type>::NextNotNull()
{
if (current->link) return TRUE;
else return FALSE;
}
//template <class Type>
ostream& operator<<(ostream& os, List<char>& l)
{
ListIterator<char> li(l);
if (!li.NotNull()) return os;
os << *li.First() << endl;
while (li.NextNotNull())
os << *li.Next() << endl;
return os;
}
class Graph
{
private:
List<int> *HeadNodes;
int n;
void DFS(const int);
Boolean *visited;
int num;
int *low;
int *dfn;
void DfnLow(const int, const int);
public:
Graph(const int vertices = 0) : n(vertices)
{ HeadNodes = new List<int>[n];};
void DFS();
void Setup();
void Setup2();
void DfnLow(const int);
void Components();
void Out();
};
void Graph::Setup()
{
HeadNodes[0].Insert(2); HeadNodes[0].Insert(1);
HeadNodes[1].Insert(4); HeadNodes[1].Insert(3); HeadNodes[1].Insert(0);
HeadNodes[2].Insert(6); HeadNodes[2].Insert(5); HeadNodes[2].Insert(0);
HeadNodes[3].Insert(7); HeadNodes[3].Insert(1);
HeadNodes[4].Insert(7); HeadNodes[4].Insert(1);
HeadNodes[5].Insert(7); HeadNodes[5].Insert(2);
HeadNodes[6].Insert(7); HeadNodes[6].Insert(2);
HeadNodes[7].Insert(6); HeadNodes[7].Insert(5); HeadNodes[7].Insert(4);
HeadNodes[7].Insert(3);
}
void Graph::Setup2()
{
HeadNodes[0].Insert(1); //
HeadNodes[1].Insert(2); HeadNodes[1].Insert(3); HeadNodes[1].Insert(0);//
HeadNodes[2].Insert(1); HeadNodes[2].Insert(4); //
HeadNodes[3].Insert(5); HeadNodes[3].Insert(1); HeadNodes[3].Insert(4);//
HeadNodes[4].Insert(3); HeadNodes[4].Insert(2); //
HeadNodes[5].Insert(7); HeadNodes[5].Insert(6);//
HeadNodes[6].Insert(7); HeadNodes[6].Insert(5);//
HeadNodes[7].Insert(6); HeadNodes[7].Insert(5); HeadNodes[7].Insert(8);
HeadNodes[7].Insert(9);
HeadNodes[8].Insert(7);
HeadNodes[9].Insert(7);
}
// Driver
void Graph::DFS()
{
visited = new Boolean[n]; // @visited@ is declared as a @Boolean@/(** data member of @Graph@.
for (int i = 0; i < n; i++)
visited[i] = FALSE; // initially, no vertices have been visited
DFS(0); // start search at vertex 0
delete [] visited;
}
// Workhorse
void Graph::DFS(const int v)
// visit all previously unvisited vertices that are reachable from vertex @v@
{
visited[v] = TRUE; cout << v << ", ";
ListIterator<int> li(HeadNodes[v]);
if (! li.NotNull())
return;
int w = *li.First();
while (1)
{
if (! visited[w])
DFS(w);
if (li.NextNotNull())
w = *li.Next();
else
return;
}
}
void Graph::Components()
{
int i;
visited = new Boolean[n];
for (i = 0; i < n; i++)
visited[i] = FALSE;
for (i = 0; i < n; i++)
if (! visited[i])
{
cout << endl << "New Component :";
DFS(i); // @DFS@ is modified to print a vertex when it is visited
}
delete [] visited;
}
void Graph::DfnLow(const int x)
{
num = 1;
dfn = new int[n];
low = new int[n];
for (int i = 0; i < n; i++) { dfn[i] = low[i] = 0;}
DfnLow(x, -1);
delete [] dfn;
delete [] low;
}
void Graph::DfnLow (const int u, const int v)
{
dfn[u] = low[u] = num++;
ListIterator<int> li(HeadNodes[u]);
if (! li.NotNull())
return;
int w = *li.First();
while (1)
{
if (dfn[w] == 0)
{
DfnLow(w, u);
if (low[w] < low[u])
low[u] = low[w];
}
else
{
if (w != v)
{
if (dfn[w] < low[u])
low[u] = dfn[w];
}
}
if (li.NextNotNull())
w = *li.Next();
else
return;
}
}
void Graph::Out()
{
for (int i = 0; i < n; i++)
{
cout << i << ": " << dfn[i] << " " << low[i] << endl;
}
}
void main()
{
Graph g(10);
g.Setup2();
// g.Components();
g.DfnLow(3);
g.Out();
getch();
}
分享到:
相关推荐
4.1 Graphs, Adjacency Structures, and Adjacency Graphs . . . . . . . . 117 4.2 Some Basics of Graph Theory . . . . . . . . . . . . . . . . . . . . . . 125 4.3 Oriented Adjacency Graphs . . . . . . . ....
matlab程序,其功能为将邻接表转换为邻接矩阵,非常方便。
目录 Wireshark抓包全集(85种协议、类别的抓包文件) R1_to_R2.cap R1_to_R3.cap R1_to_R4.cap R3_to_R4.cap 802.1D_spanning_tree.cap 802.1Q_tunneling.cap 3560_CDP.cap ...EIGRP_adjacency.cap ......
邻接矩阵遍历,可以实现邻接矩阵的深度和广度遍历
Returning Lists and Scalars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 Using Literal SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...
an adjacency list for a direct graph, input the information of the graph through keyboard~
Steganalysis by Subtractive Pixel Adjacency Matrix
1.3.1. 深度优先搜索 Depth first search (DFS) 1.3.1.1. 概念 1.3.1.2. 求无向连通图中的桥 Finding bridges in undirected graph 1.3.2. 广度优先搜索 Breadth first search (BFS) 1.4. 拓扑排序 Topological sort...
自己看了Steganalysis+by+Subtractive+Pixel+Adjacency+Matrix+之后总结的,话糙理不糙。
资源分类:Python库 所属语言:Python 资源全名:nltools-0.3.5.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
Give a divide and conquer algorithm for the following problem: you are given two sorted lists of size m and n, and are allowed unit time access to the ith element of each list. Give an O(lg m + lgn) ...
2.2. Adjacency matrixandrelated graph descriptors .... 195 2.3. Clustercoefficient and extendedconnectivity . .... 196 Contents xix 2.4. Graph distances ..................... 198 2.5. Weighted graphs...
最短路径的O(ElgV)的解法。 使用邻接表存储图,使用堆操作选取下一个最小路径点。...参考:http://www.geeksforgeeks.org/greedy-algorithms-set-7-dijkstras-algorithm-for-adjacency-list-representation/
1.3.1. 深度优先搜索 Depth first search (DFS) 1.3.1.1. 概念 1.3.1.2. 求无向连通图中的桥 Finding bridges in undirected graph 1.3.2. 广度优先搜索 Breadth first search (BFS) 1.4. 拓扑排序 Topological sort...
基于边缘连接方法的椭圆检测算法AAMED《Arc Adjacency Matrix-Based Fast Ellipse Detection》,核心思想是使用弧段邻接矩阵获得所有弧段的组合方法,然后使用提出的基于采样点的思想的验证方法进行验证。
数据结构图的遍历class LinkedDigraph; class LinkedGraph; template <class T> class LinkedWDigraph; template <class T> class ...{// Output the adjacency lists. for (int i = 1; i ; i++) { cout ;
邻接表图问题的邻接表类目前处于早期开发阶段。
数字图像盲取证技术的研究主要集中在图像来源认证、图像篡改检测和图像隐秘分析三个方面。这篇论文是基于邻域差分矩阵的图像隐秘分析核心论文英文版
return this.adjacencyList.contains(new SNode(i)); } public void removeAdjacencyNode(int i) { this.adjacencyList.remove(new SNode(i)); } public void addAdjacencyNode(int i) { this....
用邻接表实现个图的存储,在VISUAL C++环境中实现